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 m of the liquidity parameter b, but it was always possible to force an infinite loop by using an input \vec{q} so that \max_{i, j} \vert q_i - q_j \vert > m \, b.

Method #2

It’s possible to solve analytically for the number of shares q_i to move the price to a certain probability p_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

p_i(\vec{q}) = \frac{e^{q_i/b}}{\sum_j{e^{q_j/b}}}

For a specific price/probability p_i for outcome i, it must be the case that

p_i = \frac{e^{q_i/b}}{e^{q_i/b} + \sum_{j \neq i}{e^{q_j/b}}}

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

Using some math magic:

  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

Which finally leads to

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 i in the quantity vector \vec{q} needs to be changed to, in order for the price of contract i to reach price p_i.

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

Now somebody needs to do the same for the the liquidity-sensitive LMSR

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})}}}


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

How hard can it be?