关于「先到先得与评分优先:私奔对从哪里来」,《稳定匹配与无私奔配对》给出的定量结论是什么?

结论:第一章在示意扫描中发现口味越一致,先到先得越糟,平均私奔对从 4.14 个升到 14.12 个;评分优先只在所有买手看法完全一致时才稳定;罗斯对英国八个地区的比较单看计数,单侧费希尔检验 p 值为 0.2143,须与定理和实验复现一起才站得住。

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

English version

对照数据表

下表数字由本章 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.004.14 0.968 4.11 0.966 0.00 0.000
0.508.06 1.000 3.62 0.946 0.00 0.000
0.8012.38 1.000 1.62 0.779 0.00 0.000
0.9513.63 1.000 0.45 0.350 0.00 0.000
1.0014.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 (w1); 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}
}

本书其他章节结论