关于「多对一:摄影师档期、医院与住院医」,《稳定匹配与无私奔配对》给出的定量结论是什么?

结论:第五章把配对推广到摄影师档期这样的多对一,检验偏远医院定理,并算出稳定的代价:0.115 的周里只求塞满可多排约 1.04 场。

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

English version

对照数据表

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

weeks 400; stable assignments per week: mean 1.040, max 2
weeks with more than one stable assignment16
violations of the same-fill and same-unplaced claims0
weeks where a stable rule places fewer shoots than the largest
feasible assignment46 (0.115), shortfall 1.04 shoots on average
查看完整验算程序
# Chapter 5. p52: who gets a slot does not depend on which stable rule.
# Model: 3 photographers with 2, 1 and 1 slots; 6 shoots. Each shoot
# lists 1 to 3 acceptable photographers in random order; a photographer
# accepts a shoot with probability 0.8 and ranks the accepted ones at
# random (fixed seed, 400 illustrative weeks). Every assignment of
# shoots to a photographer or to nobody (4^6 = 4,096 per week) is
# checked for capacity, mutual acceptability and blocking pairs.
# Claims checked (the "rural hospitals" theorem, Roth 1986; see Roth
# and Sotomayor 1990): every stable assignment fills
# each photographer with the same number of shoots and leaves the same
# shoots unplaced; an under-filled photographer gets the same shoots in
# all of them. Also: how often does stability cost placements, compared
# with the largest feasible assignment that ignores rankings?
import itertools
import math
import random

CAP = [2, 1, 1]
P, S, WEEKS = 3, 6, 400
rng = random.Random(20261113)


def week():
    sp = [rng.sample(range(P), rng.randint(1, 3)) for _ in range(S)]
    pp = []
    for p in range(P):
        acc = [s for s in range(S) if p in sp[s] and rng.random() < 0.8]
        rng.shuffle(acc)
        pp.append(acc)
    return sp, pp


def feasible(a, sp, pp):
    for p in range(P):
        if a.count(p) > CAP[p]:
            return False
    return all(p is None or (p in sp[s] and s in pp[p])
               for s, p in enumerate(a))


def stable(a, sp, pp):
    for s in range(S):
        lst = sp[s]
        cut = lst.index(a[s]) if a[s] is not None else len(lst)
        for p in lst[:cut]:
            if s not in pp[p]:
                continue
            held = [t for t in range(S) if a[t] == p]
            if len(held) < CAP[p]:
                return False
            if pp[p].index(s) < max(pp[p].index(t) for t in held):
                return False
    return True


n_stable, viol, cost, gap = [], 0, 0, []
for _ in range(WEEKS):
    sp, pp = week()
    feas = [a for a in itertools.product([None, 0, 1, 2], repeat=S)
            if feasible(a, sp, pp)]
    st = [a for a in feas if stable(a, sp, pp)]
    n_stable.append(len(st))
    fills = {tuple(a.count(p) for p in range(P)) for a in st}
    unplaced = {tuple(s for s in range(S) if a[s] is None) for a in st}
    if len(fills) != 1 or len(unplaced) != 1:
        viol += 1
    for p in range(P):
        under = [a for a in st if a.count(p) < CAP[p]]
        if under and len({tuple(s for s in range(S) if a[s] == p)
                          for a in st}) != 1:
            viol += 1
    placed_st = S - len(next(iter(unplaced)))
    best = max(S - a.count(None) for a in feas)
    if best > placed_st:
        cost += 1
        gap.append(best - placed_st)
print("weeks %d; stable assignments per week: mean %.3f, max %d"
      % (WEEKS, math.fsum(n_stable) / WEEKS, max(n_stable)))
print("weeks with more than one stable assignment: %d"
      % len([x for x in n_stable if x > 1]))
print("violations of the same-fill and same-unplaced claims: %d" % viol)
print("weeks where a stable rule places fewer shoots than the largest")
print("feasible assignment: %d (%.3f), shortfall %.2f shoots on average"
      % (cost, cost / WEEKS, math.fsum(gap) / len(gap)))

唯一数据源与引用

范雅福(Fan, Y.). (2026). 《稳定匹配盖尔沙普利算法、买手客户达人品牌摄影师档期的无私奔配对母典》第 5 章「多对一:摄影师档期、医院与住院医」(版本 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}
}

本书其他章节结论