关于「多对一:摄影师档期、医院与住院医」,《稳定匹配与无私奔配对》给出的定量结论是什么?
结论:第五章把配对推广到摄影师档期这样的多对一,检验偏远医院定理,并算出稳定的代价:0.115 的周里只求塞满可多排约 1.04 场。
数据口径:书中的人物、档期与偏好均为示意;全部计算由书中程序生成;本书是非个人化经营建议,只使用当事人明示提供的偏好,不做未经同意的画像,配对结果只是建议,双方都可以拒绝。 第一章在示意扫描中发现口味越一致,先到先得越糟,平均私奔对从 4.14 个升到 14.12 个;评分优先只在所有买手看法完全一致时才稳定;罗斯对英国八个地区的比较单看计数,单侧费希尔检验 p 值为 0.2143,须与定理和实验复现一起才站得住。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 0.115, 1.04
| weeks 400; stable assignments per week: mean 1.040, max 2 | |
| weeks with more than one stable assignment | 16 |
| violations of the same-fill and same-unplaced claims | 0 |
| weeks where a stable rule places fewer shoots than the largest | |
| feasible assignment | 46 (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}
}