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 pp scores ln⁡pi\ln p_i if outcome ii 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 𝒒\mathbf{q} be the shares sold for each outcome and bb the liquidity parameter. The market maker’s cost function and prices are C(𝒒)=bln⁡∑ieqi/b,pi=eqi/b∑jeqj/b.C(\mathbf{q}) = b \ln \sum_i e^{q_i/b}, \qquad p_i = \frac{e^{q_i/b}}{\sum_j e^{q_j/b}} . The prices are the softmax of 𝒒/b\mathbf{q}/b. Buying Δ𝒒\Delta\mathbf{q} costs C(𝒒+Δ𝒒)−C(𝒒)C(\mathbf{q} + \Delta\mathbf{q}) – C(\mathbf{q}). The convex dual is C(𝒒)=max𝒑∈Δ[𝒑⋅𝒒+bH(𝒑)],H(𝒑)=−∑ipiln⁡pi,C(\mathbf{q}) = \max_{\mathbf{p} \in \Delta} \Big[\, \mathbf{p}\cdot\mathbf{q} + b H(\mathbf{p}) \Big], \qquad H(\mathbf{p}) = -\sum_i p_i \ln p_i , 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 bln⁡(pi′/pi)b \ln(p'_i / p_i): +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 p′p', the expected gain is 3.3614, exactly bb times the KL divergence DKL(p′∥p)D_{\mathrm{KL}}(p' \,\|\, p) 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 ii happen. Of the shares sold, only qiq_i pay out, and the market maker has collected C(𝒒)−C(𝟎)C(\mathbf{q}) – C(\mathbf{0}). Since C(𝒒)≥qiC(\mathbf{q}) \ge q_i and C(𝟎)=bln⁡nC(\mathbf{0}) = b \ln n, the loss qi−C(𝒒)+C(𝟎)≤bln⁡nq_i – C(\mathbf{q}) + C(\mathbf{0}) \le b \ln n.

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 bln⁡nb \ln n. 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

bb 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 b=50b = 50 the subsidy cap is only 34.7, but a single buy order of 100 pushes the price from 0.50 to 0.9323; at b=1000b = 1000 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 0.2231b0.2231\,b, which is 223.1 at b=1000b = 1000.

The last column is the worst-case loss times the price impact. As bb grows it tends to a constant, 34.66, which is 100ln⁡2/2100 \ln 2 / 2. The reason: near a price of 0.50 a small order of size xx moves the price by about x/(2b)x/(2b), while the worst-case loss is bln⁡2b \ln 2, so their product does not depend on bb. Choosing bb cannot escape this trade-off, only move along it: a deeper market needs a larger subsidy.

The LMSR’s liquidity trade-off: the market maker’s worst-case loss (log scale) against the price move caused by a buy of 100 (log scale); dots mark four values of b from p05’s table.

Note

The liquidity-sensitive variant. Othman, Pennock, Reeves and Sandholm proposed letting bb 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 bb.

Hypothesis · not established

The author’s hypothesis (not yet tested): in internal prediction markets run on an LMSR, markets whose bb is set as “worst-case loss per participant” produce final forecasts with better Brier scores than markets with a very large or very small bb; 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 bb, or improves monotonically as bb 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 bln⁡nb \ln n. The liquidity parameter bb trades subsidy against price impact precisely: for small orders their product tends to a constant that does not depend on bb.

References

Abernethy, Jacob, Yiling Chen, and Jennifer Wortman Vaughan. 2013. “Efficient Market Making via Convex Optimization, and a Connection to Online Learning.” ACM Transactions on Economics and Computation 1 (2): Article 12.
Bregman, L. M. 1967. “The Relaxation Method of Finding the Common Point of Convex Sets and Its Application to the Solution of Problems in Convex Programming.” USSR Computational Mathematics and Mathematical Physics 7 (3): 200–217.
Chen, Yiling, and David M. Pennock. 2007. “A Utility Framework for Bounded-Loss Market Makers.” Proceedings of the 23rd Conference on Uncertainty in Artificial Intelligence (UAI), 49–56.
Csiszár, Imre. 1975. “I-Divergence Geometry of Probability Distributions and Minimization Problems.” The Annals of Probability 3 (1): 146–58.
Gneiting, Tilmann, and Adrian E. Raftery. 2007. “Strictly Proper Scoring Rules, Prediction, and Estimation.” Journal of the American Statistical Association 102 (477): 359–78.
Hanson, Robin. 2003. “Combinatorial Information Market Design.” Information Systems Frontiers 5 (1): 107–19.
Hanson, Robin. 2007. “Logarithmic Market Scoring Rules for Modular Combinatorial Information Aggregation.” Journal of Prediction Markets 1 (1): 3–15.
Othman, Abraham, David M. Pennock, Daniel M. Reeves, and Tuomas Sandholm. 2013. “A Practical Liquidity-Sensitive Automated Market Maker.” ACM Transactions on Economics and Computation 1 (3): Article 14.

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).