Study notes: The Bookmaker Is a Learner: The Mathematics

A scoring rule pays s_i(p) for a reported distribution p when outcome i occurs. It is proper if \mathbb E_{i\sim r}s_i(r)\ge\mathbb E_{i\sim r}s_i(p) for all r,p: reporting one’s belief maximizes expected score. It is strictly proper if equality holds only at p=r. The logarithmic rule is s_i(p)=b\log p_i.

The payments telescope: the operator pays s_k(p^T)-s_k(p^0) when the outcome is k. For the logarithmic rule this is b\log p^T_k-b\log\frac1n\le b\log n, since \log p^T_k\le0.

C(q)=\log(e^{q_1}+e^{q_2}). The cost is C(1,0)-C(0,0)=\log\frac{e+1}{2}\approx0.620. The new price is \frac{e}{e+1}\approx0.731. If outcome 1 occurs the bookmaker pays 1 and has collected 0.620, a loss of 0.380, within the bound \log 2\approx0.693.

Differentiable, monotone, and translation-invariant: C(q+k\mathbf 1)=C(q)+k (Lemma 5). Translation invariance says that k shares of every outcome cost exactly k, as they must, since they pay k whatever happens. Differentiating it in k gives prices that sum to one.

Outcomes are experts. The shares outstanding q_{i,t} are expert i’s cumulative gains. The learning rate is \eta=1/b, and Hedge’s weights are the LMSR prices. By convexity of C the bookmaker’s revenue is at least \sum_tw_t\cdot r_t, and it pays at most \max_iG_{i,T}, so its loss is at most Hedge’s regret: b\log n+T\varepsilon^2/(2b) for trades of size at most \varepsilon. For fixed volume the second term vanishes as trades become small, leaving b\log n.

Play w_t=p(-\varepsilon L_{t-1}): the market’s state is q_t=-\varepsilon L_t, so step t trades r_t=-\varepsilon l_t. Bounded loss gives \max_i\sum_tr_{i,t}-\sum_t(C(q_t)-C(q_{t-1}))\le B, and the Taylor bound of Lemma 3 replaces each cost difference by w_t\cdot r_t with error \varepsilon^2\varphi/2. Dividing by \varepsilon: regret \le B/\varepsilon+\varepsilon\varphi T/2, minimized at \varepsilon=\sqrt{2B/(\varphi T)} with value \sqrt{2B\varphi T} (Theorem 4). For the LMSR, \partial p_i/\partial q_j=p_i(\delta_{ij}-p_j)/b gives \varphi=2/b, and B=b\log n, so the bound is 2\sqrt{T\log n}, independent of b.

C(q)=\sup_{p\in\Delta_n}\bigl(p\cdot q-\alpha(p)\bigr) for a convex lower semicontinuous \alpha (Lemma 6). The prices \nabla C(q) are the maximizers (Lemma 7). The worst-case loss from q=0 is at most \sup_{p,p'}(\alpha(p)-\alpha(p')) (Lemma 8). For the LMSR \alpha(p)=b\sum_ip_i\log p_i, which ranges from -b\log n at the uniform distribution to 0 at a vertex, so the bound is b\log n.

\alpha_C(p)=\sum_ip_is_i(p), the expected score of a truthful report. In reverse, s_i(p)=\alpha_C(p)-\sum_jp_j\partial_j\alpha_C(p)+\partial_i\alpha_C(p). For the LMSR \partial_i\alpha_C=b(\log p_i+1), so \sum_jp_j\partial_j\alpha_C=\alpha_C+b and s_i(p)=b\log p_i.

The cost-function market with \alpha_C=R/\eta, at q=-L_{t-1}: by Lemma 7 its prices maximize p\cdot q-\alpha_C(p), which is the same problem. With R the negative entropy this is Hedge and the LMSR.

It charges the dual price of the final solution for the whole filled quantity, p(x^*)^\top a\,x^*, which is not truthful. The repair charges the integral of the marginal prices as the order is filled, which coincides with VCG pricing. The repaired payment is C(q+ax^*)-C(q) with C(q)=\min_t\bigl(t-u(t\mathbf 1-q)\bigr): a convex cost-function market (Theorem 13). Conversely every convex cost-function market is an SCPM with u(s)=-C(-s) (Theorem 14). The step from duals to a cost function is sensitivity analysis: optimal multipliers are shadow prices.

• Divisible subset-bet matching: polynomial. The ellipsoid method needs only a separation oracle, and the worst outcome is a maximum-weight perfect matching between candidates and positions (Theorem 16).
• Pair-bet matching: NP-hard, divisible or not, through minimum feedback arc set.
• LMSR pricing of subset bets: #P-hard, by reduction from the permanent.
• LMSR pricing of pair bets: #P-hard, by reduction from counting linear extensions.

It keeps an n\times n doubly stochastic matrix, multiplies entry (k,j) by e^{q_{kj}/b} after a trade, and restores double stochasticity by Sinkhorn balancing; these are PermELearn’s weights. It is not the exact LMSR over permutations, whose prices need permanents. Its worst-case loss is at most b\,n\log n in the limit of small trades, against b\log n! for the exact LMSR. The guarantee is a regret bound, not an approximation ratio for LMSR prices.

It makes a dynamic mechanism only myopically incentive compatible: reporting one’s estimate is optimal for a trader who ignores the effect of the report on later traders. Under some information structures a trader gains by bluffing.