How to Set Specific Probabilities Using the LMSR?

How many shares do you need to buy/sell in the in a prediction market using the Logarithmic Market Scoring Rule (LMSR) to change the price/probability of an asset to a specific value?

This post assumes knowledge about prediction markets and market scoring rules. I think the original paper by Robin Hanson provides a good introduction.

There are basically two approaches to buying/selling the right amount of shares to reach a certain probability. Method #1 is the sledgehammer approach, Method #2 is elegant, but tedious for more complicated price functions.

Method #1

Doing some kind of binary search until the price is “close enough”. I’ve written some example code in Clojure:

(defn set-to-prob [q i prob]
  (loop [lower (magically-find-lower-bound q i prob)
         upper (magically-find-upper-bound q i prob)]
    (let [q_i'  (/ (+ upper lower) 2)
          q'    (assoc q i q_i')
          p'    (p i q')]
      (if (close? 0.1 p' prob)
        (if (> p' prob)
          (recur lower q_i')
          (recur q_i'  upper))))))

Other than inelegance, this has the obvious flaw that it’s difficult to find reasonable upper and lower bounds for the number of outstanding shares.

I used a simple implementation for the upper (lower) bound that added (subtracted) a multiple mm of the liquidity parameter bb, but it was always possible to force an infinite loop by using an input q\vec{q} so that maxi,jqiqj>mb\max_{i, j} \vert q_i - q_j \vert > m \, b.

Method #2

It’s possible to solve analytically for the number of shares qiq_i to move the price to a certain probability pip_i.

I’ve actually found the solution in this GitHub repository, but there was no hint as to how the solution was arrived at (maybe obvious when you have better math skills 🙁). However, eventually I was able to figure it out 😏. So if you are like me and need to have every baby step laid out, here they are:

We know the price function for the LMSR is pi(q)=eqi/bjeqj/bp_i(\vec{q}) = \frac{e^{q_i/b}}{\sum_j{e^{q_j/b}}}

For a specific price/probability pip_i for outcome ii, it must be the case that pi=eqi/beqi/b+jieqj/bp_i = \frac{e^{q_i/b}}{e^{q_i/b} + \sum_{j \neq i}{e^{q_j/b}}}

where ji\sum_{j \neq i} iterates over all indices in q\vec{q} except for ii.

Using some math magic: pi(eqi/b+jieqj/b)=eqi/bpieqi/b+pijieqj/b=eqi/bpijieqj/b=eqi/bpieqi/bpijieqj/b=eqi/b(1pi)pi1pijieqj/b=eqi/blog(pi1pijieqj/b)=qib\begin{aligned} p_i \left(e^{q_i/b} + \sum_{j \neq i}{e^{q_j/b}}\right) &= e^{q_i/b} \\[2em] p_i\, e^{q_i/b} + p_i \sum_{j \neq i}{e^{q_j/b}} &= e^{q_i/b} \\[2em] p_i \sum_{j \neq i}{e^{q_j/b}} &= e^{q_i/b} - p_i\, e^{q_i/b} \\[2em] p_i \sum_{j \neq i}{e^{q_j/b}} &= e^{q_i/b}(1 - p_i) \\[2em] \frac{p_i}{1 - p_i} \sum_{j \neq i}{e^{q_j/b}} &= e^{q_i/b} \\[2em] \log{\left(\frac{p_i}{1 - p_i} \sum_{j \neq i}{e^{q_j/b}}\right)} &= \frac{q_i}b \end{aligned}

Which finally leads to qi=b log(pi1pijieqj/b)q_i = b\ \log{\left(\frac{p_i}{1 - p_i} \sum_{j \neq i}{e^{q_j/b}}\right)}

which is the number of shares that element ii in the quantity vector q\vec{q} needs to be changed to, in order for the price of contract ii to reach price pip_i.

For the number of shares Δqi\Delta q_i to buy/sell, the current amount of shares qi,tq_{i,t} needs to be subtracted Δqi=qiqi,t\Delta q_i = q_i - q_{i,t}.

Now somebody needs to do the same for the the liquidity-sensitive LMSRpi(q)=αlog(jeqj/b(q))+jqjeqi/b(q)jqjeqj/b(q)jqjjeqj/b(q)p_i(\vec{q}) = \alpha \log\left({\sum_j{e^{q_j/b(\vec{q})}}}\right) + \frac{\sum_j{q_j \, e^{q_i/b(\vec{q})}} - \sum_j{q_j \, e^{q_j/b(\vec{q})}}} {\sum_j{q_j} \sum_j{e^{q_j/b(\vec{q})}}}

where b(q)=αjqjb(\vec{q}) = \alpha \sum_j{q_j}

How hard can it be?

© 2022 Florian Klampfer

Powered by Hydejack v9.1.6