关于「先到先得与评分优先:私奔对从哪里来」,《稳定匹配与无私奔配对》给出的定量结论是什么?
结论:第一章在示意扫描中发现口味越一致,先到先得越糟,平均私奔对从 4.14 个升到 14.12 个;评分优先只在所有买手看法完全一致时才稳定;罗斯对英国八个地区的比较单看计数,单侧费希尔检验 p 值为 0.2143,须与定理和实验复现一起才站得住。
数据口径:书中的人物、档期与偏好均为示意;全部计算由书中程序生成;本书是非个人化经营建议,只使用当事人明示提供的偏好,不做未经同意的画像,配对结果只是建议,双方都可以拒绝。 第一章在示意扫描中发现口味越一致,先到先得越糟,平均私奔对从 4.14 个升到 14.12 个;评分优先只在所有买手看法完全一致时才稳定;罗斯对英国八个地区的比较单看计数,单侧费希尔检验 p 值为 0.2143,须与定理和实验复现一起才站得住。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 14.12, 4.14
| w = weight of shared taste; mean blocking pairs per market | |
| and share of markets with at least one, 2000 markets of 8x8 | |
| w first-come score-first deferred acc. | |
| 0.00 | 4.14 0.968 4.11 0.966 0.00 0.000 |
| 0.50 | 8.06 1.000 3.62 0.946 0.00 0.000 |
| 0.80 | 12.38 1.000 1.62 0.779 0.00 0.000 |
| 0.95 | 13.63 1.000 0.45 0.350 0.00 0.000 |
| 1.00 | 14.12 1.000 0.00 0.000 0.00 0.000 |
| score-first is stable only when every buyer ranks clients by | |
| the same score (w | 1); first-come is unstable at every w. |
查看完整验算程序
# Chapter 1. p12: blocking pairs of first-come and score-first, swept.
# Model: 8 clients and 8 buyers. A client's value of a buyer is
# w * (buyer's common appeal) + (1 - w) * (idiosyncratic taste); a
# buyer's value of a client is w * (client's common score) + (1 - w) *
# (idiosyncratic fit). All draws uniform on [0, 1], fixed seed; w = 0
# means tastes are private, w = 1 means everybody agrees. First-come:
# clients arrive in random order and take the best free buyer.
# Score-first: clients are served in order of their common score.
# Deferred acceptance: clients propose. 2,000 illustrative markets per w.
import math
import random
N, MARKETS = 8, 2000
rng = random.Random(20261113)
def market(w):
qa = [rng.random() for _ in range(N)] # 买手的公共吸引力
qs = [rng.random() for _ in range(N)] # 客户的公共评分
cv = [[w * qa[b] + (1 - w) * rng.random() for b in range(N)]
for _ in range(N)]
bv = [[w * qs[c] + (1 - w) * rng.random() for c in range(N)]
for _ in range(N)]
cp = [sorted(range(N), key=lambda b, r=row: -r[b]) for row in cv]
bp = [sorted(range(N), key=lambda c, r=row: -r[c]) for row in bv]
return cp, bp, qs
def serial(order, cp):
taken, m = set(), [None] * N
for c in order:
for b in cp[c]:
if b not in taken:
m[c] = b
taken.add(b)
break
return m
def deferred(cp, bp):
rank = [{c: i for i, c in enumerate(v)} for v in bp]
nxt, held, free = [0] * N, [None] * N, list(range(N))
while free:
c = free.pop()
b = cp[c][nxt[c]]
nxt[c] += 1
cur = held[b]
if cur is None:
held[b] = c
elif rank[b][c] < rank[b][cur]:
held[b] = c
free.append(cur)
else:
free.append(c)
m = [None] * N
for b, c in enumerate(held):
m[c] = b
return m
def blocking(m, cp, bp):
owner = [None] * N
for c, b in enumerate(m):
owner[b] = c
k = 0
for c in range(N):
for b in cp[c][:cp[c].index(m[c])]:
if bp[b].index(c) < bp[b].index(owner[b]):
k += 1
return k
print("w = weight of shared taste; mean blocking pairs per market")
print("and share of markets with at least one, %d markets of %dx%d"
% (MARKETS, N, N))
print(" w first-come score-first deferred acc.")
for w in (0.0, 0.5, 0.8, 0.95, 1.0):
res = {"fc": [], "sf": [], "da": []}
for _ in range(MARKETS):
cp, bp, qs = market(w)
arrive = list(range(N))
rng.shuffle(arrive)
res["fc"].append(blocking(serial(arrive, cp), cp, bp))
order = sorted(range(N), key=lambda c: -qs[c])
res["sf"].append(blocking(serial(order, cp), cp, bp))
res["da"].append(blocking(deferred(cp, bp), cp, bp))
cells = []
for key in ("fc", "sf", "da"):
v = res[key]
mean = math.fsum(v) / len(v)
share = len([x for x in v if x > 0]) / len(v)
cells.append("%5.2f %5.3f" % (mean, share))
print("%5.2f %s %s %s" % (w, cells[0], cells[1], cells[2]))
print("score-first is stable only when every buyer ranks clients by")
print("the same score (w = 1); first-come is unstable at every w.")唯一数据源与引用
范雅福(Fan, Y.). (2026). 《稳定匹配盖尔沙普利算法、买手客户达人品牌摄影师档期的无私奔配对母典》第 1 章「先到先得与评分优先:私奔对从哪里来」(版本 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}
}