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

第五章 逻辑相关的事件:凸多面体、Frank-Wolfe 投影与套利证书

「赢一州」与「赢全国」

第四章的约束只涉及互斥结果。更多的套利藏在逻辑相关的合约之间:某候选人「赢得 A 州」「赢得 B 州」「赢得全国」分别挂牌交易,各有各的盘口与交易者,但它们的价格必须相互一致。若全国结果由三州的多数决定,那么三州都很可能赢、全国却不太可能赢的报价就不可能同时正确。

问题是:「一致」的确切含义是什么?对少数几份合约,可以写出几条规则;对成百上千份相关合约,规则的数目会爆炸。Hanson 在提出 LMSR 时就把组合市场列为核心难题 (Hanson 2003);Dudík、Lahaie 与 Pennock,以及 Kroer、Dudík、Lahaie 与 Balakrishnan,用凸优化与整数规划把它变得可解 (Dudík et al. 2012; Kroer et al. 2016)。本章用一个最小的例子把其中的几何讲清楚。

可行价格就是一个凸多面体

推导

边际多面体。 三个州 A、B、C 与全国 N(三州中赢得多数)。联合状态有 8 个,每个给出一个支付向量 𝝓(s)=(a,b,c,maj(a,b,c))\boldsymbol{\phi}(s) = (a, b, c, \text{maj}(a,b,c))。一组价格 𝜽\boldsymbol{\theta} 是一致的,当且仅当它是这 8 个顶点的凸组合——即存在一个关于 8 个状态的概率分布,使每份合约的价格等于它的期望支付。不在多面体内的价格向量,必然存在一个在所有状态下都赚钱的组合。

推导

投影与证书。 设 𝝁*\boldsymbol{\mu}^* 是 𝜽\boldsymbol{\theta} 在多面体 ℳ\mathcal{M} 上的欧氏投影。投影的最优性条件说,对任意顶点 𝝓(s)\boldsymbol{\phi}(s) 有 (𝝁*−𝜽)⋅(𝝓(s)−𝝁*)≥0(\boldsymbol{\mu}^* – \boldsymbol{\theta}) \cdot (\boldsymbol{\phi}(s) – \boldsymbol{\mu}^*) \ge 0。于是以价格 𝜽\boldsymbol{\theta} 买入组合 𝒙=𝝁*−𝜽\mathbf{x} = \boldsymbol{\mu}^* – \boldsymbol{\theta},在任何状态下的收益 𝒙⋅(𝝓(s)−𝜽)≥‖𝝁*−𝜽‖2>0.\mathbf{x}\cdot(\boldsymbol{\phi}(s) – \boldsymbol{\theta}) \;\ge\; \lVert \boldsymbol{\mu}^* – \boldsymbol{\theta} \rVert^2 > 0 . 换成第二章 LMSR 的几何——二元 KL 散度这一布雷格曼散度——证书变为 𝒙=logit⁡𝝁*−logit⁡𝜽\mathbf{x} = \operatorname{logit}\boldsymbol{\mu}^* – \operatorname{logit}\boldsymbol{\theta},保证收益不低于对称化的散度 D(𝝁*,𝜽)+D(𝜽,𝝁*)D(\boldsymbol{\mu}^*, \boldsymbol{\theta}) + D(\boldsymbol{\theta}, \boldsymbol{\mu}^*)。

Frank-Wolfe:只需要一个线性预言机

求投影的困难在于多面体通常没有现成的不等式描述:顶点可以列举(或用整数规划逐个找出),面却多得写不下。Frank-Wolfe 算法恰好只需要前者 (Frank and Wolfe 1956; Jaggi 2013):每一步问「沿当前梯度,哪个顶点最好?」,然后向它走一步。普通的 Frank-Wolfe 在答案位于多面体的某个面上时会锯齿式前进,收敛很慢;成对(pairwise)变体把权重从最差的活跃顶点直接挪到预言机给出的顶点,在多面体上线性收敛 (Lacoste-Julien and Jaggi 2015)。

第十段程序对报价 (0.65, 0.62, 0.60, 0.40) 求投影。三州价格之和是 1.87,而多数规则要求它不超过 1+2N=1.801 + 2N = 1.80。

推导

