关于「提议方最优:稳定配对的格与「谁先开口」的价值」,《稳定匹配与无私奔配对》给出的定量结论是什么?
结论:第三章穷举全部稳定配对,说明提议方最优即接受方最差,而一边只多一个人时,先开口的价值从 6.02 个名次缩到 0.62 个。
数据口径:书中的人物、档期与偏好均为示意;全部计算由书中程序生成;本书是非个人化经营建议,只使用当事人明示提供的偏好,不做未经同意的画像,配对结果只是建议,双方都可以拒绝。 第一章在示意扫描中发现口味越一致,先到先得越糟,平均私奔对从 4.14 个升到 14.12 个;评分优先只在所有买手看法完全一致时才稳定;罗斯对英国八个地区的比较单看计数,单侧费希尔检验 p 值为 0.2143,须与定理和实验复现一起才站得住。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 0.62, 6.02
clients buyers | clients propose | buyers propose | gap in
| client buyer | client buyer | client rank
40 39 | 9.59 3.86 | 11.21 3.19 | 1.62
40 40 | 3.99 9.80 | 10.01 3.88 | 6.02
40 41 | 3.18 11.46 | 3.80 9.87 | 0.62
balanced: proposing is worth several ranks; unbalanced: the short
side does well and the long side does poorly whoever proposes.查看完整验算程序
# Chapter 3. p33: one extra buyer erases the advantage of proposing.
# Model: 40 clients and 39, 40 or 41 buyers, uniformly random complete
# rankings, fixed seed, 400 illustrative markets per row. Each market is
# solved with clients proposing and with buyers proposing; the program
# reports the mean rank of the partner for matched clients and matched
# buyers. Question (Ashlagi, Kanoria and Leshno 2017): does the side
# that proposes still matter once the two sides differ by one agent?
import math
import random
rng = random.Random(20261114)
C, REPS = 40, 400
def deferred(pp, rp):
rank = [{p: i for i, p in enumerate(v)} for v in rp]
nxt, held = [0] * len(pp), [None] * len(rp)
free = list(range(len(pp)))
while free:
p = free.pop()
if nxt[p] >= len(pp[p]):
continue
r = pp[p][nxt[p]]
nxt[p] += 1
cur = held[r]
if cur is None:
held[r] = p
elif rank[r][p] < rank[r][cur]:
held[r] = p
free.append(cur)
else:
free.append(p)
return {p: r for r, p in enumerate(held) if p is not None}
print("clients buyers | clients propose | buyers propose | gap in")
print(" | client buyer | client buyer | client rank")
for nb in (39, 40, 41):
acc = [[], [], [], []]
for _ in range(REPS):
cp = [rng.sample(range(nb), nb) for _ in range(C)]
bp = [rng.sample(range(C), C) for _ in range(nb)]
mc = deferred(cp, bp)
mb = {c: b for b, c in deferred(bp, cp).items()}
for k, m in enumerate((mc, mb)):
rc = [cp[c].index(b) + 1 for c, b in m.items()]
rb = [bp[b].index(c) + 1 for c, b in m.items()]
acc[2 * k].append(math.fsum(rc) / len(rc))
acc[2 * k + 1].append(math.fsum(rb) / len(rb))
a = [math.fsum(v) / REPS for v in acc]
print("%7d %6d | %6.2f %6.2f | %6.2f %6.2f | %6.2f"
% (C, nb, a[0], a[1], a[2], a[3], a[2] - a[0]))
print("balanced: proposing is worth several ranks; unbalanced: the short")
print("side does well and the long side does poorly whoever proposes.")唯一数据源与引用
范雅福(Fan, Y.). (2026). 《稳定匹配盖尔沙普利算法、买手客户达人品牌摄影师档期的无私奔配对母典》第 3 章「提议方最优:稳定配对的格与「谁先开口」的价值」(版本 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}
}