5D Library › Prediction Market Microstructure, Bregman Information Projection and Cross-Book Arbitrage Bounds · 中文
Chapter 2. The Logarithmic Market Scoring Rule: Softmax, KL Divergence and the Subsidy Cap
A market without a counterparty
An order-book market needs someone to post orders. Thinly traded questions — a small election, whether an internal project will ship on time — often lack counterparties, so the price either does not exist or is stale. Hanson’s solution is an automated market maker that always quotes and whose loss is capped (Hanson 2003, 2007). That market maker is the logarithmic market scoring rule (LMSR).
Its design comes from proper scoring rules: a forecaster who reports probabilities scores if outcome happens, and reporting one’s true belief maximises the expected score (Gneiting and Raftery 2007). The LMSR turns the scoring rule into a market: each trader pays to “take over” the previous forecast and is scored on the new one.
The cost function and its convex dual
Calculation
The LMSR. Let be the shares sold for each outcome and the liquidity parameter. The market maker’s cost function and prices are The prices are the softmax of . Buying costs . The convex dual is the conjugate of negative entropy on the simplex. Chen and Pennock described this family of bounded-loss market makers in a utility framework (Chen and Pennock 2007), and Abernethy, Chen and Wortman Vaughan showed that every cost-function market maker corresponds to a convex regulariser, matching “follow the regularised leader” in online learning one for one (Abernethy et al. 2013).
The fourth program checks these properties one by one.
Calculation
# Chapter 2. p04: Hanson's logarithmic market scoring rule (LMSR) and its
# convex dual. Outstanding shares q (one per outcome) cost
# C(q) = b ln sum_i exp(q_i / b), prices p = softmax(q / b).
# Four facts are checked numerically:
# 1. duality C(q) = p.q + b H(p), H = entropy (so C is the convex
# conjugate of -b H on the simplex)
# 2. payoff moving prices from p to p' and then seeing outcome i
# earns exactly b ln(p'_i / p_i)
# 3. Bregman a trader who believes p' and moves the price to p'
# expects b KL(p' || p); KL is the Bregman divergence of
# negative entropy
# 4. bound the market maker's worst-case loss is b ln n
import math
def cost(q, b):
m = max(q)
return m + b * math.log(math.fsum(math.exp((x - m) / b) for x in q))
def prices(q, b):
m = max(q)
e = [math.exp((x - m) / b) for x in q]
s = math.fsum(e)
return [x / s for x in e]
def entropy(p):
return -math.fsum(x * math.log(x) for x in p if x > 0)
def kl(a, c):
return math.fsum(x * math.log(x / y) for x, y in zip(a, c) if x > 0)
def bregman_negent(a, c):
f = lambda v: math.fsum(x * math.log(x) for x in v if x > 0)
grad = [math.log(y) + 1 for y in c]
return f(a) - f(c) - math.fsum(g * (x - y)
for g, x, y in zip(grad, a, c))
if __name__ == "__main__":
b = 100.0
q = [30.0, -10.0, -50.0]
p = prices(q, b)
print("b = 100, q = {} -> prices {}".format(
q, [round(x, 4) for x in p]))
gap = cost(q, b) - math.fsum(x * y for x, y in zip(p, q)) - b * entropy(p)
print("1. |C(q) - p.q - b H(p)| < 1e-9: {}".format(abs(gap) < 1e-9))
target = [0.60, 0.25, 0.15]
dq = [b * (math.log(t) - math.log(x)) for t, x in zip(target, p)]
dq = [d - min(dq) for d in dq] # buy only; same prices
q2 = [x + d for x, d in zip(q, dq)]
paid = cost(q2, b) - cost(q, b)
print("2. buy {} shares -> prices {}; pay {:.3f}".format(
[round(d, 2) for d in dq], target, paid))
for i in range(3):
print(" outcome {}: net {:+8.3f} b ln(p'_i/p_i) {:+8.3f}".format(
i, dq[i] - paid, b * math.log(target[i] / p[i])))
exp_profit = math.fsum(t * (d - paid) for t, d in zip(target, dq))
print("3. expected profit under p' {:.4f}; b KL(p'||p) {:.4f};"
" b Bregman {:.4f}".format(exp_profit, b * kl(target, p),
b * bregman_negent(target, p)))
print("4. worst case: start uniform, outcome 0 wins, price of 0 -> 1")
for n in (2, 4, 10, 50):
q0 = [0.0] * n
qn = [3000.0] + [0.0] * (n - 1)
loss = 3000.0 - (cost(qn, b) - cost(q0, b))
print(" n = {:2d}: loss at q_0 = 3000 is {:7.2f};"
" b ln n = {:7.2f}".format(n, loss, b * math.log(n)))
print("\nReading: the LMSR is the entropy-regularised market: its prices")
print("are a softmax, a trader's expected gain is a KL (Bregman)")
print("divergence, and the subsidy for that information is capped at")
print("b ln n, reached only when the market becomes certain.")
# b = 100, q = [30.0, -10.0, -50.0] -> prices [0.4718, 0.3162, 0.212]
# 1. |C(q) - p.q - b H(p)| < 1e-9: True
# 2. buy [58.63, 11.08, 0.0] shares -> prices [0.6, 0.25, 0.15]; pay 34.587
# outcome 0: net +24.042 b ln(p'_i/p_i) +24.042
# outcome 1: net -23.504 b ln(p'_i/p_i) -23.504
# outcome 2: net -34.587 b ln(p'_i/p_i) -34.587
# 3. expected profit under p' 3.3614; b KL(p'||p) 3.3614; b Bregman 3.3614
# 4. worst case: start uniform, outcome 0 wins, price of 0 -> 1
# n = 2: loss at q_0 = 3000 is 69.31; b ln n = 69.31
# n = 4: loss at q_0 = 3000 is 138.63; b ln n = 138.63
# n = 10: loss at q_0 = 3000 is 230.26; b ln n = 230.26
# n = 50: loss at q_0 = 3000 is 391.20; b ln n = 391.20
#
# Reading: the LMSR is the entropy-regularised market: its prices
# are a softmax, a trader's expected gain is a KL (Bregman)
# divergence, and the subsidy for that information is capped at
# b ln n, reached only when the market becomes certain.The first item checks the duality identity: the residual is at machine precision. The second is a concrete trade: prices are pushed from (0.4718, 0.3162, 0.212) to (0.60, 0.25, 0.15) by buying only, at a cost of 34.587. Whatever then happens, the net gain is exactly : +24.042 if outcome 0 happens, −34.587 if outcome 2 does. This is the logarithmic scoring rule: the trader is scored for improving the forecast and penalised for getting it wrong.
The third item takes the expectation. If the trader’s belief is , the expected gain is 3.3614, exactly times the KL divergence and exactly the Bregman divergence of negative entropy (Bregman 1967). KL is the Bregman divergence generated by negative entropy; Csiszár used it to build the geometry of “information projection” between probability distributions (Csiszár 1975). Every trade in an LMSR is therefore an information projection: the trader projects the market’s distribution onto their own, and the market maker pays for the distance.
Calculation
The worst-case loss. Start the market at uniform prices and let outcome happen. Of the shares sold, only pay out, and the market maker has collected . Since and , the loss .
The fourth item drives the price to certainty: the loss is 69.31 with two outcomes, 138.63 with four, 230.26 with ten and 391.20 with fifty — each equal to . That is the cap on what the market maker pays for all the information in the market, reached only when the market becomes certain. The cap grows with the logarithm of the number of outcomes, so a many-outcome market costs only a little more.
What the liquidity parameter buys
is the only design parameter. It sets two things at once: how much the market maker can lose, and how far one order moves the price.
Calculation
# Chapter 2. p05: The liquidity parameter b buys depth with subsidy.
# Binary LMSR starting at a price of 0.50. For each b: the market maker's
# worst-case loss (b ln 2), the price after a trader spends 100 on YES,
# the average price paid, and the cost of moving the price from 0.50 to
# 0.60, which is b ln((1 - 0.50) / (1 - 0.60)) = 0.2231 b.
# A small order of size x at 0.50 moves the price by about x / (2 b), so
# (worst-case loss) x (price impact) tends to x ln(2) / 2 for every b:
# the trade-off cannot be escaped by choosing b, only moved along.
import math
def spend(budget, b, p0=0.5):
"""Shares s of YES bought for `budget` from price p0 (binary LMSR)."""
# cost(s) = b ln(1 - p0 + p0 e^{s/b}); invert it
s = b * math.log((math.exp(budget / b) - (1 - p0)) / p0)
p1 = p0 * math.exp(s / b) / (1 - p0 + p0 * math.exp(s / b))
return s, p1
if __name__ == "__main__":
print(" b worst loss price after 100 avg price move .50->.60"
" loss x impact")
for b in (50, 100, 250, 500, 1000, 5000):
s, p1 = spend(100.0, b)
move = b * math.log(0.5 / 0.4)
loss = b * math.log(2)
print(" {:5d} {:9.1f} {:13.4f} {:8.4f} {:11.1f} {:12.2f}"
.format(b, loss, p1, 100.0 / s, move, loss * (p1 - 0.5)))
print("\n order size needed to move 0.50 -> 0.60 at b = 1000:"
" {:.1f}".format(1000 * math.log(0.5 / 0.4)))
print("\nReading: small b means a cheap subsidy and a jumpy price; large")
print("b means a deep market that the operator pays for. The product of")
print("the two tends to 100 ln(2) / 2 = {:.2f} as orders become small"
.format(50 * math.log(2)))
print("relative to b.")
# b worst loss price after 100 avg price move .50->.60 loss x impact
# 50 34.7 0.9323 0.7625 11.2 14.98
# 100 69.3 0.8161 0.6712 22.3 21.91
# 250 173.3 0.6648 0.5840 55.8 28.56
# 500 346.6 0.5906 0.5456 111.6 31.41
# 1000 693.1 0.5476 0.5238 223.1 32.98
# 5000 3465.7 0.5099 0.5050 1115.7 34.31
#
# order size needed to move 0.50 -> 0.60 at b = 1000: 223.1
#
# Reading: small b means a cheap subsidy and a jumpy price; large
# b means a deep market that the operator pays for. The product of
# the two tends to 100 ln(2) / 2 = 34.66 as orders become small
# relative to b.At the subsidy cap is only 34.7, but a single buy order of 100 pushes the price from 0.50 to 0.9323; at the same order moves it only to 0.5476, at an average fill of 0.5238, but the cap is 693.1. Moving the price from 0.50 to 0.60 costs exactly , which is 223.1 at .
The last column is the worst-case loss times the price impact. As grows it tends to a constant, 34.66, which is . The reason: near a price of 0.50 a small order of size moves the price by about , while the worst-case loss is , so their product does not depend on . Choosing cannot escape this trade-off, only move along it: a deeper market needs a larger subsidy.
Note
The liquidity-sensitive variant. Othman, Pennock, Reeves and Sandholm proposed letting grow with trading volume, so the market deepens automatically when it is active (Othman et al. 2013). That changes how the subsidy is spread over time, but at any given moment the trade-off between depth and subsidy remains. This book treats only a fixed .
Hypothesis · not established
The author’s hypothesis (not yet tested): in internal prediction markets run on an LMSR, markets whose is set as “worst-case loss per participant” produce final forecasts with better Brier scores than markets with a very large or very small ; too small and a few large orders dominate the price, too large and the price barely moves, so traders lose the incentive to trade. What would show it wrong: across several pre-registered internal markets, accuracy is unrelated to , or improves monotonically as grows.
Summary
The LMSR’s prices are the softmax of its shares and its cost function is the convex conjugate of negative entropy; each trade earns exactly a difference of logarithmic scores, and a trader’s expected gain is exactly a KL divergence — the Bregman divergence of negative entropy — so every trade is an information projection. The market maker’s worst-case loss is . The liquidity parameter trades subsidy against price impact precisely: for small orders their product tends to a constant that does not depend on .
References
Fan, Y. (2026). Prediction Market Microstructure, Bregman Information Projection and Cross-Book Arbitrage Bounds: Logarithmic Market Scoring Rules, Favorite-Longshot Calibration Bias, Lock-Up Opportunity Cost and Frank-Wolfe Combinatorial Pricing [预测市场微观结构、布雷格曼信息投影与跨盘口无套利边界] (Version 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.24090166 · Licensed under Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0).