拆解 Gale–Shapley：求婚、稳定与偏向
Gale–Shapley 从三个层面拆解：先看核心步骤——求婚、拒绝与延迟接受如何一步步收敛；再定义稳定——为什么结果里不存在 blocking pair；最后考察偏向——man-optimal 定理揭示主动求婚一方的系统性优势。每节都可以修改偏好、单步执行，旁边的代码面板会高亮当前执行行。
1 · 核心步骤：求婚与替换
Gale–Shapley 的核心规则：自由的 man 按偏好从高到低依次求婚，woman 始终持有当前最优对象。关键在于 woman 的接受是暂时的——出现更优者就替换，把原对象退回自由队列。
两条性质保证算法收敛:
其一，man 只沿偏好往下求婚，不回头——因此每个 man 对每个 woman 至多求婚一次。其二，woman 持有的对象只会变得更优——一旦订婚就不再单身，只会换成更喜欢的。两者结合：求婚次数有上限（至多 ），队列必然清空，且结束时所有人都有对象。
下面按 man A B C D / woman 1 2 3 4 的偏好执行。点下一步，自由队列、连线、偏好表三处同步变化：橙虚线 = 本步求婚，绿实线 = 当前订婚。
2 · 稳定 = 没有 blocking pair
求婚与替换一节得到的匹配为什么称为「稳定」？需要先定义不稳定。一个匹配不稳定，是因为存在一对没配在一起、却彼此都更想要对方的 (m, w)——二者都有动机抛弃各自的当前对象、转而结合。这样的隐患对称为 blocking pair。
blocking pair 的精确定义：一对 (m, w) 满足两个条件——
其一，m 更喜欢 w 胜过自己的当前 partner;且其二，w 也更喜欢 m 胜过自己的当前 partner。只要存在哪怕一对这样的 (m, w)，匹配就不稳定；一对都找不出 = 稳定。
为什么 Gale–Shapley 的结果一定稳定？ 反过来想——假设结束时还有一对 blocking pair (m, w)，即 m 更想要 w 胜过自己的现任。注意 m 是按偏好从高到低挨个求婚的：既然他更喜欢 w，那他在向现任求婚之前，一定先向 w 求过婚。可如今 m 没和 w
在一起，只剩两种可能——w 当场拒了他，或先接受、后来又被更中意的人替换掉；无论哪种，都说明 w 手里的对象不比 m 差（回忆求婚与替换:woman 一旦订婚只会越换越好、绝不回头）。既然 w 并不更想要 m，「彼此都更想要对方」便不成立，与 blocking pair
的定义直接矛盾。举个例子： A 最想要 1，但 1 更中意 B;A 向 1 求婚被拒，退而和 2 在一起——这时 A 心里仍偏爱 1，可 (A, 1) 并非 blocking pair，因为 1 根本不想要 A，不过是 A 的一厢情愿。算法跑完后，这种「一方热、另一方冷」的对一个都不会剩，匹配必然稳定。
下面沿用同一组偏好 (man A B C D / woman 1 2 3 4)。切换不同的配对方案观察连线变化，红虚线 = 自动找出的 blocking pair。点一条红线（或下方的红色对），偏好表会高亮出这两人为什么都更想要对方。
3 · 偏向求婚方：man-optimal vs woman-optimal
稳定匹配可能不止一个。同一组偏好，让 man 主动求婚和让 woman 主动求婚，得到的稳定解可能不同——且差异有规律。
man-optimal 定理 (Gale–Shapley):man 求婚得到的稳定匹配中，每个 man 都得到「所有稳定匹配中各自能得到的最好对象」 (man-optimal)；与此同时，每个 woman 都得到各自最差的对象 (woman-pessimal)。交换求婚方，结果整体偏向另一方。主动求婚的一方占据系统性优势。
左右并排：man 求婚的结果 与 woman 求婚的结果。下方满意度条 = 每个人得到的对象在自己偏好里的名次（条越短越靠前 = 越满意）;名次和越小，整体满意度越高。换几组随机偏好，验证定理是否始终成立。
现实中的应用： 美国的 NRMP（住院医师与医院匹配）、各地的公立学校择校 / 高考志愿录取、器官捐献交换链，底层都是 Gale–Shapley 或它的变体。算法对「哪一方求婚」的选择，直接决定了结果偏向哪一方。
相关链接
- Stable marriage problem — Wikipedia en.wikipedia.org 问题定义、Gale–Shapley 算法、man-optimal 定理与复杂度证明。
- 2012 诺贝尔经济学奖 — Roth & Shapley nobelprize.org 「稳定分配理论与市场设计实践」,把这套算法从纸面推到真实的市场机制。