5D Library › 预测市场微观结构、布雷格曼信息投影与跨盘口无套利边界 · English

第二章 对数市场评分规则:Softmax、KL 散度与补贴上限

没有对手方的市场

订单簿市场需要有人挂单。交易稀少的问题——一场小型选举、一项内部项目能否按期完成——往往没有足够的对手方,价格要么不存在,要么停在很久以前。Hanson 的解决办法是让一个自动做市商永远报价,并为它的亏损设一个上限 (Hanson 2003, 2007)。这个做市商就是对数市场评分规则(LMSR)。

它的设计源自适当评分规则:一个预测者报出概率 pp,若结果 ii 发生,得到 ln⁡pi\ln p_i 分;诚实地报出自己的信念,期望得分最高 (Gneiting and Raftery 2007)。LMSR 把评分规则变成市场:每位交易者付钱「接手」上一位的预测,并按自己的新预测得分。

成本函数与它的凸对偶

推导

LMSR。 设各结果的已售份数为 𝒒\mathbf{q},流动性参数为 bb。做市商的成本函数与价格为 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}} . 价格就是 𝒒/b\mathbf{q}/b 的 Softmax。买入 Δ𝒒\Delta\mathbf{q} 要付 C(𝒒+Δ𝒒)−C(𝒒)C(\mathbf{q} + \Delta\mathbf{q}) – C(\mathbf{q})。它的凸对偶是 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 , 也就是负熵在单纯形上的共轭。Chen 与 Pennock 用效用框架描述了这一类有界亏损做市商 (Chen and Pennock 2007),Abernethy、Chen 与 Wortman Vaughan 证明了一般的成本函数做市商都对应一个凸正则项,并与在线学习中的「跟随正则化领先者」算法一一对应 (Abernethy et al. 2013)。

第四段程序逐项核对这些性质。

推导

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

第一项检查对偶等式:残差在机器精度以内。第二项是一笔具体交易:价格从 (0.4718, 0.3162, 0.212) 被推到 (0.60, 0.25, 0.15),交易者只买不卖,付出 34.587。之后无论哪个结果发生,净收益都恰好是 bln⁡(pi′/pi)b \ln(p'_i / p_i):结果 0 发生得 +24.042,结果 2 发生则亏 −34.587。这就是对数评分规则:交易者因改进了预测而得分,因弄错了而失分。

第三项把这笔账取期望。若交易者的信念正是 p′p',他的期望收益为 3.3614,恰好等于 bb 乘以 KL 散度 DKL(p′∥p)D_{\mathrm{KL}}(p' \,\|\, p),也恰好等于负熵的布雷格曼散度 (Bregman 1967)。KL 散度是负熵生成的布雷格曼散度;Csiszár 用它建立了概率分布的「信息投影」几何 (Csiszár 1975)。所以 LMSR 里的每一笔交易都是一次信息投影:交易者把市场的分布投影到自己的分布上,做市商为这段距离付钱。

推导

最坏情况的亏损。 设市场从均匀价格开始,最终结果 ii 发生。做市商卖出的份额中只有 qiq_i 要兑付,而它收到的总额为 C(𝒒)−C(𝟎)C(\mathbf{q}) – C(\mathbf{0})。由 C(𝒒)≥qiC(\mathbf{q}) \ge q_i 与 C(𝟎)=bln⁡nC(\mathbf{0}) = b \ln n,亏损 qi−C(𝒒)+C(𝟎)≤bln⁡nq_i – C(\mathbf{q}) + C(\mathbf{0}) \le b \ln n。

第四项把价格推到确定:两个结果的亏损为 69.31,四个 138.63,十个 230.26,五十个 391.20——都等于 bln⁡nb \ln n。这就是做市商为整个市场的信息所付的补贴上限,只在市场完全确定时达到。上限随结果数的对数增长,所以多结果的市场只贵一点点。

流动性参数买的是什么

bb 是唯一的设计参数。它同时决定两件事:做市商最多亏多少,以及一笔订单能把价格推多远。

推导

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

b=50b = 50 时补贴上限只有 34.7,但一笔 100 元的买单就把价格从 0.50 推到 0.9323;b=1000b = 1000 时同一笔买单只把价格推到 0.5476,平均成交价 0.5238,补贴上限却是 693.1。把价格从 0.50 推到 0.60,所需金额恰为 0.2231b0.2231\,b,在 b=1000b = 1000 时是 223.1。

最后一列是最坏亏损乘以价格冲击。它随 bb 增大而趋于一个常数,34.66,即 100ln⁡2/2100 \ln 2 / 2。原因是:在价格 0.50 附近,金额为 xx 的小单把价格推动约 x/(2b)x/(2b),而最坏亏损是 bln⁡2b \ln 2,两者的乘积与 bb 无关。选择 bb 不能逃出这个权衡,只能沿着它移动:要更深的市场,就得付更多的补贴。

LMSR 的流动性权衡:做市商最坏亏损(对数轴)与一笔 100 元买单造成的价格变动(对数轴);圆点为 p05 表中的四个 b 值。

注

流动性敏感的变体。 Othman、Pennock、Reeves 与 Sandholm 提出让 bb 随交易量增长的变体,使市场在交易活跃时自动加深 (Othman et al. 2013)。它改变了补贴随时间的分配,但在任何给定时刻,深度与补贴之间的权衡仍然存在。本书只讨论固定的 bb。

假说 · 尚未验证

作者的假说(尚未验证): 在使用 LMSR 的内部预测市场中,按「最坏亏损 / 参与人数」设定 bb 的市场,其最终预测的布赖尔分数优于把 bb 设得很大或很小的市场;bb 太小时价格被少数大单左右,太大时价格不动、交易者失去动力。什么结果会证明它错:在预先登记的多个内部市场中,预测精度与 bb 无关,或单调地随 bb 增大而提高。

小结

LMSR 的价格是份额的 Softmax,成本函数是负熵的凸共轭;每笔交易的收益恰为对数评分之差,交易者的期望收益恰为 KL 散度——负熵的布雷格曼散度,因此每笔交易都是一次信息投影。做市商的最坏亏损是 bln⁡nb \ln n。流动性参数 bb 在补贴与价格冲击之间做精确的交换:对小单而言,两者之积趋于与 bb 无关的常数。

参考文献

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