关于「短名单、平局与猜出来的偏好」,《稳定匹配与无私奔配对》给出的定量结论是什么?

结论:第六章处理不完整名单与平局,并说明猜出来的偏好配不出稳定的表:噪声标准差仅 0.05 时已有 0.790 的市场留下私奔对。

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

English version

对照数据表

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

本书其他章节结论