How to Set Specific Probabilities Using the LMSR?

15 Jun 2016 in Finance Last modified at: 2018-02-26

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)
        q'
        (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: $$\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 $$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})}}}$$

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

How hard can it be?