# Chapter 5. p10: Frank-Wolfe projection onto the marginal polytope.
# Contracts: A, B, C (a candidate carries state A, B, C) and N (carries
# a majority of the three). The 8 joint states give 8 payoff vectors
# (a, b, c, maj(a, b, c)); coherent prices are exactly the convex hull of
# these vertices. Quoted prices theta = (0.65, 0.62, 0.60, 0.40).
# Frank-Wolfe needs only a linear oracle (best vertex for a direction),
# which is why it scales to markets whose polytope has too many facets to
# write down. Plain FW zigzags when the answer lies on a face; the
# pairwise variant moves weight from the worst active vertex to the
# oracle's vertex and converges fast. Two geometries:
#   E  Euclidean: certificate x = mu - theta gains at least |mu-theta|^2
#      in every state
#   K  binary KL, the LMSR's Bregman geometry: x = logit(mu) -
#      logit(theta) gains at least D(mu,theta) + D(theta,mu) everywhere
import itertools
import math

THETA = (0.65, 0.62, 0.60, 0.40)
V = [(a, b, c, 1 if a + b + c >= 2 else 0)
     for a, b, c in itertools.product((0, 1), repeat=3)]

def dot(u, v):
    return math.fsum(x * y for x, y in zip(u, v))

def point(w):
    return [math.fsum(w[i] * V[i][j] for i in w) for j in range(4)]

def search(obj, mu, d, top):
    lo, hi = 0.0, top
    for _ in range(80):
        m1, m2 = lo + (hi - lo) / 3, hi - (hi - lo) / 3
        f1 = obj([a + m1 * b for a, b in zip(mu, d)])
        f2 = obj([a + m2 * b for a, b in zip(mu, d)])
        lo, hi = (lo, m2) if f1 < f2 else (m1, hi)
    return (lo + hi) / 2

def fw(grad, obj, iters, pairwise):
    w = {i: 1 / len(V) for i in range(len(V))}
    log = []
    for t in range(1, iters + 1):
        mu = point(w)
        g = grad(mu)
        # ties are broken by index after rounding, so the path does not
        # depend on the last bit of a sum
        s = min(range(len(V)), key=lambda i: (round(dot(g, V[i]), 12), i))
        gap = dot(g, [a - b for a, b in zip(mu, V[s])])
        if pairwise:
            a = max(w, key=lambda i: (round(dot(g, V[i]), 12), -i))
            d = [x - y for x, y in zip(V[s], V[a])]
            step = search(obj, mu, d, w[a])
            w[a] -= step
            w[s] = w.get(s, 0.0) + step
            if w[a] <= 1e-15:
                del w[a]
        else:
            d = [x - y for x, y in zip(V[s], mu)]
            step = search(obj, mu, d, 1.0)
            w = {i: (1 - step) * v for i, v in w.items()}
            w[s] = w.get(s, 0.0) + step
        if t in (1, 5, 20, 100, 400):
            log.append((t, obj(point(w)), gap))
    return point(w), log

def lg(p):
    p = min(max(p, 1e-12), 1 - 1e-12)
    return math.log(p / (1 - p))

def kl(m, th):
    s = 0.0
    for a, b in zip(m, th):
        a = min(max(a, 1e-12), 1 - 1e-12)
        s += a * math.log(a / b) + (1 - a) * math.log((1 - a) / (1 - b))
    return s

def check(x, bound):
    pay = [dot(x, [a - b for a, b in zip(v, THETA)]) for v in V]
    print("   certificate x = {}".format([round(a, 4) for a in x]))
    print("   gain per state: min {:.5f}  max {:.5f};  bound {:.5f}"
          .format(min(pay), max(pay), bound))

if __name__ == "__main__":
    print("theta = {}: A+B+C = {:.2f} but 1 + 2N = {:.2f}".format(
        THETA, sum(THETA[:3]), 1 + 2 * THETA[3]))
    e_obj = lambda m: 0.5 * math.fsum((a - b) ** 2 for a, b in zip(m, THETA))
    e_grad = lambda m: [a - b for a, b in zip(m, THETA)]
    k_obj = lambda m: kl(m, THETA)
    k_grad = lambda m: [lg(a) - lg(b) for a, b in zip(m, THETA)]
    for name, grad, obj, pw in (("E plain FW", e_grad, e_obj, False),
                                ("E pairwise FW", e_grad, e_obj, True),
                                ("K pairwise FW", k_grad, k_obj, True)):
        mu, log = fw(grad, obj, 400, pw)
        print("\n{}: mu = {}".format(name, [round(a, 4) for a in mu]))
        for t, f, gap in log:
            shown = "{:.1e}".format(gap) if gap >= 1e-8 else "< 1e-8"
            print("   iter {:3d}  objective {:.3e}  FW gap {}"
                  .format(t, f, shown))
        if name.startswith("E"):
            x = [a - b for a, b in zip(mu, THETA)]
            check(x, dot(x, x))
        else:
            x = [lg(a) - lg(b) for a, b in zip(mu, THETA)]
            check(x, kl(mu, THETA) + kl(THETA, mu))
    print("\nReading: the four quotes cannot all be right. The projection")
    print("lowers the states and raises N; its certificate gains in all 8")
    print("states by at least the divergence removed - once converged.")
    print("Plain FW after 400 steps is not converged and its certificate")
    print("falls short of the bound; the pairwise variant is exact.")
