inamerrata

Some additional notes on implementing Hanson’s Logarithmic Market Scoring Rule, based on David Pennock’s post from 2006.

Usage is to is to pick \(n\) distinct outcomes, such that exactly one will be true, and then to trade contracts that correspond with each outcome, so that if the outcome occurs the corresponding contract has a unit payoff, and otherwise is worthless. The market scoring rule provides a way for a market maker to set and update prices for the outcomes no matter how they might be bought and sold. While the market maker’s worst-case loss is limited to a fixed amount, \(F\), this is also the usual outcome.

The scoring rule uses a cost function, defined as:

\[ C(q) = \beta \ln\left( \sum_{i=1}^{n}{e^{\frac{q_i}{\beta}}} \right) \]

At any point, if event \(i\) occurs, the payoff owed to participants is \(q_i\). In order to achieve any given combination of payouts per outcome, a participant need simply pay \(C(q+\delta) – C(q)\) where \(\delta_i\) is the participant’s desired payout for event \(i\).

Prices thus vary non-linearly depending on both current payoff’s expected, and desired payoff. However a number of properties can be easily verified. First, the total payout for any event \(j\) is no more than \(C(q)\):

\[ \begin{aligned}
C(q) & = \beta \ln\left( \sum_{i=1}^{n}{e^{\frac{q_i}{\beta}}} \right) \\
e^{\frac{C(q)}{\beta}} & = \sum_{i=1}^{n}{e^{\frac{q_i}{\beta}}} \\
& \ge e^{\frac{q_j}{\beta}} \\
C(q) & \ge q_j
\end{aligned} \]

If we define the initial state, \(q^0\) by \(q^0_i=0\) for all \(i\), then \(C(q^0)=\beta \ln(n)\). \(C(q^0)\) is the maximum amount we can lose (since we will have received the remaining \(C(q)-C(q^0)\) from participants), and as such, we can define \(\beta\) in terms of the funds the marked maker can afford to lose, \(F\), as:

\[ \beta = \frac{F}{\ln(n)} \]

We can see that the cost of buying a payout of \(p\) in all scenarios (which we will denote as \(\delta = p\iota\), meaning \(\delta_i=p\) for all \(i\)) is exactly \(p\):

\[ \begin{aligned}
C(q+p\iota) & = \beta \ln\left( \sum_{i=1}^{n}{e^{\frac{q_i+p}{\beta}}} \right) \\
& = \beta \ln\left( \sum_{i=1}^{n}{e^{\frac{q_i}{\beta}} e^{\frac{p}{\beta}}} \right) \\
& = \beta \ln\left( \sum_{i=1}^{n}{e^{\frac{q_i}{\beta}}} \right) + \beta \ln\left( e^{\frac{p}{\beta}} \right) \\
& = C(q) + p \\
\end{aligned} \]

The instantaneous price of each contract is given by the derivative of the cost function, which works out to be:

\[ p_i(q) = \frac{\partial{C(q)}}{\partial{q_i}} = \frac{e^{\frac{q_i}{\beta}}}{\sum_{j=1}^{n}{e^{\frac{q_j}{\beta}}}} \]

We can directly observe from this that at any time the instantaneous prices of all the events will be between 0 and 1, and that they will sum to exactly 1. Furthermore, if we maintain a record of the values of \(C(q)\) (which represents the sum of funds received from participants and the maximum loss) and \(p_i(q)\), we can calculate \(q_i\):

\[ \begin{aligned}
p_i(q) & = \frac{e^{\frac{q_i}{\beta}}}{\sum_{j=1}^{n}{e^{\frac{q_j}{\beta}}}} \\
& = \frac{e^{\frac{q_i}{\beta}}}{e^{\frac{C(q)}{\beta}}} \\
& = e^{\frac{q_i}{\beta} – \frac{C(q)}{\beta}} \\
& = e^{\frac{q_i – C(q)}{\beta}} \\
\beta \ln\left( p_i(q) \right) &= q_i – C(q) \\
q_i &= C(q) + \beta \ln\left( p_i(q) \right) \\
\end{aligned} \]

Note that since \(0 \lt p_i(q) \lt 1\), then \(\beta \ln\left( p_i(q) \right) \lt 0\) and \(q_i \lt C(q)\) as expected.

If we partition the possible states into three disjoint sets, \(W\), \(L\) and \(I\), such that

