关于「延迟接受:只暂留、不拍板的算法为何必然收敛」,《稳定匹配与无私奔配对》给出的定量结论是什么?
结论:延迟接受把「先答应」改成「先暂留」:提议者沿着自己的名单往下走,接受方只把目前最好的一份留在手里,直到没有人再被退回。两条单调性,提议者只往下、接受方只往上换,足以证明算法一定会停、停下时一定没有私奔对。示意运行 p21 用 10 次提议得到一张稳定的表,其中 K4 落在自己的末位,却找不到任何愿意与他私奔的品牌。p22 显示,随机市场里平均提议次数低于威尔逊的上界,200 对时只占 n 的平方的 0.029;最坏情形 n 的平方减 n 加 1 确实可以达到,但需要极其特殊的偏好。处理顺序不影响结果,提议方向则影响很大,这是下一章的主题。
数据口径:书中的人物、档期与偏好均为示意;全部计算由书中程序生成;本书是非个人化经营建议,只使用当事人明示提供的偏好,不做未经同意的画像,配对结果只是建议,双方都可以拒绝。 第一章在示意扫描中发现口味越一致,先到先得越糟,平均私奔对从 4.14 个升到 14.12 个;评分优先只在所有买手看法完全一致时才稳定;罗斯对英国八个地区的比较单看计数,单侧费希尔检验 p 值为 0.2143,须与定理和实验复现一起才站得住。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 0.029, 10, 200, 21
| n markets mean proposals n*H_n mean/n^2 max seen | |
| 10 | 2000 24.1 29.3 0.241 48 |
| 20 | 1000 63.0 72.0 0.157 138 |
| 50 | 400 209.0 225.0 0.084 421 |
| 100 | 200 495.0 518.7 0.050 805 |
| 200 | 60 1153.2 1175.6 0.029 1663 |
| worst case found by hill climbing (5 restarts each): | |
| n | 4: 13 proposals, bound n^2 - n + 1 = 13 |
| n | 5: 21 proposals, bound n^2 - n + 1 = 21 |
| n | 6: 31 proposals, bound n^2 - n + 1 = 31 |
查看完整验算程序
# Chapter 2. p22: how many proposals does deferred acceptance need?
# Model: n creators propose to n brands, all rankings uniformly random
# (fixed seed, illustrative). Typical case: mean proposals against
# Wilson's (1972) bound n * H_n, where H_n is the n-th harmonic number
# (the sum of 1/k for k = 1 to n). Worst case: the count can never
# exceed n^2 - n + 1; a fixed-seed hill climb over preference lists
# looks for markets that reach it, to show the bound is attained.
import math
import random
rng = random.Random(20261113)
def proposals(cp, bp):
n = len(cp)
rank = [{k: i for i, k in enumerate(v)} for v in bp]
nxt, held, free, cnt = [0] * n, [None] * n, list(range(n)), 0
while free:
k = free.pop()
b = cp[k][nxt[k]]
nxt[k] += 1
cnt += 1
cur = held[b]
if cur is None:
held[b] = k
elif rank[b][k] < rank[b][cur]:
held[b] = k
free.append(cur)
else:
free.append(k)
return cnt
def rand_market(n):
return ([rng.sample(range(n), n) for _ in range(n)],
[rng.sample(range(n), n) for _ in range(n)])
print(" n markets mean proposals n*H_n mean/n^2 max seen")
for n, reps in ((10, 2000), (20, 1000), (50, 400), (100, 200),
(200, 60)):
v = [proposals(*rand_market(n)) for _ in range(reps)]
hn = n * math.fsum(1.0 / k for k in range(1, n + 1))
print("%4d %7d %14.1f %6.1f %8.3f %8d"
% (n, reps, math.fsum(v) / reps, hn,
math.fsum(v) / reps / n / n, max(v)))
def climb(n, iters):
cp, bp = rand_market(n)
cur = proposals(cp, bp)
for _ in range(iters):
side = cp if rng.random() < 0.5 else bp
r = rng.randrange(n)
a, b = rng.sample(range(n), 2)
side[r][a], side[r][b] = side[r][b], side[r][a]
val = proposals(cp, bp)
if val >= cur:
cur = val
else:
side[r][a], side[r][b] = side[r][b], side[r][a]
return cur
print("worst case found by hill climbing (5 restarts each):")
for n in (4, 5, 6):
best = max(climb(n, 20000) for _ in range(5))
print(" n = %d: %2d proposals, bound n^2 - n + 1 = %2d"
% (n, best, n * n - n + 1))唯一数据源与引用
范雅福(Fan, Y.). (2026). 《稳定匹配盖尔沙普利算法、买手客户达人品牌摄影师档期的无私奔配对母典》第 2 章「延迟接受:只暂留、不拍板的算法为何必然收敛」(版本 1.0.0). 5D Library. DOI 待发布
DOI 待发布 · 专著页正式发布后上线(本站暂无专著页) · 5DL-B-299 · v1.0.0 · CC-BY-NC-ND-4.0
BibTeX
@book{fan2026299,
author = {Fan, Yafu},
title = {Gale-Shapley Stable Matching: Pairings without Blocking Pairs for Buyers and Clients, Creators and Brands, Photographers and Slots},
year = {2026},
publisher = {5D Library},
edition = {1.0.0},
note = {DOI pending}
}