关于「稳定匹配:延迟接受、提前签约与说真话」,《布雷斯悖论与无秩序代价》给出的定量结论是什么?

结论:程序在 500 个随机的 6 × 6 市场上逐一检查了这些性质:结果全部稳定;每个提议者得到的都是他在全部稳定匹配(用穷举 720 种配对找出)中最好的伴侣;每个接受者得到的都是他最差的;随机打乱申请次序 5 次,结果都不变。稳定匹配常常不止一个:500 个市场中只有 183 个是唯一的,204 个有两个,最多的一个市场有 8 个。

数据口径:书中关于流量池与推荐算法的模型都是示意,不描述任何真实平台;本书不是投资、经营或营销建议。 书中以标注框区分已发表的证据、可运行的 Python 计算(16 段程序,全部核对)、原典与作者的假说。

English version

对照数据表

下表数字由本章 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}
}

本书其他章节结论