5D Library › 算法博弈论、布雷斯悖论与流量分配的无秩序代价 · English

第六章 稳定匹配:延迟接受、提前签约与说真话

没有价格的市场

前几章的「市场」都有一个共同点:每个人选的是一条路、一个赛道或一个物品,而被选的一方不会拒绝。许多重要的市场不是这样。医院挑医生,医生也挑医院;学校录取学生,学生也选学校;品牌找合作的创作者,创作者也选品牌。这类双边匹配市场里,交易不能靠价格单方面完成,双方都必须愿意。

这类市场常见三种失败。第一是不稳定:已经配好的两对中,有一个人与另一对中的人都更愿意彼此合作,于是双方毁约另配,称为一个阻挡对。第二是提前签约(unraveling):为了抢在别人之前锁定好的对象,各方越来越早地发出要约,在信息很少的时候就做出决定。第三是拥堵:要约太多、决定的时间太短,市场来不及处理。

证据

医生市场的提前签约与集中匹配。 罗斯 1984 年研究了美国医学实习生市场的历史:20 世纪 40 年代,医院之间争相提前录取,要约有时在实习开始前两年发出;1950 年代初建立了集中的匹配程序,罗斯证明它的算法等价于以医院为提议方的盖尔—沙普利算法,产生稳定匹配,这可以解释为什么它能长期维持 (Roth 1984)。罗斯与邢 1994 年比较了许多市场中交易时间提前的现象,讨论了导致提前签约的条件与用来对付它的制度 (Roth and Xing 1994)。罗斯与佩兰森 1999 年为美国全国住院医师匹配项目重新设计了算法,改为以申请人为提议方,并处理了夫妻共同申请等实际约束 (Roth and Peranson 1999)。尼德勒与罗斯 2003 年研究了胃肠病学专科:它退出集中匹配后,录取提前,医生在医院之间的流动减少了 (Niederle and Roth 2003)。

证据

2012 年诺贝尔经济学奖。 2012 年诺贝尔经济学奖授予罗斯与沙普利,表彰「稳定分配理论与市场设计实践」;评奖委员会指出,罗斯参与的医生匹配与学校录取的重新设计都建立在盖尔—沙普利算法的基础上 (Economic Sciences Prize Committee of the Royal Swedish Academy of Sciences 2012)。盖尔已于 2008 年去世。

延迟接受算法

推导

提议方(例如医生)与接受方(例如医院)各有 nn 人,每人对另一方的全部成员排出严格的偏好顺序。

延迟接受算法(盖尔与沙普利 1962):每个尚未被暂时接受的提议者,向自己名单上还没有拒绝过他的最喜欢的接受者提出申请;每个接受者在所有向他申请的人中,只「暂时」留下最喜欢的一个,拒绝其余的人;被拒绝的人继续向名单上的下一位申请。当没有人再被拒绝时,暂时的接受变成最终的匹配 (Gale and Shapley 1962)。

接受是「延迟」的:接受者手里的人随时可能被更好的申请者替换,所以他不必在信息很少时做最终决定。

证据

算法的性质。 盖尔与沙普利证明,这一算法总在有限步内结束,结果总是稳定的(没有阻挡对),并且对提议方而言,它是所有稳定匹配中最好的:每个提议者得到的伴侣,不比他在任何其他稳定匹配中能得到的差 (Gale and Shapley 1962)。同一个匹配对接受方而言是所有稳定匹配中最差的;提议者申请的先后次序不影响结果 (Economic Sciences Prize Committee of the Royal Swedish Academy of Sciences 2012)。

推导

# Deferred acceptance (Gale & Shapley 1962) and the set of all stable matchings.
# Proposers and receivers each rank everyone on the other side. Checks on 500 random 6 x
# 6 markets: the result is stable; every proposer gets her best partner among ALL stable
# matchings; every receiver gets his worst; and the order in which proposers move does
# not matter.
import itertools, random
rng = random.Random(12)

def deferred_acceptance(P, R, order=None):
    """P[i] = proposer i's ranking of receivers, R[j] = receiver j's ranking of proposers.
    Returns match[i] = receiver matched to proposer i."""
    n = len(P)
    rank = [{p: k for k, p in enumerate(R[j])} for j in range(n)]
    nxt, held, free = [0] * n, {}, list(order if order else range(n))
    while free:
        i = free.pop(0); j = P[i][nxt[i]]; nxt[i] += 1
        if j not in held: held[j] = i
        elif rank[j][i] < rank[j][held[j]]: free.append(held[j]); held[j] = i
        else: free.append(i)
    match = [None] * n
    for j, i in held.items(): match[i] = j
    return match

