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 个,每个给出一个支付向量 。一组价格 是一致的,当且仅当它是这 8 个顶点的凸组合——即存在一个关于 8 个状态的概率分布,使每份合约的价格等于它的期望支付。不在多面体内的价格向量,必然存在一个在所有状态下都赚钱的组合。
推导
投影与证书。 设 是 在多面体 上的欧氏投影。投影的最优性条件说,对任意顶点 有 。于是以价格 买入组合 ,在任何状态下的收益 换成第二章 LMSR 的几何——二元 KL 散度这一布雷格曼散度——证书变为 ,保证收益不低于对称化的散度 。
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,而多数规则要求它不超过 。
推导
# 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。证书 在所有 8 个状态下至少赚 0.00070,恰好等于界。KL 几何给出几乎相同的投影 (0.6404, 0.6101, 0.5899, 0.4202) 与一个放大的证书,最差状态收益 0.00293,也恰好等于对称化散度。
这个结果说的是:四个报价不可能同时正确,且市场自己的价格就足以证明这一点——无需知道谁会赢。
从证书到交易
证书是方向,不是规模。第十一段程序把它放大为「买 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%,刚过无风险利率; 时最好也只有年化 +2.1%; 时每个规模都亏。组合套利的数学是确定的,可执行的利润却和第四章一样薄。
B 段在 4,000 个随机报价向量中找出 2,518 个不一致的向量。只检查两两逻辑(「赢两州则必赢全国」之类)的规则 R1 抓住 92.9%;加上计数规则 之后,R2 抓住 100.0%。对这个小市场,十条不等式就是多面体的全部描述;但对五十个州的选举人团,顶点有 个,面的数目无法列出,这时线性预言机——一个可以用整数规划求解的「最好的结局是哪个」的问题——就是唯一可行的入口 (Kroer et al. 2016)。
注
「套利空间」的含义。 本章的证书只在报价不变时成立。真实盘口里,第一条腿成交后其余报价可能改变(第四章的腿部风险);而且相关合约常常在不同平台、不同结算规则下交易,「全国」一词在两份合约里的定义未必相同。数学上的不一致是套利的必要条件,不是充分条件。
假说 · 尚未验证
作者的假说(尚未验证): 在同一平台上同时挂牌的、逻辑相关的选举合约中,由多面体投影找出的不一致,其幅度在选举前最后两周明显大于更早的时期,因为新信息先到达流动性最好的合约、后到达其余合约。什么结果会证明它错:投影距离在选举周期中没有趋势,或最后两周更小。
小结
逻辑相关合约的一致价格构成一个凸多面体——联合状态支付向量的凸包。报价落在多面体之外,就存在一个在所有状态下都赚钱的组合;把报价投影到多面体上,投影方向就是这个组合,保证收益不低于投影所去掉的散度(欧氏几何下是距离的平方,LMSR 几何下是对称化的 KL 散度)。Frank-Wolfe 只需要线性预言机,因此能处理面多到写不下的组合市场;成对变体在多面体上快速收敛,普通变体可能在 400 步后仍未收敛、证书的界不成立。两两逻辑规则会漏掉一部分不一致。可执行的利润仍受深度、手续费与锁仓限制,例子中最好的年化回报只有 +4.6%。
参考文献
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).