关于「东西方原典考辨:《周礼》的媒氏与盖尔与沙普利 1962」,《稳定匹配与无私奔配对》给出的定量结论是什么?
结论:《周礼·地官·媒氏》描述了一个集中的配对机构:登记、统一会期、照看落空者,并在会期内「奔者不禁」。它说对了集中与统一时间点的重要,也照看了第五、六章所说的那批无论用哪种稳定算法都会落空的人;它说错的是强制与处罚,并且只组织相会、不规定怎样配。p71 把「奔者不禁」写成动力过程:放任私奔对一个接一个落实,1,000 个市场全部到达稳定,但随机顺序平均要拆散 57.37 次婚约,最长 1348 次。盖尔与沙普利 1962 年的两条具体说法经 p72 核对成立:分身法与名额算法在 500 个市场里结果一致;室友问题的原文例子没有稳定配对。下一章把全书落到一张周度配对单和一份预注册检验方案上。
数据口径:书中的人物、档期与偏好均为示意;全部计算由书中程序生成;本书是非个人化经营建议,只使用当事人明示提供的偏好,不做未经同意的画像,配对结果只是建议,双方都可以拒绝。 第一章在示意扫描中发现口味越一致,先到先得越糟,平均私奔对从 4.14 个升到 14.12 个;评分优先只在所有买手看法完全一致时才稳定;罗斯对英国八个地区的比较单看计数,单侧费希尔检验 p 值为 0.2143,须与定理和实验复现一起才站得住。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 1000, 1348, 57.37
start: a random arranged pairing of 8 and 8, 1000 markets rule stable mean steps median max steps cycles ends at DA random 1000 57.37 37 1348 0 0.530 fixed 1000 12.71 12 44 0 0.879 each step breaks one existing pairing; letting blocking pairs act does end in stability, after a chain of broken promises that DA, run before anything is announced, never makes.
查看完整验算程序
# Chapter 7. p71: "those who elope are not stopped" as a dynamic.
# Model: 8 and 8 agents with uniformly random rankings (fixed seed,
# 1,000 illustrative markets). Start from a pairing arranged at random
# without asking anyone, then let one blocking pair at a time leave
# their partners and pair up (their old partners become single).
# Random order: pick a blocking pair at random (Roth and Vande Vate
# 1990 prove this reaches a stable matching with probability one).
# Fixed order: always the first blocking pair in a fixed scan; such
# deterministic orders can cycle for ever (Knuth 1976). From a full
# pairing to a full pairing every step forms one pair and breaks one, so
# steps = broken pairings. We report steps, cycles detected, and how
# often the end point is the left-proposing DA outcome.
import math
import random
N, MARKETS, LIMIT = 8, 1000, 2000
rng = random.Random(20261113)
def blocking_pairs(m, cp, bp):
# m: 左侧 -> 右侧(或 None);返回所有私奔对
owner = [None] * N
for a, b in enumerate(m):
if b is not None:
owner[b] = a
out = []
for a in range(N):
cut = cp[a].index(m[a]) if m[a] is not None else N
for b in cp[a][:cut]:
o = owner[b]
if o is None or bp[b].index(a) < bp[b].index(o):
out.append((a, b))
return out
def elope(m, a, b):
m = list(m)
for x in range(N):
if m[x] == b:
m[x] = None
m[a] = b
return tuple(m)
def deferred(cp, bp):
rank = [{a: i for i, a in enumerate(v)} for v in bp]
nxt, held, free = [0] * N, [None] * N, list(range(N))
while free:
a = free.pop()
b = cp[a][nxt[a]]
nxt[a] += 1
cur = held[b]
if cur is None:
held[b] = a
elif rank[b][a] < rank[b][cur]:
held[b] = a
free.append(cur)
else:
free.append(a)
m = [None] * N
for b, a in enumerate(held):
m[a] = b
return tuple(m)
res = {"random": ([], 0, 0), "fixed": ([], 0, 0)}
for _ in range(MARKETS):
cp = [rng.sample(range(N), N) for _ in range(N)]
bp = [rng.sample(range(N), N) for _ in range(N)]
da = deferred(cp, bp)
start = list(range(N))
rng.shuffle(start)
for rule in ("random", "fixed"):
m, steps, seen, cyc = tuple(start), 0, {tuple(start)}, False
while steps < LIMIT:
bl = blocking_pairs(m, cp, bp)
if not bl:
break
a, b = rng.choice(bl) if rule == "random" else bl[0]
m = elope(m, a, b)
steps += 1
if rule == "fixed":
if m in seen:
cyc = True
break
seen.add(m)
st, cy, at_da = res[rule]
if not cyc and steps < LIMIT:
st.append(steps)
res[rule] = (st, cy + int(cyc), at_da + int(m == da))
print("start: a random arranged pairing of %d and %d, %d markets"
% (N, N, MARKETS))
print("rule stable mean steps median max steps cycles ends at DA")
for rule in ("random", "fixed"):
st, cy, at_da = res[rule]
st.sort()
print("%-7s %6d %10.2f %6d %9d %6d %10.3f"
% (rule, len(st), math.fsum(st) / len(st), st[len(st) // 2],
st[-1], cy, at_da / MARKETS))
print("each step breaks one existing pairing; letting blocking pairs act")
print("does end in stability, after a chain of broken promises that DA,")
print("run before anything is announced, never makes.")唯一数据源与引用
范雅福(Fan, Y.). (2026). 《稳定匹配盖尔沙普利算法、买手客户达人品牌摄影师档期的无私奔配对母典》第 7 章「东西方原典考辨:《周礼》的媒氏与盖尔与沙普利 1962」(版本 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}
}