5D Library › Prediction Market Microstructure, Bregman Information Projection and Cross-Book Arbitrage Bounds · 中文
Chapter 5. Logically Related Events: Convex Polytopes, Frank-Wolfe Projection and Arbitrage Certificates
“Wins a state” and “wins the country”
Chapter 4’s constraint involved only exclusive outcomes. More arbitrage hides between logically related contracts: a candidate “wins state A”, “wins state B” and “wins nationally” are listed separately, each with its own book and its own traders, yet their prices must agree. If the national result is decided by a majority of three states, then quotes saying the candidate will very likely win all three states but probably not the country cannot all be right.
The question is what “agree” means exactly. For a handful of contracts one can write down a few rules; for hundreds or thousands of related contracts the number of rules explodes. Hanson listed combinatorial markets as a central difficulty when he proposed the LMSR (Hanson 2003); Dudík, Lahaie and Pennock, and Kroer, Dudík, Lahaie and Balakrishnan, made them tractable with convex optimisation and integer programming (Dudík et al. 2012; Kroer et al. 2016). This chapter uses the smallest example to make the geometry plain.
Coherent prices form a convex polytope
Calculation
The marginal polytope. Three states A, B, C and the nation N (a majority of the three). There are 8 joint states, each giving a payoff vector . A price vector is coherent if and only if it is a convex combination of these 8 vertices — that is, if some probability distribution over the 8 states makes each contract’s price its expected payoff. For any price vector outside the polytope there is a portfolio that gains in every state.
Calculation
Projection and certificate. Let be the Euclidean projection of onto the polytope . Optimality of the projection says that for every vertex . So buying the portfolio at prices gains, in every state, In Chapter 2’s LMSR geometry — the binary KL divergence, a Bregman divergence — the certificate becomes , and the guaranteed gain is at least the symmetrised divergence .
Frank-Wolfe: a linear oracle is enough
The difficulty with projecting is that the polytope usually has no ready description by inequalities: its vertices can be listed (or found one at a time by integer programming), but its facets are too many to write down. Frank-Wolfe needs exactly the former (Frank and Wolfe 1956; Jaggi 2013): at each step it asks “along the current gradient, which vertex is best?” and moves toward it. Plain Frank-Wolfe zigzags and converges slowly when the answer lies on a face of the polytope; the pairwise variant moves weight directly from the worst active vertex to the oracle’s vertex and converges linearly on polytopes (Lacoste-Julien and Jaggi 2015).
The tenth program projects the quotes (0.65, 0.62, 0.60, 0.40). The three state prices sum to 1.87, while the majority rule requires at most .
Calculation
# 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.After 400 steps plain Frank-Wolfe still has an objective of 9.791e-04, and its certificate gains only 0.00086 in the worst state, below its own bound of 0.00196: it has not converged and the bound fails (although the portfolio still gains everywhere). The pairwise variant converges within 100 steps to (0.64, 0.61, 0.59, 0.42): each state down 0.01, the nation up 0.02. The certificate gains at least 0.00070 in all 8 states, exactly the bound. The KL geometry gives an almost identical projection (0.6404, 0.6101, 0.5899, 0.4202) and a scaled-up certificate whose worst-state gain, 0.00293, again equals the symmetrised divergence exactly.
What this says: the four quotes cannot all be right, and the market’s own prices are enough to prove it — without knowing who will win.
From certificate to trade
A certificate is a direction, not a size. The eleventh program scales it to “buy 1 nation, sell 0.5 of each state” (selling a state means buying its NO at one minus its price), then charges depth, fees, fixed costs and six months of lock-up. It also tests a practical question: how much incoherence does a screen of simple logical rules catch?
Calculation
# 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.At quoted prices one unit locks in 0.035 on 0.965 of capital, 3.63 % for six months. After depth and fixed costs the best case is 2,000 units at +4.6 % a year, just above the risk-free rate; at the best is +2.1 % a year; at every size loses. The mathematics of combinatorial arbitrage is exact, but the executable profit is as thin as in Chapter 4.
Part B finds 2,518 incoherent vectors among 4,000 random quotes. Rule set R1, which checks only pairwise logic (“winning two states means winning the country”, and the like), catches 92.9 %; adding the counting rule , R2 catches 100.0 %. For this small market ten inequalities describe the whole polytope; but an electoral college of fifty states has vertices and too many facets to list, and then the linear oracle — the integer program “which outcome is best for this direction?” — is the only way in (Kroer et al. 2016).
Note
What “arbitrage space” means. The certificates here hold only while quotes stay put. In a real book the other quotes may move once the first leg fills (Chapter 4’s leg risk); and related contracts often trade on different platforms under different settlement rules, so “national winner” may not mean the same thing in two contracts. Mathematical incoherence is necessary for arbitrage, not sufficient.
Hypothesis · not established
The author’s hypothesis (not yet tested): among logically related election contracts listed together on one platform, the incoherence found by polytope projection is clearly larger in the last two weeks before an election than earlier, because new information reaches the most liquid contracts first and the rest later. What would show it wrong: projection distance shows no trend over the election cycle, or is smaller in the last two weeks.
Summary
Coherent prices for logically related contracts form a convex polytope — the convex hull of the joint states’ payoff vectors. Quotes outside it admit a portfolio that gains in every state; projecting the quotes onto the polytope gives that portfolio as the direction of projection, with a guaranteed gain no smaller than the divergence the projection removes (the squared distance in Euclidean geometry, the symmetrised KL divergence in the LMSR’s geometry). Frank-Wolfe needs only a linear oracle, so it handles combinatorial markets whose facets are too many to write down; the pairwise variant converges quickly on polytopes, while the plain one can remain unconverged after 400 steps, with its certificate bound failing. Pairwise logical rules miss part of the incoherence. The executable profit is still limited by depth, fees and lock-up: in the example the best annual return is only +4.6 %.
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).