# theta = (0.65, 0.62, 0.6, 0.4): A+B+C = 1.87 but 1 + 2N = 1.80
#
# E plain FW: mu = [0.6328, 0.603, 0.5839, 0.4334]
#    iter   1  objective 1.934e-02  FW gap 1.4e-01
#    iter   5  objective 1.266e-02  FW gap 5.0e-02
#    iter  20  objective 6.408e-03  FW gap 1.4e-02
#    iter 100  objective 2.215e-03  FW gap 6.2e-03
#    iter 400  objective 9.791e-04  FW gap 1.8e-03
#    certificate x = [-0.0172, -0.017, -0.0161, 0.0334]
#    gain per state: min 0.00086  max 0.01828;  bound 0.00196
#
# E pairwise FW: mu = [0.64, 0.61, 0.59, 0.42]
#    iter   1  objective 1.934e-02  FW gap 1.4e-01
#    iter   5  objective 1.008e-02  FW gap 6.2e-02
#    iter  20  objective 4.330e-04  FW gap 2.0e-03
#    iter 100  objective 3.500e-04  FW gap < 1e-8
#    iter 400  objective 3.500e-04  FW gap < 1e-8
#    certificate x = [-0.01, -0.01, -0.01, 0.02]
#    gain per state: min 0.00070  max 0.01070;  bound 0.00070
#
# K pairwise FW: mu = [0.6404, 0.6101, 0.5899, 0.4202]
#    iter   1  objective 7.936e-02  FW gap 5.5e-01
#    iter   5  objective 4.112e-02  FW gap 2.5e-01
#    iter  20  objective 3.020e-03  FW gap 5.6e-02
#    iter 100  objective 1.467e-03  FW gap < 1e-8
#    iter 400  objective 1.467e-03  FW gap < 1e-8
#    certificate x = [-0.0418, -0.0418, -0.0418, 0.0836]
#    gain per state: min 0.00293  max 0.04474;  bound 0.00293
#
# Reading: the four quotes cannot all be right. The projection
# lowers the states and raises N; its certificate gains in all 8
# states by at least the divergence removed - once converged.
# Plain FW after 400 steps is not converged and its certificate
# falls short of the bound; the pairwise variant is exact.

普通 Frank-Wolfe 走了 400 步,目标值仍是 9.791e-04,证书在最差状态下只赚 0.00086,低于它自己的界 0.00196:没有收敛,界不成立(虽然组合仍然处处赚钱)。成对变体在 100 步之内收敛到 (0.64, 0.61, 0.59, 0.42):三州各降 0.01,全国升 0.02。证书 (−0.01,−0.01,−0.01,0.02)(-0.01, -0.01, -0.01, 0.02) 在所有 8 个状态下至少赚 0.00070,恰好等于界。KL 几何给出几乎相同的投影 (0.6404, 0.6101, 0.5899, 0.4202) 与一个放大的证书,最差状态收益 0.00293,也恰好等于对称化散度。

这个结果说的是:四个报价不可能同时正确,且市场自己的价格就足以证明这一点——无需知道谁会赢。

Frank-Wolfe 的收敛:目标值高出最优值的部分(对数轴)随迭代次数的变化;普通变体锯齿式缓慢下降,成对变体很快到达机器精度。

从证书到交易

证书是方向,不是规模。第十一段程序把它放大为「买 1 份全国、卖三州各 0.5 份」(卖一州等于以「1 减去价格」买它的 NO),再计入盘口深度、手续费、固定成本与半年锁仓。它还检验了一个实际问题:只用简单的逻辑规则筛查报价,能抓住多少不一致?

推导

# Chapter 5. p11: From certificate to trade, and why simple rules miss it.
# A. The certificate of p10, scaled to buy 1 N and sell 0.5 of each state
#    (selling a state = buying its NO at 1 - price), gains at least 0.035
#    per unit in every state. Each leg's book deepens by 0.01 per 2,000
#    contracts; fee phi P(1 - P) per contract; 2 per leg order; payout in
#    6 months. Annualised return on the capital locked is reported.
# B. 4,000 random price vectors in [0.02, 0.98]^4. A vector is incoherent
#    if its Euclidean distance to the polytope (pairwise FW, as in p10)
#    exceeds 1e-6. Two rule sets are tried as screens:
#      R1 pairwise logic: N >= s_i + s_j - 1 and N <= s_i + s_j
#      R2 R1 plus the counting rule 2N <= A + B + C <= 1 + 2N
import itertools
import random

