关于「延迟接受:只暂留、不拍板的算法为何必然收敛」,《稳定匹配与无私奔配对》给出的定量结论是什么?

结论:延迟接受把「先答应」改成「先暂留」:提议者沿着自己的名单往下走,接受方只把目前最好的一份留在手里,直到没有人再被退回。两条单调性,提议者只往下、接受方只往上换,足以证明算法一定会停、停下时一定没有私奔对。示意运行 p21 用 10 次提议得到一张稳定的表,其中 K4 落在自己的末位,却找不到任何愿意与他私奔的品牌。p22 显示,随机市场里平均提议次数低于威尔逊的上界,200 对时只占 n 的平方的 0.029;最坏情形 n 的平方减 n 加 1 确实可以达到,但需要极其特殊的偏好。处理顺序不影响结果,提议方向则影响很大,这是下一章的主题。

数据口径:书中的人物、档期与偏好均为示意;全部计算由书中程序生成;本书是非个人化经营建议,只使用当事人明示提供的偏好,不做未经同意的画像,配对结果只是建议,双方都可以拒绝。 第一章在示意扫描中发现口味越一致,先到先得越糟,平均私奔对从 4.14 个升到 14.12 个;评分优先只在所有买手看法完全一致时才稳定;罗斯对英国八个地区的比较单看计数,单侧费希尔检验 p 值为 0.2143,须与定理和实验复现一起才站得住。

English version

对照数据表

下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 0.029, 10, 200, 21

n markets mean proposals n*H_n mean/n^2 max seen
102000 24.1 29.3 0.241 48
201000 63.0 72.0 0.157 138
50400 209.0 225.0 0.084 421
100200 495.0 518.7 0.050 805
20060 1153.2 1175.6 0.029 1663
worst case found by hill climbing (5 restarts each):
n4: 13 proposals, bound n^2 - n + 1 = 13
n5: 21 proposals, bound n^2 - n + 1 = 21
n6: 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}
}

本书其他章节结论