关于「稳定匹配:延迟接受、提前签约与说真话」,《布雷斯悖论与无秩序代价》给出的定量结论是什么?
结论:程序在 500 个随机的 6 × 6 市场上逐一检查了这些性质:结果全部稳定;每个提议者得到的都是他在全部稳定匹配(用穷举 720 种配对找出)中最好的伴侣;每个接受者得到的都是他最差的;随机打乱申请次序 5 次,结果都不变。稳定匹配常常不止一个:500 个市场中只有 183 个是唯一的,204 个有两个,最多的一个市场有 8 个。
数据口径:书中关于流量池与推荐算法的模型都是示意,不描述任何真实平台;本书不是投资、经营或营销建议。 书中以标注框区分已发表的证据、可运行的 Python 计算(16 段程序,全部核对)、原典与作者的假说。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 183, 204, 500
500 random 6 x 6 markets: stable 500/500, proposer-best 500/500, receiver-worst 500/500, order-free 500/500 number of stable matchings per market: 1: 183, 2: 204, 3: 78, 4: 25, 5: 7, 6: 2, 8: 1 3 x 3, proposers propose: [0, 1, 2]; ranks: proposers [1, 1, 1], receivers [3, 3, 3] 3 x 3, receivers propose: [2, 0, 1]; ranks: proposers [3, 3, 3], receivers [1, 1, 1] all stable matchings (proposer i -> receiver): [[0, 1, 2], [1, 2, 0], [2, 0, 1]]
查看完整验算程序
# Deferred acceptance (Gale & Shapley 1962) and the set of all stable matchings.
# Proposers and receivers each rank everyone on the other side. Checks on 500 random 6 x
# 6 markets: the result is stable; every proposer gets her best partner among ALL stable
# matchings; every receiver gets his worst; and the order in which proposers move does
# not matter.
import itertools, random
rng = random.Random(12)
def deferred_acceptance(P, R, order=None):
"""P[i] = proposer i's ranking of receivers, R[j] = receiver j's ranking of proposers.
Returns match[i] = receiver matched to proposer i."""
n = len(P)
rank = [{p: k for k, p in enumerate(R[j])} for j in range(n)]
nxt, held, free = [0] * n, {}, list(order if order else range(n))
while free:
i = free.pop(0); j = P[i][nxt[i]]; nxt[i] += 1
if j not in held: held[j] = i
elif rank[j][i] < rank[j][held[j]]: free.append(held[j]); held[j] = i
else: free.append(i)
match = [None] * n
for j, i in held.items(): match[i] = j
return match
def blocking_pairs(match, P, R):
n = len(P); partner = {j: i for i, j in enumerate(match)}
return [(i, j) for i in range(n) for j in range(n) if match[i] != j
and P[i].index(j) < P[i].index(match[i])
and R[j].index(i) < R[j].index(partner[j])]
def all_stable(P, R):
return [list(m) for m in itertools.permutations(range(len(P)))
if not blocking_pairs(m, P, R)]
def market(n):
P = [rng.sample(range(n), n) for _ in range(n)]
R = [rng.sample(range(n), n) for _ in range(n)]
return P, R
ok = {"stable": 0, "proposer-best": 0, "receiver-worst": 0, "order-free": 0}
counts = {}
for _ in range(500):
P, R = market(6)
m = deferred_acceptance(P, R)
S = all_stable(P, R)
counts[len(S)] = counts.get(len(S), 0) + 1
ok["stable"] += not blocking_pairs(m, P, R)
ok["proposer-best"] += all(P[i].index(m[i]) == min(P[i].index(s[i]) for s in S)
for i in range(6))
inv = lambda mm: {j: i for i, j in enumerate(mm)}
ok["receiver-worst"] += all(R[j].index(inv(m)[j])
== max(R[j].index(inv(s)[j]) for s in S)
for j in range(6))
ok["order-free"] += all(deferred_acceptance(P, R, rng.sample(range(6), 6)) == m
for _ in range(5))
print("500 random 6 x 6 markets:\n " + ", ".join(f"{k} {v}/500" for k, v in ok.items()))
print("number of stable matchings per market: "
+ ", ".join(f"{k}: {counts[k]}" for k in sorted(counts)))
# A small market with three stable matchings: which side proposes decides who is
# favoured.
P = [[0, 1, 2], [1, 2, 0], [2, 0, 1]] # proposer i likes receiver i best
R = [[1, 2, 0], [2, 0, 1], [0, 1, 2]] # receiver j likes proposer j + 1 best
mp = deferred_acceptance(P, R); mr = deferred_acceptance(R, P)
mr = [mr.index(i) for i in range(3)] # rewrite as proposer i -> receiver
for lab, m in (("proposers propose", mp), ("receivers propose", mr)):
print(f"3 x 3, {lab}: {m}; ranks: proposers "
f"{[P[i].index(m[i]) + 1 for i in range(3)]}, receivers "
f"{[R[m[i]].index(i) + 1 for i in range(3)]}")
print(f" all stable matchings (proposer i -> receiver): {all_stable(P, R)}")唯一数据源与引用
范雅福(Fan, Y.). (2026). 《算法博弈论、布雷斯悖论与流量分配的无秩序代价》第 6 章「稳定匹配:延迟接受、提前签约与说真话」(版本 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.23782094
DOI: 10.5281/zenodo.23782094 · 阅读本章所在专著 · 5DL-B-032 · v1.0.0 · CC-BY-NC-ND-4.0
BibTeX
@book{fan2026032,
author = {Fan, Yafu},
title = {Algorithmic Game Theory, Braess's Paradox and the Price of Anarchy in Traffic and Attention Networks},
year = {2026},
publisher = {5D Library},
edition = {1.0.0},
doi = {10.5281/zenodo.23782094},
url = {https://doi.org/10.5281/zenodo.23782094}
}