## LMSR Implementation Notes, two

At the end of my previous post I mentioned some thoughts on dealing with more interesting initial states (\(q^0\)). We’ll define our initial state by choosing the amount of funds we’re willing to lose \(F\), and a set of initial prices \(0 < p_i(q^0) < 1\). Unless \(p_i(q^0) = \frac{1}{n}\) for all \(i\), we will be forced to set \(q^0_i > 0\) in some (possibly all) cases. We will treat this as implying a virtual payout from the market maker to the market maker.

The maximum loss, is then given by \(C(q^0) – \min(q^0_i) = F\) (since the final payout will be \(q_j – q^0_j\), the money collected will be \(C(q)-C(q^0)\), and \(C(q) \ge q_j\)).

If we wish to restrict quantities \(q_i\) to be integers, we face a dificulty at this point. Working from the relationship between \(p_i(q^0)\) and \(q^0_i\) gives:

\[ \begin{aligned}

p_i(q^0) & = \frac{e^{q^0_i/\beta}}{\sum_{j=1}^{n}{e^{q^0_j/\beta}}} \\

& = \frac{e^{q^0_i/\beta}}{e^{C(q^0)/\beta}} \\

& = e^{q^0_i/\beta – C(q^0)/\beta} \\

\beta \ln( p_i(q^0) ) & = q^0_i – C(q^0) \\

q^0_i & = C(q^0) + \beta \ln( p_i(q^0 ) )

\end{aligned} \]

Since \(C(q^0)\) is independent of \(i\), we can immediately see that the \(i\) with minimal \(q^0_i\) will be the one with minimal price. Without loss of generality, assume that this is when \(i=1\), then we can see:

\[ \begin{aligned}

F & = C(q^0) – q^0_1 \\

& = C(q^0) – \left( C(q^0) + \beta \ln(p_1(q^0)) \right) \\

& = – \beta \ln(p_1(q^0)) \\

\beta & = \frac{F}{\ln\left(p_1(q^0)^{-1}\right)}

\end{aligned} \]

In the case where \(p_i(q^0) = \frac{1}{n}\) is common for all outcomes this simplifies to the formula seen in the previous post.

Note that this is unlikely to result in a value of \(\beta\) that is particularly easy to work with. However simply rounding down to the nearest representable number works fine — since \(\beta\) is in direct proportion to the amount of funds at risk, this simply rounds down the amount of funds at risk at the same rate.

