📑 本页目录（点开跳转）
17 · 稳定匹配
⏱ 42 分钟 ｜ ⭐⭐ 谁提案，谁受益
🎯 一句话
稳定 = 没有任何两个人愿意撇开安排、私下重新配对；延迟接受算法（DA）总能算出一个稳定匹配，而且提案的那一边会拿到全场对它最好的那个。
这是本套教程里第一个真正在跑的机制：美国住院医师分配（NRMP）每年拿它匹配四万多人，纽约、波士顿的中小学择校系统也是它。
🧩 一、一个会散伙的安排
两个学生 $s_1,s_2$，两所学校 $c_1,c_2$，各招 1 人。偏好：
| 谁 | 偏好（从最想要开始） |
|---|---|
| $s_1$ | $c_1 \succ c_2$ |
| $s_2$ | $c_1 \succ c_2$ |
| $c_1$ | $s_1 \succ s_2$ |
| $c_2$ | $s_2 \succ s_1$ |
现在管理员拍脑袋安排：$s_1 \to c_2$，$s_2 \to c_1$。
看上去每个人都有着落。但 $s_1$ 更想去 $c_1$，而 $c_1$ 也更想要 $s_1$ —— 这两个人只要私下一碰头，双方都能变好。安排就废了：$s_1$ 会去敲 $c_1$ 的门，$c_1$ 会把 $s_2$ 换掉。
⭐ 阻挡对（blocking pair）： $(s,c)$ 阻挡匹配 $\mu$，如果 $c \succ_s \mu(s)$ 并且 $s \succ_c \mu(c)$ —— 两个人都觉得对方比自己现在的搭档好。 匹配 $\mu$ 是稳定的（stable），当且仅当它一个阻挡对都没有。
稳定不是「大家都满意」，是「不满意也没辙」：你想跳槽，人家看不上你；人家想挖你，你看不上人家。
模型
- 学生集合 $S$、学校集合 $C$，学校 $c$ 有名额 $b_c$
- 匹配 $\mu \subseteq S \times C$ 要满足：每个学生最多出现在一对里；每个学校 $c$ 最多出现在 $b_c$ 对里
- $b_c = 1$（且 $|S| = |C| = n$）叫一对一匹配，也叫「稳定婚姻问题」；$b_c > 1$ 叫多对一匹配
三条偏好假设（后面所有结论都靠它们）：
- 每个人都宁可配上也不愿落单
- 每个人只关心自己配到谁，不关心别人配到谁
- 偏好是完全、传递、严格的 —— 没有并列
⚠️ 第 3 条不是装饰。有并列时「谁提案谁受益」那套结论会整个塌掉，本章从头到尾默认无并列。
🧩 二、延迟接受算法：手算套路
Gale 和 Shapley 1962 年给的算法。先固定一边提案（这里让学生提案，简称 SPDA）。
四步循环：
- 每个还没被暂定接收的学生，向自己列表里还没拒过自己的最高的那所学校提案
- 学校收到提案后，把「手里已有的人 + 新提案的人」放一起排序，只留最好的 $b_c$ 个
- 被挤下来的学生回到第 1 步（他被这所学校拒了，以后不再提这所）
- 没有人再能提案时停
⭐ 关键在「延迟」两个字：学校收下不等于定下来，只是暂时握着（tentatively hold）。后面来了更好的，随时把手里的人踢掉。这就是它能保证稳定的原因 —— 一个学校永远不会因为「早签了约」而错过更好的人。
完整走一遍
$|S| = |C| = 3$，每校招 1 人：
| 学生 | 偏好 | 学校 | 偏好 | |
|---|---|---|---|---|
| $s_1$ | $c_2 \succ c_1 \succ c_3$ | $c_1$ | $s_1 \succ s_2 \succ s_3$ | |
| $s_2$ | $c_1 \succ c_2 \succ c_3$ | $c_2$ | $s_2 \succ s_1 \succ s_3$ | |
| $s_3$ | $c_1 \succ c_2 \succ c_3$ | $c_3$ | $s_1 \succ s_2 \succ s_3$ |
第 1 轮 - $s_1 \to c_2$：$c_2$ 空着，暂收 - $s_2 \to c_1$：$c_1$ 空着，暂收 - $s_3 \to c_1$：$c_1$ 手里是 $s_2$，而 $c_1$ 觉得 $s_2 \succ s_3$ → 拒了 $s_3$
第 2 轮 - $s_3 \to c_2$（它列表里的下一个）：$c_2$ 手里是 $s_1$，$c_2$ 觉得 $s_1 \succ s_3$ → 又拒了
第 3 轮 - $s_3 \to c_3$：$c_3$ 空着，暂收
没人能再提案，停。结果：
$$\mu = \{(s_1,c_2),\ (s_2,c_1),\ (s_3,c_3)\}$$
三条从手算里就能看出来的性质
- 一定会停：一个学生最多被 $n$ 所学校各拒一次，总提案数不超过 $n^2$ ⟹ 算法是 $O(n^2)$ 的
- 学校手里的人只会变好，学生手里的学校只会变差（看上图那两个红箭头，只朝右下走）
- 没人落单（当 $|S|=|C|=n$ 时）：某个学校空着，说明没人向它提过案；可算法只在没人能提案时才停，而落单的学生本该继续提案 —— 矛盾
为什么它一定稳定（这个论证很短，值得看）
取任意一对 $(s,c)$，证明它不阻挡结果 $\mu$：
- 情况 1：$s$ 觉得 $\mu(s)$ 不比 $c$ 差 → $s$ 不想跳，不构成阻挡对
- 情况 2：$s$ 觉得 $c$ 比 $\mu(s)$ 好 → 那么 $s$ 一定在提案给 $\mu(s)$ 之前先向 $c$ 提过案（学生是从上往下走的），而 $s$ 现在不在 $c$ 那儿，说明 $c$ 拒过 $s$。而学校手里的人只会越换越好 ⟹ $\mu(c) \succ_c s$，$c$ 看不上 $s$，也不构成阻挡对
两种情况都不阻挡 ⟹ $\mu$ 稳定。∎
🧩 三、一个实例可以有好几个稳定匹配
改一组偏好（这是最经典的「循环」例子）：
| 学生 | 偏好 | 学校 | 偏好 | |
|---|---|---|---|---|
| $s_1$ | $c_1 \succ c_2 \succ c_3$ | $c_1$ | $s_2 \succ s_3 \succ s_1$ | |
| $s_2$ | $c_2 \succ c_3 \succ c_1$ | $c_2$ | $s_3 \succ s_1 \succ s_2$ | |
| $s_3$ | $c_3 \succ c_1 \succ c_2$ | $c_3$ | $s_1 \succ s_2 \succ s_3$ |
这个实例有三个稳定匹配。用「每个人拿到的是自己列表里第几名」来看：
| 稳定匹配 | 配对 | 学生拿到第几名 | 学校拿到第几名 |
|---|---|---|---|
| $\mu_S$ | $(s_1,c_1),(s_2,c_2),(s_3,c_3)$ | 1, 1, 1 ⭐ | 3, 3, 3 💀 |
| $\mu_M$ | $(s_1,c_2),(s_2,c_3),(s_3,c_1)$ | 2, 2, 2 | 2, 2, 2 |
| $\mu_C$ | $(s_1,c_3),(s_2,c_1),(s_3,c_2)$ | 3, 3, 3 💀 | 1, 1, 1 ⭐ |
自己动手验一下 $\mu_M$ 为什么稳定：$s_1$ 手里是 $c_2$，它更想要 $c_1$；可 $c_1$ 手里是 $s_3$，而 $c_1$ 觉得 $s_3 \succ s_1$ —— 看不上。另外两个同理。没有一对能同时满意。
现在跑一遍 SPDA：$s_1 \to c_1$、$s_2 \to c_2$、$s_3 \to c_3$，三所学校都空着，全部暂收，一次拒绝都没发生，直接停 —— 得到的正是 $\mu_S$，每个学生第一志愿，每个学校垫底志愿。
反过来跑 CPDA（学校提案）：$c_1 \to s_2$、$c_2 \to s_3$、$c_3 \to s_1$，同样一轮结束 —— 得到 $\mu_C$，每个学校第一志愿，每个学生垫底志愿。
可达搭档与最优搭档
可达（achievable）：学校 $c$ 对学生 $s$ 是可达的，如果存在某个稳定匹配 $\mu$ 使 $\mu(s)=c$。 最优搭档：$s$ 的所有可达学校里它最想去的那个。（偏好严格 ⟹ 唯一）
在上面的例子里，$s_1$ 的可达学校是 $\{c_1,c_2,c_3\}$ 全部三所，最优搭档是 $c_1$。
⭐ 定理（Gale–Shapley 1962）：SPDA 把每个学生匹配到它的最优搭档；同时把每所学校匹配到它最差的可达学生。CPDA 反过来。
为什么「每个学生同时拿到最优」不会打架？因为两个学生不可能有同一个最优搭档：假如 $c$ 同时是 $s$ 和 $s'$ 的最优搭档、且 $c$ 更喜欢 $s$，那在那个把 $c$ 给了 $s'$ 的稳定匹配里，$s$ 只能配到比 $c$ 差的学校 —— 于是 $(s,c)$ 就是阻挡对，那个匹配根本不稳定。矛盾。
⭐ 「谁提案，谁受益」： DA 对提案方最优、对接受方最差。这是整章最值得记住的一句 —— 一个系统上线时选谁提案，就等于事先决定了利益偏向谁。NRMP 1998 年把机制从「医院提案」改成「申请人提案」，改的就是这一个字。
🧩 四、说真话划不划算
机制拿到的是上报的偏好，不是真偏好。所以必须问：有人靠撒谎能变好吗？
策略防伪（strategyproof）：不管别人报什么，每个人报真话都是自己的最优选择。
⭐ 定理：SPDA 对学生是策略防伪的。 直觉：SPDA 已经把每个学生送到它的最优可达搭档了 —— 你能拿到的最好结果已经拿到了，撒谎只能更差。
⚠️ 但对学校不是。 回到第二节那个实例，$c_1$ 的真实偏好是 $s_1 \succ s_2 \succ s_3$，跑出来 $c_1$ 拿到 $s_2$（第 2 名）。现在让 $c_1$ 谎报成 $s_1 \succ s_3 \succ s_2$：
- 第 1 轮：$s_1 \to c_2$ 暂收；$s_2 \to c_1$ 暂收；$s_3 \to c_1$，按谎报的偏好 $s_3 \succ s_2$ → $c_1$ 收下 $s_3$，踢掉 $s_2$
- 第 2 轮：$s_2 \to c_2$，$c_2$ 真心觉得 $s_2 \succ s_1$ → 收 $s_2$，踢掉 $s_1$
- 第 3 轮：$s_1 \to c_1$，谎报里 $s_1 \succ s_3$ → 收 $s_1$，踢掉 $s_3$
- 第 4 轮：$s_3 \to c_2$ 被拒；第 5 轮：$s_3 \to c_3$ 暂收
结果 $\mu' = \{(s_1,c_1),(s_2,c_2),(s_3,c_3)\}$ —— $c_1$ 靠撒谎从 $s_2$ 升到了 $s_1$，拿到了自己真正的第一志愿。
$c_1$ 干的事很朴素：先假装喜欢一个「诱饵」把现有的人挤走，制造连锁反应，等真正想要的人被别的学校吐出来时正好接住。
💀 Roth 1982：没有任何稳定匹配机制能对双方同时策略防伪。 这不是 DA 没设计好，是做不到。稳定 + 双边防伪，只能二选一。所以现实里的问题永远是「让哪一边说真话」，而不是「怎么让所有人说真话」。
补充两个考点级结论：
- 最优操纵（对所有可能情况都最好的谎报）能在 $O(n^3)$ 时间内算出来 —— 撒谎不但有用，还是可计算的
- 学校数量很多时，单个学校能靠谎报捞到的好处会迅速消失（大市场里操纵空间趋近于零），这是 NRMP 敢一直用 DA 的现实理由
🧩 五、多对一、乡村医院，和它到底用在哪
现实里学校招的不是 1 个人，是 $b_c$ 个。处理办法出人意料地简单：把一所招 $b_c$ 人的学校拆成 $b_c$ 个「只招 1 人的座位」（座位之间学生按固定顺序偏好，学校的每个座位偏好都一样）。
⭐ 这个「典范归约」和原问题的稳定匹配是一一对应的。于是一对一的所有结论直接搬过来：稳定匹配一定存在、DA 多项式时间能算、提案方最优。DA 本身也只要改一个字：学校暂时握住排名最高的 $b_c$ 个人。
学校的偏好这时要求是回应性的（responsive）：其他人不变时，用好学生换掉差学生一定更好。注意它不完全 —— $\{s_1,s_4\}$ 和 $\{s_2,s_3\}$ 谁更好，回应性不做规定。
乡村医院定理
⭐ 定理（Roth）：在任意两个稳定匹配 $\mu, \mu'$ 下， 1. 每所学校招到的人数完全相同：$|\mu(c)| = |\mu'(c)|$ 2. 如果某所学校没招满（$|\mu(c)| < b_c$），那它招到的人是同一批：$\mu(c) = \mu'(c)$
名字来自一个真实诉求：美国的乡村医院常年招不满，一直抱怨 NRMP 对它们不利，要求改机制。这条定理说的是 —— 只要还想要稳定，换哪个稳定匹配都没用，招不满的医院拿到的会是一模一样的那几个人。 想帮乡村医院，只能放弃稳定或者改变约束（比如给补贴、给配额），改算法是无效的。
真实落地
| 场景 | 怎么用 |
|---|---|
| NRMP（美国住院医师匹配） | 1952 年起用 DA，每年匹配 4 万多名医学生。1998 年改成申请人提案并加入「夫妻同城」配对 |
| 学校择校 | 纽约高中、波士顿小学都换成了学生提案的 DA。此前的「波士顿机制」（按第一志愿优先录取）逼得家长必须策略性填报 —— 不敢填热门校 |
| 器官交换、劳动力市场 | 见下一章的单边版本 |
⚠️ 多对一还多了一种操纵：谎报容量。 学校可以少报名额（$b_c$ 报小），把自己变「稀缺」来挤掉竞争对手，最后反而招到更好的人。这是一对一版本里根本不存在的攻击面。
🔗 这一章连到哪里
| 去哪 | 为什么 |
|---|---|
| 18-住房市场与TTC.md | 下一章把「两边都有偏好」换成「只有一边有偏好、但每人手里已经有东西」—— 稳定的概念会变成「核心」，算法会变成找环 |
| 16 · 机制设计在解什么 | 回去看策略防伪、帕累托最优这些性质的一般定义；本章是它们的第一个完整实例 |
| ../推荐算法/15b-广告-从推荐到竞价.html | 同一套机制设计思想最赚钱的工业落点：广告拍卖里的 GSP/VCG 也在解「怎么让人说真话」，而且和这里一样做不到全都要 |
| ../智能体工程教程/13-多Agent协作.html | 那边是工程：多个 Agent 目标一致，问怎么编排；这边是理论：目标冲突时会自发变成什么样。做多 Agent 系统前先知道哪些冲突是编排不掉的 |
✅ 检查点
- 用自己的话说清「阻挡对」的两个条件，并解释为什么「稳定」不等于「所有人都满意」。
- SPDA 里「延迟」两个字指的是什么？如果学校收到提案就当场定死，会出什么问题？
- 第二节那个 3×3 实例里，$s_3$ 一共被拒了几次？最后配到第几志愿？
- 为什么 SPDA 的总提案数不会超过 $n^2$？
- 稳定性证明的情况 2 用到了「学校手里的人只会越换越好」，去掉这一条论证在哪一步断掉？
- 第三节的循环实例里，$\mu_S$ 和 $\mu_C$ 分别让学生/学校拿到第几志愿？为什么两个都稳定？
- $c_1$ 那次成功的谎报，第 1 轮做了什么、为什么会引发连锁反应？
- 乡村医院定理为什么意味着「换稳定匹配救不了招不满的医院」？
- 多对一比一对一多出来的那种操纵手段是什么？
👀 答案
- $(s,c)$ 阻挡 $\mu$ 需要 $c \succ_s \mu(s)$ 且 $s \succ_c \mu(c)$ —— 两个人互相都觉得对方更好。稳定只是说「没有这样的一对」，完全允许有人拿到垫底志愿：第三节的 $\mu_C$ 里三个学生全是第 3 志愿，照样稳定，因为想跳的人都被对方看不上。
- 「延迟」指学校只是暂时握着手里的人，后面来了更好的随时替换，不做最终承诺。当场定死的话，$c_1$ 会在第 1 轮就锁死 $s_2$，等更好的 $s_1$ 来了也换不了 —— 而 $(s_1,c_1)$ 就成了阻挡对，结果不稳定。
- $s_3$ 被拒 2 次（第 1 轮被 $c_1$ 拒、第 2 轮被 $c_2$ 拒），最后进 $c_3$，是它的第 3 志愿。
- 一个学生绝不向同一所学校提案两次，所以每人最多提 $n$ 次；$n$ 个学生共 $n^2$ 次。
- 情况 2 推出「$c$ 拒过 $s$」之后，需要「$c$ 现在手里的人不比 $s$ 差」才能断定 $c$ 看不上 $s$。如果学校手里的人可能变差，$c$ 完全可能拒了 $s$ 之后又跌到比 $s$ 更差的人 —— 那 $(s,c)$ 就真成阻挡对了。
- $\mu_S$：学生 1,1,1；学校 3,3,3。$\mu_C$：学生 3,3,3；学校 1,1,1。两个都稳定是因为想跳的那一方总被对方看不上 —— 比如 $\mu_C$ 里 $s_1$ 想要 $c_1$，但 $c_1$ 手里是 $s_2$，而 $c_1$ 觉得 $s_2 \succ s_1$。
- $c_1$ 谎称 $s_3 \succ s_2$，第 1 轮就把 $s_2$ 踢出去当诱饵。$s_2$ 转投 $c_2$ 并挤掉 $s_1$，$s_1$ 只好回头找 $c_1$ —— 这正是 $c_1$ 真正想要的人。最终 $c_1$ 从 $s_2$ 换成了 $s_1$。
- 定理第 2 条说：招不满的学校在所有稳定匹配下拿到的是同一批人。所以在「保持稳定」的前提下换任何算法、换任何一边提案，乡村医院的结果一个字都不会变。要改只能放弃稳定或改约束（补贴、配额）。
- 谎报容量：少报 $b_c$ 把自己变稀缺，挤掉竞争对手后反而招到更好的学生。一对一里 $b_c$ 恒等于 1，没有这个自由度。
🛑 可以停在这里
⚡ 走神救援
这一章解决的问题是：两边都有偏好、要配对，怎么配才不会散伙。判据叫稳定：不存在阻挡对 —— 也就是没有任何一对 $(s,c)$ 同时满足「$s$ 觉得 $c$ 比自己现在的搭档好」和「$c$ 觉得 $s$ 比自己现在的搭档好」。稳定不等于人人满意，它只保证「你不满意也跳不动」。
算法是 Gale–Shapley 的延迟接受（DA）：固定一边提案，提案方从自己列表最上面往下走，接受方只暂时握着目前最好的 $b_c$ 个人，来了更好的就把手里的人踢掉。关键就在「暂时」两个字 —— 学校永远不会因为早签约而错过更好的人。手算的那个 3×3 例子里，$s_1 \to c_2$、$s_2 \to c_1$ 被暂收，$s_3$ 连续被 $c_1$、$c_2$ 拒了 2 次，第 3 轮才落到 $c_3$，一共 5 次提案。全程有两条不变量：学校手里的人只会越换越好，学生手里的选择只会越换越差。由此得到：一定终止（每人最多被 $n$ 所学校各拒一次，$O(n^2)$）、没人落单、而且一定稳定（证明只有两种情况：要么 $s$ 不想跳，要么 $s$ 早提案给 $c$ 却被拒过，说明 $c$ 手里的人只会更好）。
一个实例可以有多个稳定匹配。经典的循环例子里有三个：学生全拿第 1 志愿（学校全拿第 3）、全拿第 2、全拿第 3（学校全拿第 1）。SPDA 输出的正是第一个，CPDA 输出的正是第三个。这就是本章最该记住的一句：⭐ 谁提案谁受益 —— DA 对提案方最优、对接受方最差。上线时选谁提案，等于事先决定了利益偏向谁。
策略上：SPDA 对学生策略防伪（你已经拿到最优可达搭档了，撒谎只会更差），但对学校不是。手算的那个反例里 $c_1$ 谎报 $s_1 \succ s_3 \succ s_2$，先把 $s_2$ 当诱饵踢走引发连锁反应，最后接住了真正想要的 $s_1$，从第 2 名升到第 1 名。Roth 1982 证明：没有任何稳定机制能对双方同时策略防伪，这是不可能性不是设计缺陷。
多对一（每校 $b_c$ 个名额）靠「把学校拆成 $b_c$ 个座位」归约回一对一，结论全部照搬。乡村医院定理说：所有稳定匹配下每所学校招到的人数相同，招不满的学校招到的甚至是同一批人 —— 所以想帮招不满的乡村医院，换算法是无效的。落地上，NRMP 从 1952 年用到今天（1998 年改成申请人提案），纽约和波士顿的择校系统也换成了学生提案的 DA，替掉了逼家长不敢填热门校的旧机制。
下一节 👉 18-住房市场与TTC.md