关于「东西方原典考辨:《周礼》的媒氏与盖尔与沙普利 1962」,《稳定匹配与无私奔配对》给出的定量结论是什么?

结论:《周礼·地官·媒氏》描述了一个集中的配对机构:登记、统一会期、照看落空者,并在会期内「奔者不禁」。它说对了集中与统一时间点的重要,也照看了第五、六章所说的那批无论用哪种稳定算法都会落空的人;它说错的是强制与处罚,并且只组织相会、不规定怎样配。p71 把「奔者不禁」写成动力过程:放任私奔对一个接一个落实,1,000 个市场全部到达稳定,但随机顺序平均要拆散 57.37 次婚约,最长 1348 次。盖尔与沙普利 1962 年的两条具体说法经 p72 核对成立:分身法与名额算法在 500 个市场里结果一致;室友问题的原文例子没有稳定配对。下一章把全书落到一张周度配对单和一份预注册检验方案上。

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

English version

对照数据表

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

本书其他章节结论