def blocking_pairs(match, P, R):
    n = len(P); partner = {j: i for i, j in enumerate(match)}
    return [(i, j) for i in range(n) for j in range(n) if match[i] != j
            and P[i].index(j) < P[i].index(match[i])
            and R[j].index(i) < R[j].index(partner[j])]

def all_stable(P, R):
    return [list(m) for m in itertools.permutations(range(len(P)))
            if not blocking_pairs(m, P, R)]

def market(n):
    P = [rng.sample(range(n), n) for _ in range(n)]
    R = [rng.sample(range(n), n) for _ in range(n)]
    return P, R

ok = {"stable": 0, "proposer-best": 0, "receiver-worst": 0, "order-free": 0}
counts = {}
for _ in range(500):
    P, R = market(6)
    m = deferred_acceptance(P, R)
    S = all_stable(P, R)
    counts[len(S)] = counts.get(len(S), 0) + 1
    ok["stable"] += not blocking_pairs(m, P, R)
    ok["proposer-best"] += all(P[i].index(m[i]) == min(P[i].index(s[i]) for s in S)
                               for i in range(6))
    inv = lambda mm: {j: i for i, j in enumerate(mm)}
    ok["receiver-worst"] += all(R[j].index(inv(m)[j])
                                == max(R[j].index(inv(s)[j]) for s in S)
                                for j in range(6))
    ok["order-free"] += all(deferred_acceptance(P, R, rng.sample(range(6), 6)) == m
                            for _ in range(5))
print("500 random 6 x 6 markets:\n   " + ", ".join(f"{k} {v}/500" for k, v in ok.items()))
print("number of stable matchings per market: "
      + ", ".join(f"{k}: {counts[k]}" for k in sorted(counts)))
# A small market with three stable matchings: which side proposes decides who is
# favoured.
P = [[0, 1, 2], [1, 2, 0], [2, 0, 1]]           # proposer i likes receiver i best
R = [[1, 2, 0], [2, 0, 1], [0, 1, 2]]           # receiver j likes proposer j + 1 best
mp = deferred_acceptance(P, R); mr = deferred_acceptance(R, P)
mr = [mr.index(i) for i in range(3)]              # rewrite as proposer i -> receiver
for lab, m in (("proposers propose", mp), ("receivers propose", mr)):
    print(f"3 x 3, {lab}: {m}; ranks: proposers "
          f"{[P[i].index(m[i]) + 1 for i in range(3)]}, receivers "
          f"{[R[m[i]].index(i) + 1 for i in range(3)]}")
print(f"   all stable matchings (proposer i -> receiver): {all_stable(P, R)}")
# 500 random 6 x 6 markets:
#    stable 500/500, proposer-best 500/500, receiver-worst 500/500, order-free 500/500
# number of stable matchings per market: 1: 183, 2: 204, 3: 78, 4: 25, 5: 7, 6: 2, 8: 1
# 3 x 3, proposers propose: [0, 1, 2]; ranks: proposers [1, 1, 1], receivers [3, 3, 3]
# 3 x 3, receivers propose: [2, 0, 1]; ranks: proposers [3, 3, 3], receivers [1, 1, 1]
#    all stable matchings (proposer i -> receiver): [[0, 1, 2], [1, 2, 0], [2, 0, 1]]

程序在 500 个随机的 6 × 6 市场上逐一检查了这些性质:结果全部稳定;每个提议者得到的都是他在全部稳定匹配(用穷举 720 种配对找出)中最好的伴侣;每个接受者得到的都是他最差的;随机打乱申请次序 5 次,结果都不变。稳定匹配常常不止一个:500 个市场中只有 183 个是唯一的,204 个有两个,最多的一个市场有 8 个。

最后的 3 × 3 例子说明「谁提议」有多重要。提议者 ii 最喜欢接受者 ii,接受者 jj 最喜欢提议者 j+1j + 1。提议方提议时,每个提议者都得到第一志愿,每个接受者都得到最后一个志愿;接受方提议时恰好相反。两者之间还有第三个稳定匹配,每个人都得到第二志愿。三个都稳定,算法选哪一个,取决于规则让谁先说话。

谁能从说谎中获益

证据

