关于「短名单、平局与猜出来的偏好」,《稳定匹配与无私奔配对》给出的定量结论是什么?
结论:第六章处理不完整名单与平局,并说明猜出来的偏好配不出稳定的表:噪声标准差仅 0.05 时已有 0.790 的市场留下私奔对。
数据口径:书中的人物、档期与偏好均为示意;全部计算由书中程序生成;本书是非个人化经营建议,只使用当事人明示提供的偏好,不做未经同意的画像,配对结果只是建议,双方都可以拒绝。 第一章在示意扫描中发现口味越一致,先到先得越糟,平均私奔对从 4.14 个升到 14.12 个;评分优先只在所有买手看法完全一致时才稳定;罗斯对英国八个地区的比较单看计数,单侧费希尔检验 p 值为 0.2143,须与定理和实验复现一起才站得住。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 0.05, 0.790
| sigma | blocking pairs markets with clients with a | |
| | per market any blocking different partner | |
| 0.00 | | 0.00 0.000 0.000 |
| 0.05 | | 1.60 0.790 0.375 |
| 0.10 | | 2.86 0.928 0.499 |
| 0.20 | | 5.86 0.987 0.648 |
| 0.40 | | 10.38 0.997 0.760 |
| 0.80 | | 15.25 1.000 0.838 |
| a guess with noise of 0.1 on a 0-1 scale already leaves most | |
| markets with someone who would rather elope. |
查看完整验算程序
# Chapter 6. p63: stable for guessed rankings is not stable for real ones.
# Model: 10 clients and 10 buyers with true values drawn uniformly
# (fixed seed, 1,000 illustrative markets per row). An operator who
# does not ask, and instead guesses each value as the true value plus
# Gaussian noise of standard deviation sigma, runs DA on the guesses.
# We count blocking pairs judged by the TRUE rankings, and the share of
# clients whose partner differs from DA on the stated rankings. This is
# the arithmetic behind the book's rule: match only on rankings that
# the parties stated themselves.
import math
import random
N, MARKETS = 10, 1000
rng = random.Random(20261113)
def order(vals):
return [sorted(range(N), key=lambda j, v=row: -v[j]) for row in vals]
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("sigma | blocking pairs markets with clients with a")
print(" | per market any blocking different partner")
for sigma in (0.0, 0.05, 0.1, 0.2, 0.4, 0.8):
bl, anyb, moved = [], 0, []
for _ in range(MARKETS):
cv = [[rng.random() for _ in range(N)] for _ in range(N)]
bv = [[rng.random() for _ in range(N)] for _ in range(N)]
cp, bp = order(cv), order(bv)
gc = order([[x + rng.gauss(0, sigma) for x in r] for r in cv])
gb = order([[x + rng.gauss(0, sigma) for x in r] for r in bv])
truth = deferred(cp, bp)
guess = deferred(gc, gb)
k = blocking(guess, cp, bp)
bl.append(k)
anyb += int(k > 0)
moved.append(len([c for c in range(N) if guess[c] != truth[c]]))
print("%5.2f | %8.2f %8.3f %8.3f"
% (sigma, math.fsum(bl) / MARKETS, anyb / MARKETS,
math.fsum(moved) / MARKETS / N))
print("a guess with noise of 0.1 on a 0-1 scale already leaves most")
print("markets with someone who would rather elope.")唯一数据源与引用
范雅福(Fan, Y.). (2026). 《稳定匹配盖尔沙普利算法、买手客户达人品牌摄影师档期的无私奔配对母典》第 6 章「短名单、平局与猜出来的偏好」(版本 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}
}