算法与数据结构 / 拆解 Gale–Shapley：求婚、稳定与偏向 待审核
Gale–Shapley · 延迟接受

拆解 Gale–Shapley：求婚、稳定与偏向

Gale–Shapley 分三层拆解：求婚与替换看延迟接受如何一步步收敛；稳定性与 blocking pair给出「稳定」的定义并证明算法结果满足它；求婚方的系统性优势考察谁主动求婚会如何改变结果。

以下讨论都设在最规整的情形：两侧人数相等，且每个人都对另一侧的每一位都排出了完整偏好，没有「宁可单身也不要某人」这种保留选项。这个前提保证算法结束时不会有人落单。

1 · 求婚与替换

核心规则是：自由的 man 按偏好从高到低依次求婚，woman 始终持有当前最优对象。关键在于 woman 的接受是暂时的，出现更优者就替换，把原对象退回自由队列。

两条性质保证算法收敛。其一，man 只沿偏好往下求婚、不回头，因此每个 man 对每个 woman 至多求婚一次，求婚总次数不超过 n2n^2。其二，woman 持有的对象只会变得更优，一旦订婚就不再单身，只会换成更喜欢的。两者结合即得：求婚次数有上限、自由队列必然清空，且在上述完整偏好的前提下，结束时所有人都有对象。

图 1-1 · 按 man A–D 与 woman 1–4 的偏好逐步执行。橙虚线为本步求婚，绿实线为当前订婚；自由队列、连线与偏好表三处同步变化。可单步推进或改偏好。

2 · 稳定性与 blocking pair

要说明上一节的结果为什么叫「稳定」，得先定义不稳定。一个匹配不稳定，是因为存在一对没配在一起、却彼此都更想要对方的 (m,w)(m, w)：两人都有动机抛弃各自的当前对象转而结合。这样的隐患对称为 blocking pair。

它的精确定义是两个条件同时成立：mm 更喜欢 ww 胜过自己的当前 partner，同时 ww 也更喜欢 mm 胜过自己的当前 partner。只要存在哪怕一对这样的 (m,w)(m, w)，匹配就不稳定；一对都找不出即为稳定。

建议 · Gale–Shapley 的结果一定稳定，反证如下。假设结束时还剩一对 blocking pair (m,w)(m, w)，即 mm 更想要 ww 胜过现任。mm 是按偏好从高到低挨个求婚的，既然他更喜欢 ww，那他在向现任求婚之前一定先向 ww 求过婚。可如今两人没在一起，只剩两种可能：ww 当场拒了他，或先接受、后来又被更中意的人替换。无论哪种，都说明 ww 手里的对象不比 mm 差（§1 已证 woman 一旦订婚只会越换越好）。既然 ww 并不更想要 mm，「彼此都更想要对方」不成立，与 blocking pair 的定义矛盾。

单向的偏爱不构成 blocking pair：AA 最想要 11，但 11 更中意 BB，于是 AA 被拒后退而与 22 在一起。AA 心里仍偏爱 11，可 (A,1)(A, 1) 不是 blocking pair——11 根本不想要 AA。算法跑完后，这种一方热、另一方冷的对一个都不会剩。

图 2-1 · 沿用同一组偏好，红虚线为自动找出的 blocking pair。可切换配对方案观察连线变化，或点一条红线看偏好表里这两人为何都更想要对方。

3 · 求婚方的系统性优势

稳定匹配可能不止一个。同一组偏好，让 man 主动求婚与让 woman 主动求婚，得到的稳定解可能不同，而差异有规律。

注 · Gale–Shapley 的最优性定理：man 求婚得到的稳定匹配中，每个 man 都得到他在一切稳定匹配中能得到的最好对象（man-optimal）；与此同时每个 woman 都得到各自最差的对象（woman-pessimal）。交换求婚方，结论整体翻转。也就是说主动求婚的一方占据系统性优势。

这条定理可以在小规模上穷举验证。本页内置的那组 4×44 \times 4 偏好，4!=244! = 24 个完美匹配里只有两个是稳定的：A2 B4 C1 D3 与 A2 B4 C3 D1。man 求婚给出前者、woman 求婚给出后者，各取一端。把每人所得对象在自己偏好里的名次相加（00 为第一志愿），前者的 man 名次和为 55、woman 名次和为 22；后者的 man 名次和升到 77，而 woman 名次和降到 00——woman 求婚时四个 woman 全部拿到第一志愿。AA 与 BB 在两个匹配里的对象完全相同，差异只落在 CC 与 DD 身上。

顺带一个实测：这组偏好跑完只用了 1414 次求婚，而 §1 给的上界是 n2=16n^2 = 16。那个上界统计的是「每个 man 对每个 woman 至多求婚一次」的最坏情形，通常并不取到。

图 3-1 · man 求婚与 woman 求婚的结果并排。下方满意度条为每人所得对象在自己偏好里的名次，条越短越靠前；名次和越小该侧整体越满意。可换随机偏好复核定理。

注 · 现实中的匹配市场大多跑这套算法或它的变体：美国的 NRMP（住院医师与医院匹配）、各地的公立学校择校与志愿录取、器官捐献交换链。既然「哪一方求婚」直接决定结果偏向哪一方，这个选择在实际制度设计里就不是技术细节。

4 · 参考文献

  1. Gale, D., & Shapley, L. S. (1962). College admissions and the stability of marriage. The American Mathematical Monthly, 69(1), 9–15.

相关链接