提议方说真话是占优策略。 杜宾斯与弗里德曼 1981 年证明,在以男方为提议方的盖尔—沙普利算法中,任何一个男方或一群男方都不能通过谎报偏好使自己每个人都严格更好 (Dubins and Freedman 1981)。罗斯 1982 年证明了两个方向的结论:不存在任何一种总能产生稳定匹配、又使所有人如实报告都是占优策略的机制;但在产生某一方最优稳定匹配的机制中,如实报告对那一方的每个人都是占优策略 (Roth 1982)。盖尔与索托马约尔 1985 年证明,只要稳定匹配不止一个,就至少有一个接受者能通过谎报偏好(例如把一些提议者列为不可接受)得到更好的伴侣 (Gale and Sotomayor 1985)。

推导

# Who can gain by lying in proposer-side deferred acceptance? On random 4 x 4 markets each
# agent tries all 24 rankings while the others tell the truth. Proposers never gain
# (Dubins & Freedman 1981; Roth 1982); receivers sometimes do (Roth 1982; Gale &
# Sotomayor 1985). Also: can a PAIR of proposers both gain together?
import itertools, random
rng = random.Random(13)
N, MARKETS = 4, 300

def da(P, R):
    n = len(P); rank = [{p: k for k, p in enumerate(R[j])} for j in range(n)]
    nxt, held, free = [0] * n, {}, list(range(n))
    while free:
        i = free.pop(0); j = P[i][nxt[i]]; nxt[i] += 1
        if j not in held: held[j] = i
        elif rank[j][i] < rank[j][held[j]]: free.append(held[j]); held[j] = i
        else: free.append(i)
    m = [None] * n
    for j, i in held.items(): m[i] = j
    return m

LISTS = [list(p) for p in itertools.permutations(range(N))]
prop_gain = rec_gain = pair_gain = rec_markets = 0
example = None
for _ in range(MARKETS):
    P = [rng.sample(range(N), N) for _ in range(N)]
    R = [rng.sample(range(N), N) for _ in range(N)]
    m = da(P, R); partner = {j: i for i, j in enumerate(m)}
    for i in range(N):
        for L in LISTS:
            Q = [row[:] for row in P]; Q[i] = L
            prop_gain += P[i].index(da(Q, R)[i]) < P[i].index(m[i])
    found = False
    for j in range(N):
        for L in LISTS:
            S = [row[:] for row in R]; S[j] = L
            m2 = da(P, S); p2 = {jj: ii for ii, jj in enumerate(m2)}
            if R[j].index(p2[j]) < R[j].index(partner[j]):
                rec_gain += 1; found = True
                if example is None: example = (R[j], partner[j], L, p2[j])
    rec_markets += found
    for a, b in itertools.combinations(range(N), 2):
        for La, Lb in itertools.product(LISTS, repeat=2):
            Q = [row[:] for row in P]; Q[a] = La; Q[b] = Lb; m2 = da(Q, R)
            pair_gain += (P[a].index(m2[a]) < P[a].index(m[a]) and
                          P[b].index(m2[b]) < P[b].index(m[b]))
print(f"{MARKETS} random 4 x 4 markets, every unilateral misreport tried:")
print(f"   profitable lies by a proposer: {prop_gain}; by a receiver: {rec_gain}"
      f" (in {rec_markets} markets, {rec_markets / MARKETS:.0%})")
print(f"   joint lies by two proposers that make BOTH strictly better off: {pair_gain}")
true, part, lie, new = example
print(f"example: a receiver whose true ranking is {true} holds proposer {part}"
      " under truth;")
print(f"   reporting {lie} instead, he ends with proposer {new}, whom he truly prefers")
# 300 random 4 x 4 markets, every unilateral misreport tried:
#    profitable lies by a proposer: 0; by a receiver: 58 (in 12 markets, 4%)
#    joint lies by two proposers that make BOTH strictly better off: 0
# example: a receiver whose true ranking is [2, 3, 0, 1] holds proposer 0 under truth;
#    reporting [2, 3, 1, 0] instead, he ends with proposer 3, whom he truly prefers