THETA = (0.65, 0.62, 0.60, 0.40)
V = [(a, b, c, 1 if a + b + c >= 2 else 0)
     for a, b, c in itertools.product((0, 1), repeat=3)]
UNIT = (-0.5, -0.5, -0.5, 1.0)
STEP, DEPTH, FIXED, TAU = 0.01, 2000.0, 2.0, 0.5

def trade(k, phi):
    capital = gain_min = 0.0
    for q, th in zip(UNIT, THETA):
        n = abs(q) * k
        px = th if q > 0 else 1 - th
        avg = px + STEP * n / DEPTH / 2
        capital += n * avg + phi * n * px * (1 - px) + FIXED
    payoff = min(sum(abs(q) * k * (v[j] if q > 0 else 1 - v[j])
                     for j, q in enumerate(UNIT)) for v in V)
    return payoff - capital, capital

def dist(th, iters=300):
    w = {i: 1 / 8 for i in range(8)}
    for _ in range(iters):
        mu = [sum(w[i] * V[i][j] for i in w) for j in range(4)]
        g = [a - b for a, b in zip(mu, th)]
        s = min(range(8), key=lambda i: sum(x * y for x, y in zip(g, V[i])))
        a = max(w, key=lambda i: sum(x * y for x, y in zip(g, V[i])))
        d = [x - y for x, y in zip(V[s], V[a])]
        dd = sum(x * x for x in d)
        if dd == 0:
            break
        st = max(0.0, min(w[a], -sum(x * y for x, y in zip(g, d)) / dd))
        w[a] -= st
        w[s] = w.get(s, 0.0) + st
        if w[a] <= 1e-15:
            del w[a]
    mu = [sum(w[i] * V[i][j] for i in w) for j in range(4)]
    return sum((a - b) ** 2 for a, b in zip(mu, th)) ** 0.5

def rules(th, counting):
    a, b, c, n = th
    for x, y in ((a, b), (a, c), (b, c)):
        if n < x + y - 1 or n > x + y:
            return False
    if counting and not (2 * n <= a + b + c <= 1 + 2 * n):
        return False
    return True

if __name__ == "__main__":
    c1 = sum(abs(q) * (th if q > 0 else 1 - th)
             for q, th in zip(UNIT, THETA))
    g1 = min(sum(abs(q) * (v[j] if q > 0 else 1 - v[j])
                 for j, q in enumerate(UNIT)) for v in V) - c1
    print("A. one unit at quoted prices: gain {:.3f} on {:.3f}"
          " = {:.2%} in 6 months".format(g1, c1, g1 / c1))
    print("   units   phi    net gain   capital   annualised")
    for phi in (0.0, 0.02, 0.07):
        best = max(range(10, 40001, 10), key=lambda k: trade(k, phi)[0])
        sizes = (500, 2000) + ((best,) if trade(best, phi)[0] > 0 else ())
        for k in sizes:
            net, cap = trade(k, phi)
            ann = ((cap + net) / cap) ** (1 / TAU) - 1
            print("   {:6d}  {:4.2f}  {:9.2f}  {:8.1f}   {:+.1%}".format(
                k, phi, net, cap, ann))
    rng = random.Random(59011)
    inc = r1 = r2 = 0
    for _ in range(4000):
        th = [rng.uniform(0.02, 0.98) for _ in range(4)]
        if dist(th) > 1e-6:
            inc += 1
            r1 += not rules(th, False)
            r2 += not rules(th, True)
    print("\nB. incoherent vectors: {} of 4000".format(inc))
    print("   caught by R1 (pairwise logic):     {:5.1%}".format(r1 / inc))
    print("   caught by R2 (plus counting rule): {:5.1%}".format(r2 / inc))
    print("\nReading: the guaranteed gain is small next to the capital it")
    print("locks - 3.63 % for six months before costs, at best 4.6 % a")
    print("year after depth and fixed costs, and a loss at every size with")
    print("a 0.07 fee. Pairwise logic misses part of the incoherence")
    print("that the polytope catches; for this tiny market one more rule")
    print("closes the gap, but real markets have too many facets to list,")
    print("which is why the vertex oracle matters.")