Likewise, keeping track of \(p_i(q)\) as an implementation choice will restrict us to rational prices, and thus likely irrational values for \(q_i\). However it’s likely we’d prefer to only offer precisely defined payoffs for precisely defined costs, even if only for ease of accounting. In order to deal with this, we can treat \(q_i = m_i(q) + g_i(q)\) where \(m_i(q) \ge q^0_i\) represents the (possibly increasing) virtual payout the market maker will receive, and \(g_i(q)\) are the (integer) payouts participants will receive. In particular, we might restrict \(q^0_i \le m_i(q) < q^0_i + 1\), so that we can calculate costs and payouts using the normal floor and ceiling functions and ensure any proceeds go to participants. This gets us very close to being able to adjust the outcomes being considered dynamically; so that we can either split a single outcome into distinct categories to achieve a more precise estimate, or merging multiple outcomes into a single category to reduce the complexity of calculations. If we look at changing the \(m \dotso n\)th outcomes from \(q\) into new outcomes \(m' \dotso n'\) in \(r\), then our presumed constraints are as follows. First, if this is the most accurate assignment between the old states and the new states we can come up with (and if it's not, use those assignments instead), then we need to set the payout for all the new cases to the worst case payout for the old cases: $$ g_{i'}(r) = \left\{ \begin{array}{l l} g_i(q) & \quad 1 \le i' < m \\ \max_{m \le i \le n}(g_i(q)) & \quad m' \le i' \le n \\ \end{array} \right. $$ Also, since we're not touching the prices for the first \(m-1\) outcomes, and our prices need to add up to one, we have: \[ \begin{aligned} p_{i'}(r) & = p_{i'}(q) \quad \forall 1 \le i' < m \\ \sum_{i'=m'}^{n'} p_{i'}(r) & = \sum_{i=m}^{n} p_i(q) \end{aligned} \] And most importantly, we wish to limit the additional funds we commit to \(\Delta F\) (possibly zero or negative), and thus \(C(r) = C(q) + \Delta F\). Using the relationship between \(p_i(r)\) and \(r_i\) again, gives: \[ \begin{aligned} C(r) & = r_i - \gamma \ln(p_i(r)) \\ & = m_i(r) + g_i(r) - \gamma \ln(p_i(r)) \\ \Delta F & = m_i(r) + g_i(r) - C(q) - \gamma \ln(p_i(r)) \\ \Delta F & \ge g_i(r) - C(q) - \gamma \ln(p_i(r)) \\ \Delta F & \ge \left\{ \begin{array}{l l} g_i(q) - C(q) - \gamma \ln(p_i(q)) & \quad 1 \le i < m \\ g_i(r) - C(q) - \gamma \ln(p_i(r)) & \quad m \le i \le n \\ \end{array} \right. \\ \Delta F & \ge \left\{ \begin{array}{l l} g_i(q) - C(q) - \left(q_i - C(q)\right) & \quad 1 \le i < m \\ \max_{m \le j \le n}(g_j(q)) - C(q) - \gamma \ln(p_i(r)) & \quad m \le i \le n \\ \end{array} \right. \\ \Delta F & \ge \left\{ \begin{array}{l l} -m_i(q) & \quad 1 \le i < m \\ \max_{m \le j \le n}\left( g_j(q) - \left( q_j - \beta \ln(p_j(q)) \right) \right) - \gamma \ln(p_i(r)) & \quad m \le i \le n \\ \end{array} \right. \\ \Delta F & \ge \left\{ \begin{array}{l l} -m_i(q) & \quad 1 \le i < m \\ \max_{m \le j \le n}\left( -m_j(q) + \beta \ln(p_j(q)) \right) - \gamma \ln(p_i(r)) & \quad m \le i \le n \\ \end{array} \right. \\ \end{aligned} \] Setting where \(\mu\) to be the modified outcome with maximum payout (that is, \(g_\mu(q) = \max_{m \le j \le n}(g_j(q))\), \(m \le \mu \le n\)) and \(\nu\) to be the least new price (so \(m' \le \nu \le n\) such that \(p_\nu(r) = \min_{m' \le j \le n'}(p_i(r))\)) lets us simplify this to: $$ \Delta F \ge -m_i(q) \quad \forall 1 \le i < m $$ and $$ \gamma \le \frac{\Delta F + m_\mu(q) + \beta \ln\left(p_\mu(q)^{-1}\right)}{\ln\left(p_\nu(r)^{-1}\right)} $$ Since \(m_i(q) \ge 0\), one simple approach to satisfying the inequalities is to simply drop the \(m_i(q)\) terms, giving: $$ \Delta F \ge 0 \quad \text{and} \quad \gamma \le \frac{\Delta F + \beta \ln(p_\mu(q)^{-1})}{\ln(p_\nu(r)^{-1})} $$ This has the drawback of not providing the maximum liquidity for the funds thought to be at risk, however.

These posts suck to read via RSS.

That said, it is rather fascinating watching them render in the browser when viewed on your blog.

Yeah, they’re something of a pain to write too (since there’s no WYSIWYG for the equations). Switching from tweaking markup to preview and back gets a bit old; especially since the WordPress editor doesn’t do bracket matching…

GMailTeX composition works better for that, since it has an automatically updating WYSIWYG version of what you’re writing below the edit window; but given gmail changed it’s CSS enough to break it within 24 hours of my trying to use it, I’m left a bit unimpressed…