在 300 个随机的 4 × 4 市场中,程序让每个人在其他人都说真话时尝试全部 24 种排序。提议者没有一次能通过谎报得到更好的伴侣;两个提议者联合谎报、使两人都严格更好的情形也一次都没有出现,与杜宾斯与弗里德曼的结论一致。接受者则不同:有 12 个市场(4%)中,某个接受者能通过谎报得到他真正更喜欢的提议者,共有 58 种这样的谎报。例子中的接受者真实偏好是 [2, 3, 0, 1],说真话时得到第三志愿 0;只把 0 和 1 对调,他就会在某一步拒绝原本会留下的申请者,引起一串新的申请,最终得到第二志愿 3。这里只允许重新排序;把人列为不可接受的操纵空间更大。

作者框架中「对提议方说真话是占优策略、对接受方不成立」核对无误。对规则设计者而言:希望哪一方放心如实填报,就让那一方提议。罗斯与佩兰森把住院医师匹配改为申请人提议,理由之一正在于此 (Roth and Peranson 1999)。

注

与第 27 本的关系。 第 27 本第三章的迈尔森—萨特思韦特定理说明,双边都有私人信息时,有效、自愿参与、激励相容与预算平衡不可兼得;罗斯 1982 年的结论是匹配市场中的类似限制:稳定与「双方都说真话」不可兼得。

注

用于品牌与创作者的撮合时。 把「医院与医生」换成「品牌与创作者」,延迟接受算法可以作为一个思考工具:检查现有的合作配对中有没有阻挡对(第八章核查表第四步)。但真实的撮合市场与教科书模型不同:一个品牌可以同时与多个创作者合作,价格与条款可以谈判,偏好会变化。这些条件下算法的性质需要另行分析;本书不对任何真实平台提出设计建议。

假说 · 尚未验证

阻挡对毁约假说(尚未确立)。作者推测,处在阻挡对中的合作配对比其他配对更早终止合作。可以检验的预测是:在事先独立收集了双方偏好排序的撮合数据中,这类配对的合作持续时间显著更短;如果没有差别,这一假说就被推翻。

本章小结

延迟接受算法总能找到稳定匹配,对提议方最好、对接受方最差,且与申请次序无关;稳定匹配常不止一个,选哪一个取决于谁提议。提议方如实报告是占优策略,接受方不是。集中匹配曾帮助医生市场停止提前签约。下一章转向古代治水文献。

参考文献

Dubins, Lester E., and David A. Freedman. 1981. “Machiavelli and the Gale–Shapley Algorithm.” The American Mathematical Monthly 88 (7): 485–94.
Economic Sciences Prize Committee of the Royal Swedish Academy of Sciences. 2012. Stable Matching: Theory, Evidence, and Practical Design. Scientific Background on the Sveriges Riksbank Prize in Economic Sciences in Memory of Alfred Nobel 2012. The Royal Swedish Academy of Sciences, Stockholm.
Gale, David, and Lloyd S. Shapley. 1962. “College Admissions and the Stability of Marriage.” The American Mathematical Monthly 69 (1): 9–15. https://doi.org/10.2307/2312726.
Gale, David, and Marilda Sotomayor. 1985. “Ms. Machiavelli and the Stable Matching Problem.” The American Mathematical Monthly 92 (4): 261–68.
Niederle, Muriel, and Alvin E. Roth. 2003. “Unraveling Reduces Mobility in a Labor Market: Gastroenterology with and Without a Centralized Match.” Journal of Political Economy 111 (6): 1342–52.
Roth, Alvin E. 1982. “The Economics of Matching: Stability and Incentives.” Mathematics of Operations Research 7 (4): 617–28. https://doi.org/10.1287/moor.7.4.617.
Roth, Alvin E. 1984. “The Evolution of the Labor Market for Medical Interns and Residents: A Case Study in Game Theory.” Journal of Political Economy 92 (6): 991–1016. https://doi.org/10.1086/261272.
Roth, Alvin E., and Elliott Peranson. 1999. “The Redesign of the Matching Market for American Physicians: Some Engineering Aspects of Economic Design.” American Economic Review 89 (4): 748–80. https://doi.org/10.1257/aer.89.4.748.
Roth, Alvin E., and Xiaolin Xing. 1994. “Jumping the Gun: Imperfections and Institutions Related to the Timing of Market Transactions.” American Economic Review 84 (4): 992–1044.

Fan, Y. (2026). Algorithmic Game Theory, Braess's Paradox and the Price of Anarchy in Traffic and Attention Networks: From Wardrop Equilibria and Selfish Routing to Platform Congestion, Read Beside Classical Chinese Hydraulic Engineering [算法博弈论、布雷斯悖论与流量分配的无秩序代价] (Version 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.23782094 · Licensed under Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0).