# A. one unit at quoted prices: gain 0.035 on 0.965 = 3.63% in 6 months
#    units   phi    net gain   capital   annualised
#       500  0.00       8.41     491.6   +3.4%
#      2000  0.00      44.50    1955.5   +4.6%
#      4000  0.00      62.00    3938.0   +3.2%
#       500  0.02       2.49     497.5   +1.0%
#      2000  0.02      20.84    1979.2   +2.1%
#      2650  0.02      22.67    2627.3   +1.7%
#       500  0.07     -12.30     512.3   -4.7%
#      2000  0.07     -38.32    2038.3   -3.7%
#
# B. incoherent vectors: 2518 of 4000
#    caught by R1 (pairwise logic):     92.9%
#    caught by R2 (plus counting rule): 100.0%
#
# Reading: the guaranteed gain is small next to the capital it
# locks - 3.63 % for six months before costs, at best 4.6 % a
# year after depth and fixed costs, and a loss at every size with
# a 0.07 fee. Pairwise logic misses part of the incoherence
# that the polytope catches; for this tiny market one more rule
# closes the gap, but real markets have too many facets to list,
# which is why the vertex oracle matters.

按报价计,一个单位锁定 0.035 的利润,占用 0.965 的资金,即半年 3.63%。计入深度与固定成本后,最好的情形是 2,000 个单位、年化 +4.6%,刚过无风险利率;ϕ=0.02\phi = 0.02 时最好也只有年化 +2.1%;ϕ=0.07\phi = 0.07 时每个规模都亏。组合套利的数学是确定的,可执行的利润却和第四章一样薄。

B 段在 4,000 个随机报价向量中找出 2,518 个不一致的向量。只检查两两逻辑(「赢两州则必赢全国」之类)的规则 R1 抓住 92.9%;加上计数规则 2N≤A+B+C≤1+2N2N \le A + B + C \le 1 + 2N 之后,R2 抓住 100.0%。对这个小市场,十条不等式就是多面体的全部描述;但对五十个州的选举人团,顶点有 2502^{50} 个,面的数目无法列出,这时线性预言机——一个可以用整数规划求解的「最好的结局是哪个」的问题——就是唯一可行的入口 (Kroer et al. 2016)。

注

「套利空间」的含义。 本章的证书只在报价不变时成立。真实盘口里,第一条腿成交后其余报价可能改变(第四章的腿部风险);而且相关合约常常在不同平台、不同结算规则下交易,「全国」一词在两份合约里的定义未必相同。数学上的不一致是套利的必要条件,不是充分条件。

假说 · 尚未验证

作者的假说(尚未验证): 在同一平台上同时挂牌的、逻辑相关的选举合约中,由多面体投影找出的不一致,其幅度在选举前最后两周明显大于更早的时期,因为新信息先到达流动性最好的合约、后到达其余合约。什么结果会证明它错:投影距离在选举周期中没有趋势,或最后两周更小。

小结

逻辑相关合约的一致价格构成一个凸多面体——联合状态支付向量的凸包。报价落在多面体之外,就存在一个在所有状态下都赚钱的组合;把报价投影到多面体上,投影方向就是这个组合,保证收益不低于投影所去掉的散度(欧氏几何下是距离的平方,LMSR 几何下是对称化的 KL 散度)。Frank-Wolfe 只需要线性预言机,因此能处理面多到写不下的组合市场;成对变体在多面体上快速收敛,普通变体可能在 400 步后仍未收敛、证书的界不成立。两两逻辑规则会漏掉一部分不一致。可执行的利润仍受深度、手续费与锁仓限制,例子中最好的年化回报只有 +4.6%。

参考文献

Dudík, Miroslav, Sébastien Lahaie, and David M. Pennock. 2012. “A Tractable Combinatorial Market Maker Using Constraint Generation.” Proceedings of the 13th ACM Conference on Electronic Commerce (EC), 459–76.
Frank, Marguerite, and Philip Wolfe. 1956. “An Algorithm for Quadratic Programming.” Naval Research Logistics Quarterly 3 (1–2): 95–110.
Hanson, Robin. 2003. “Combinatorial Information Market Design.” Information Systems Frontiers 5 (1): 107–19.
Jaggi, Martin. 2013. “Revisiting Frank–Wolfe: Projection-Free Sparse Convex Optimization.” Proceedings of the 30th International Conference on Machine Learning (ICML), PMLR, vol. 28: 427–35.
Kroer, Christian, Miroslav Dudík, Sébastien Lahaie, and Sivaraman Balakrishnan. 2016. “Arbitrage-Free Combinatorial Market Making via Integer Programming.” Proceedings of the 2016 ACM Conference on Economics and Computation (EC), 161–78.
Lacoste-Julien, Simon, and Martin Jaggi. 2015. “On the Global Linear Convergence of Frank–Wolfe Optimization Variants.” Advances in Neural Information Processing Systems 28 (NeurIPS), 496–504.

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