\[ \delta_i = \left\{ \begin{array}{l l}
-c & \quad \mbox{ iff \(i \in L\) } \\
0 & \quad \mbox{ iff \(i \in I\) } \\
g & \quad \mbox{ iff \(i \in W\) }
\end{array} \right. \]

For notational convenience, we will write \(p_S(q) = \sum_{i \in S}{p_i(q)}\). If we set \(c > 0\) and \(C(q+\delta) = C(q)\), we then can determine \(g\):

\[ \begin{aligned}
C(q+\delta) & = C(q) \\
\beta \ln\left( \sum_{i=1}^{n}{e^{\frac{q_i+\delta_i}{\beta}}} \right)
& = \beta \ln\left( \sum_{i=1}^{n}{e^{\frac{q_i}{\beta}}} \right) \\
\sum_{i=1}^{n}{e^{\frac{q_i+\delta_i}{\beta}}}
& = \sum_{i=1}^{n}{e^{\frac{q_i}{\beta}}} \\
\sum_{i \in L}{e^{\frac{q_i-c}{\beta}}}
+ \sum_{i \in I}{e^{\frac{q_i}{\beta}}}
+ \sum_{i \in W}{e^{\frac{q_i+g}{\beta}}}
& = \sum_{i \in L}{e^{\frac{q_i}{\beta}}}
+ \sum_{i \in I}{e^{\frac{q_i}{\beta}}}
+ \sum_{i \in W}{e^{\frac{q_i}{\beta}}} \\
\sum_{i \in L}{e^{-\frac{c}{\beta}} e^{\frac{q_i}{\beta}}}
+ \sum_{i \in W}{e^{\frac{g}{\beta}} e^{\frac{q_i}{\beta}}}
& = \sum_{i \in L}{e^{\frac{q_i}{\beta}}}
+ \sum_{i \in W}{e^{\frac{q_i}{\beta}}} \\
e^{-\frac{c}{\beta}} \sum_{i \in L}{e^{\frac{q_i}{\beta}}}
+ e^{\frac{g}{\beta}} \sum_{i \in W}{e^{\frac{q_i}{\beta}}}
& = \sum_{i \in L}{e^{\frac{q_i}{\beta}}}
+ \sum_{i \in W}{e^{\frac{q_i}{\beta}}} \\
e^{-\frac{c}{\beta}} \sum_{i \in L}{p_i(q)}
+ e^{\frac{g}{\beta}} \sum_{i \in W}{p_i(q)}
& = \sum_{i \in L}{p_i(q)}
+ \sum_{i \in W}{p_i(q)} \\
e^{-\frac{c}{\beta}} p_L(q)
+ e^{\frac{g}{\beta}} p_W(q)
& = p_L(q) + p_W(q) \\
e^{\frac{g}{\beta}} p_W(q)
& = p_L(q) + p_W(q) – e^{-\frac{c}{\beta}} p_L(q) \\
e^{\frac{g}{\beta}}
& = 1 + \frac{p_L(q)}{p_W(q)} \left(1 – e^{-\frac{c}{\beta}} \right) \\
g & = \beta \ln\left( 1 + \frac{p_L(q)}{p_W(q)} \left(1 – e^{-\frac{c}{\beta}} \right) \right) \\
\end{aligned} \]

Since \(c > 0\), \(e^{-\frac{c}{\beta}} \lt 1\) and \(g\) is well defined and positive. This allows us to purchase \(c\iota\) and \(\delta\) at a total cost of \(c\), with the result that we end up losing \(c\) if an event in \(L\) occurs, we end up breaking even if an event in \(I\) occurs, and we gain \(g\) if an event in \(W\) occurs.

This provides a fairly straightforward way to calculate gains for a given cost using the prices, rather than the cost function directly.

Rather than choosing a particular amount to pay for a particular gain, it’s possible to determine how much it will cost to change the prices in a particular way. We might take the same sets, \(W\), \(I\), and \(L\) and instead decide to adjust the prices as follows:

\[ p_i(q+\delta) = p_i(q) \cdot \left\{ \begin{array}{l l}
y & \quad \mbox{ iff \(i \in L\) } \\
1 & \quad \mbox{ iff \(i \in I\) } \\
x & \quad \mbox{ iff \(i \in W\) }
\end{array} \right. \]

If we take \(p_W(q+\delta) = p_W(q) \cdot x = p_W(q) + \rho\) then since the prices always add to one, \(p_L(q+\delta) = p_L(q) \cdot y = p_L(q) – \rho\) and \(y = 1 – \frac{p_W(q)}{p_L(q)}(x-1)\)

The corresponding \(c\) and \(g\) values are then

\[ \begin{aligned}
x & = e^{\frac{g}{\beta}} \\
g & = \beta \ln(x) \\
& = \beta \ln\left( \frac{p_W(q) + \rho}{p_W(q)} \right) \\
& = \beta \ln(p_W(q+\delta)) – \beta \ln(p_W(q)) \\
\\
y & = e^{\frac{-c}{\beta}} \\
c & = -\beta \ln(y) \\
& = -\beta \ln\left( 1 – \frac{p_W(q)}{p_L(q)}(x-1) \right) \\
& = -\beta \ln\left( 1 – \frac{p_W(q)}{p_L(q)}\left( 1+\frac{\rho}{p_W(q)}-1 \right) \right) \\
& = -\beta \ln\left( 1 – \frac{\rho}{p_L(q)} \right) \\
& = \beta \ln\left( \frac{p_L(q)}{p_L(q) – \rho} \right) \\
& = \beta \ln(p_L(q)) – \beta \ln(p_L(q+\delta)) \\
\end{aligned} \]

Note that this assumes each price in \(W\) is multiplied by the same amount, and similarly for each price in \(L\). This also has the benefit that it maintains the relative prices within \(W\) and \(L\).

Obviously, \(I\) can be the empty set. The advantage of having outcomes in \(I\) is it allows participants to make their estimates conditional. For instance the statement “If X happens, Y will happen” should warrant a gain if “X and Y” happens, a loss if “X but not Y” happens, and no change if either “not X and not Y” or “not X but Y” happen.

This can also be used if a market may need to be cancelled. This may be done by having a “cancellation” outcome such that every action a participant may take results in that outcome being in \(I\). This prevents people from exiting the market place at a profit before the outcome is known, however.

Splitting and merging outcomes is an interesting possibility — if the price of “it will happen on Tuesday” is \(p\), then splitting that event into two events “it will happen on Tuesday morning” and “it will happen on Tuesday afternoon”, each with price \(p/2\) would allow more precise predictions. Having this happen dynamically (such as when \(p\) rises above a particular limit) would allow for precision only when it’s needed.

The drawback is that it may require an increase in \(F\) (but not always — once Tuesday has been split into morning and afternoon, splitting Wednesday as well can simply reuse the same extra funds). Having different “sized” regions may also require some care. Representation also becomes a possible issue. Some of the maths for handling this might also help with handling initial state \(q^0\) with different prices \(p_i(q^0) \ne p_j(q^0)\).