Lecture 11: Stable Matching（稳定匹配）

目录 · ← l11 · l13 →

Lecture 11: Stable Matching（稳定匹配）

概述

本讲研究一个”看起来简单、实则深刻”的现实问题：$n$ 个求职者与 $n$ 个岗位，双方各自有一份偏好排序，如何配对才算”好”？ 直觉上的”好”有很多版本（最大化第一志愿人数？最小化最后志愿人数？平均幸福度最高？），本讲选定的标准是稳定性 (stability)：不存在一对男女，他们没被配在一起，却双方都更愿意跟对方在一起。这样的双方称为不稳定对 (instability)，官方 Note 里叫流氓对 (rogue couple)。

核心结果是 Gale–Shapley 的提出-拒绝算法 (Propose-and-Reject Algorithm，1962)：它必然终止、必然产出一个完美匹配、且该匹配必然稳定。更进一步（本讲最精彩的部分）：算法总是对”提出方”最有利——若由男生提出，则每个男生都得到他在所有稳定匹配中能拿到的最好对象；而女生则恰恰得到所有稳定匹配中最差的对象。这个”性别不平等”的结论直接对应现实中住院医师匹配 (Residency Match) 的制度设计：谁有资格提申请，谁就在制度上占优。

本讲的证明技巧极具教学价值：三重反证 + 一个关键归纳引理（Improvement Lemma）+ 良序原理 (Well-Ordering Principle)。它是讲次 2（反证法）与讲次 3（归纳法）在算法分析上的第一次真正实战。

核心概念的直观解释

稳定匹配问题的数学建模（Stable Matching Problem）

• 定义：给定两个不相交的集合 $M = \{m_1,\dots,m_n\}$（男士/申请者/提出方候选）与 $W = \{w_1,\dots,w_n\}$（女士/医院/接收方），以及
  • 每个 $m \in M$ 对 $W$ 的一个严格全序偏好 $\succ_m$（即 $W$ 的一个排列，从最喜欢到最不喜欢）；
  • 每个 $w \in W$ 对 $M$ 的一个严格全序偏好 $\succ_w$。

  一个匹配 (matching) 是 $M \cup W$ 上的一个配对：每个 $m$ 至多配一个 $w$，每个 $w$ 至多配一个 $m$。若所有人都被配上，则称完美匹配 (perfect matching)。形式上完美匹配是一个双射 $\mu: M \to W$。

• 直观解释（”它是什么意思？”）：这是一张完全二分图 $K_{n,n}$（讲次 9、10 的语言），每条边上还刻着两个人的”心理价签”。任务是从 $n!$ 个可能的完美匹配中，挑出”没有私奔动机”的那一个。类比：给 $n$ 对男女安排相亲结果，要求”事后没有任何一对男女会互相说’早知道我们俩凑一对更好’“。
• 具体示例：$n=3$，三个岗位 Approximation Inc.、Basis Co.、Control Corp. 与三位申请者 Anita、Bridget、Christine。偏好表（越靠左越喜欢）：

注意这里的偏好是严格的（没有并列）。严格性是后面”最优性唯一”结论的必要前提——若允许并列，”每个男士的配偶唯一确定”就不一定成立了。

不稳定对 / 流氓对（Instability / Rogue Couple）

• 定义：在完美匹配 $\mu$ 中，若 $m$ 与 $w$ 没有被配在一起（$\mu(m) \ne w$），但同时满足 \(w \succ_m \mu(m) \quad\text{且}\quad m \succ_w \mu(w),\) 即 $m$ 更喜欢 $w$ 而不是自己当前的配偶、$w$ 也更喜欢 $m$ 而不是自己当前的配偶，则称 $(m,w)$ 是一个不稳定对（官方 Note 的用词是 rogue couple）。

  一个匹配是稳定匹配 (stable matching)，当且仅当它是完美匹配且不含任何不稳定对。

• 直观解释（”它是什么意思？”）：稳定 = “没人有私奔的动机”。注意它是双向的：只要有一方不愿意，”私奔”就办不成，这不算不稳定。用官方 Note 的话说：不稳定的匹配会真的崩掉——流氓申请者可以撕毁已签的 offer，流氓岗位可以解雇已录用的人去雇更喜欢的那位，结果”一个岗位空了、一个无辜的人被炒了”。稳定性的目标是：让所有人都情愿遵守最终结果。
• 具体示例（在 $n=3$ 例子上检验）：
  • 匹配 $\mu_1 = \{(App, \text{Christine}), (Bas, \text{Bridget}), (Con, \text{Anita})\}$ 是不稳定的。检验 $(App, \text{Anita})$：App 当前配 Christine，而 App 更喜欢 Anita（第 1 志愿 vs 第 3 志愿）；Anita 当前配 Con，而 Anita 更喜欢 App（第 2 志愿 vs 第 3 志愿）。双方都更愿意，于是 $(App, \text{Anita})$ 是不稳定对。（同理 $(App, \text{Bridget})$ 也是。）
  • 匹配 $\mu_2 = \{(App, \text{Bridget}), (Bas, \text{Anita}), (Con, \text{Christine})\}$ 是稳定的。有人会问：App 明明更喜欢 Anita 啊？但 Anita 当前配的是她的第一志愿 Bas，她不会为了 App 而离开，所以 $(App, \text{Anita})$ 不构成不稳定对。同理 Con 与 Christine 都配了自己的最后志愿，但他们更喜欢的对象都不愿意要他们，所以依然稳定。
• 脚本验算（下面的完整代码会给出）：对 $\mu_1$ 检测出不稳定对 $[(App,Anita), (App,Bridget)]$，对 $\mu_2$ 与算法输出均检测出零个不稳定对。

提出-拒绝算法（Propose-and-Reject / Gale–Shapley Algorithm）

• 定义：算法按”天 (day)”离散推进：
  • 每天上午：每个尚未被任何女士保留 offer 的男士，向自己名单上”还没拒绝过他的最靠前的那位女士”提出申请。
  • 每天下午：每位女士收集上午收到的所有申请，加上自己手上已有的 offer，从中挑出最喜欢的那一个回”也许（maybe）”（即把手上的 offer 换成这一个），对其余所有申请回”不（no）”，即拒绝。
  • 每天傍晚：每位被拒绝的男士，把该女士从自己名单上划掉（该女士从此不会再收到这位男士的申请）。
  • 当某一天没有任何申请被拒绝时循环结束：所有女士手上都有 offer，大家接受，算法终止。
• 直观解释（”它是什么意思？”）：这是一场”逐步降低标准”的相亲大会。男士方只会越来越将就（被拒一次，名单就少一个，剩下的选择只会更差）；女士方只会越来越挑剔（手上的 offer 只会越来越好）。两者”从两头向中间靠”，最终在某个点上恰好相遇——这个相遇点就是稳定匹配。官方 Note 把这个观察总结成 Observation 4.1，并由 Improvement Lemma（改进引理） 严格化。
• 具体示例：见下一节的完整伪代码与逐日手算表。

最优性（Optimality）：最优对象 / 最优匹配

• 定义 11.1（岗位 $J$ 的最优对象）：在 $J$ 的偏好表上，所有稳定匹配中能与 $J$ 配对的最靠前的那位申请者，称为 $J$ 的最优对象（optimal candidate）。若一个稳定匹配使每个岗位都配上它的最优对象，就称它是岗位最优匹配（job/employer-optimal matching）。
• 定义 11.2（申请者 $C$ 的最优岗位）：对称地，$C$ 的偏好表上所有稳定匹配中能与 $C$ 配对的最靠前的那个岗位，称为 $C$ 的最优岗位（optimal job）；相应地有申请者最优匹配（candidate-optimal matching）。
• 定义 11.3（最差对象 / pessimal）：同理可定义岗位最差对象（pessimal candidate）为 $J$ 在所有稳定匹配中能配到的最靠后的一位。若每个申请者都配上她的最差岗位，则该匹配是申请者最差匹配（candidate-pessimal matching）。
• 直观解释：注意”最优对象”不是”第一志愿”！第一志愿可能根本不现实（对方看不上你，任何稳定匹配里都配不到）。最优性是在稳定性的约束下取上确界——一个”条件最优”的概念。这一点是官方 Note 特别提醒的：”the notion of best partner can be a bit fuzzy if we are not careful.”
• 具体示例（$n=4$ 的官方例子）：岗位 1,2,3,4 与申请者 A,B,C,D，偏好如下。

这个实例恰有两个稳定匹配（下面的脚本穷举 $4! = 24$ 个匹配逐一验证过）： \(S = \{(1,A),(2,D),(3,C),(4,B)\}, \qquad T = \{(1,A),(2,C),(3,D),(4,B)\}.\) 岗位 2 的第一志愿是 A，但不存在任何稳定匹配把 2 与 A 配在一起（穷举确认）——因为 A 在岗位 2 身上只排第 3，而别的岗位（1 和 3）都更喜欢 A，把 2 与 A 硬配会制造不稳定对。所以岗位 2 的最优对象是 D。在 $S$ 中每个岗位都拿到自己在该实例中的最优对象，故 $S$ 是岗位最优匹配；$T$ 则是申请者最优匹配（A 拿到最优岗位 1，B 拿到最优岗位 4，C 拿到最优岗位 2，D 拿到最优岗位 3）。

良序原理（Well-Ordering Principle）

• 定义：若 $S \subseteq \mathbb{N}$ 且 $S \ne \varnothing$，则 $S$ 有最小元素。
• 直观解释：这是”自然数集上一定存在第一个反例”的保证。它和归纳法等价：归纳法的有效性正依赖于自然数有良序。反证法里那句熟悉的 “suppose day $k$ is the first day such that…” 之所以合法，正是因为有良序原理；而整数集 $\mathbb{Z}$（有负无穷）、实数集 $\mathbb{R}$、非负实数集 $[0,\infty)$ 都不满足良序原理（例如 $\{n \in \mathbb{Z} : n < 0\}$ 没有最小元素，$(0,1]$ 作为非负实数的子集没有最小元素）。
• 具体示例：$S_1 = \{5,2,11,7,8\}$ 最小元是 2；$S_2 = $ 全体奇数，最小元是 1；$S_3 = $ 全体质数，最小元是 2。三个都有最小元，符合良序原理。反例：$\{n\in\mathbb{Z} : n \text{ 是负数}\}$ 没有最小元，所以 $\mathbb{Z}$ 不满足良序原理。

室友问题（Roommates Problem）——为什么”两类对象”不可省

• 定义：$2n$ 个人两两配对成室友，每个人对其余 $2n-1$ 人有偏好序。这里没有”两类”之分，任何人都可能与任何人配对。
• 直观解释：稳定匹配问题的”两类性（gender / two types）”看起来只是一个无关紧要的叙述设定，其实是本质性的。室友问题是一个”同类”问题，它不一定有稳定匹配。这解释了为什么任何”稳定匹配一定存在”的证明都必须用到两类性——也解释了为什么不能天真地认为”把不稳定对配起来、重复，最终必然稳定”（那个论证如果成立，就能套用到室友问题上，而室友问题会给出反例）。
• 具体示例（$2n=4$ 的反例，脚本已穷举验证）：四人 A,B,C,D（$D$ 视为”谁都可以”，官方表格中 D 那一行是全破折号）。

全部 3 种配对方式都会出现不稳定对：

配对方式              不稳定对        判定
-------------------------------------------------
{(A,B), (C,D)}        (B,C)          不稳定
{(A,C), (B,D)}        (A,B)          不稳定
{(A,D), (B,C)}        (A,C)          不稳定
-------------------------------------------------
结论：该室友问题实例没有稳定匹配。
（对比：稳定匹配问题中，Gale-Shapley 保证一定存在稳定匹配。）

完整证明与推导（核心）

算法完整伪代码

算法：PROPOSE-AND-REJECT（男士提出、女士保留的版本）

输入：n 位男士 M = {m_1,...,m_n}，
       n 位女士 W = {w_1,...,w_n}，
       每位男士 m 的偏好表 pref_m（W 的排列），
       每位女士 w 的偏好表 pref_w（M 的排列）。
输出：一个完美匹配 mu: M -> W。

 1  for each m in M:  next[m] <- 1          # next[m] 指向 m 的下一个申请目标（1-based）
 2  for each m in M:  free[m] <- true       # 是否"手上没有 offer 被保留"
 3  for each w in W:  held[w] <- NIL        # 女士 w 当前手上保留的 offer（来自哪位男士）
 4
 5  while 存在 m 使得 free[m] = true:       # 只要还有人要提申请
 6      # ---------- 上午：提出 ----------
 7      for each m with free[m] = true:
 8          if next[m] <= n:
 9              w <- pref_m[next[m]]        # 名单上最靠前、尚未拒绝过他的女士
10              next[m] <- next[m] + 1
11              m 向 w 提出申请
12
13      # ---------- 下午：保留 / 拒绝 ----------
14      rejected <- 空集
15      for each w in W 收到申请:
16          candidates <- {刚才向 w 申请的男士} ∪ ({held[w]} 若非 NIL)
17          best <- candidates 中在 pref_w 里最靠前的那位
18          for each c in candidates, c != best:
19              rejected <- rejected ∪ {c}          # w 拒绝 c
20          held[w] <- best                          # 保留最好的这一个
21
22      # ---------- 傍晚：划名单 ----------
23      for each m in rejected:
24          free[m] <- true                          # 被拒者明天继续提申请
25          # m 的名单事实上已通过 next[m] 前进而"划掉"了 w
26      for each m not in rejected:
27          free[m] <- false                         # 被保留者明天不再提申请
28
29  # ---------- 终止：某天无人被拒 ----------
30  return mu: for each w in W, mu(held[w]) <- w

逐日手算演示（$n=3$，官方 $n=3$ 例子；全部数据经脚本复算）

偏好表重抄一遍（越靠左越喜欢）：

男士（岗位）偏好                女士（申请者）偏好
--------------------------------------------------------
App : Anita > Bridget > Chris   Anita   : Bas > App > Con
Bas : Bridget > Anita > Chris   Bridget : App > Bas > Con
Con : Anita > Bridget > Chris   Chris   : App > Bas > Con
--------------------------------------------------------

【第 1 天】
  上午提出：App -> Anita      （App 的第 1 志愿）
            Bas -> Bridget    （Bas 的第 1 志愿）
            Con -> Anita      （Con 的第 1 志愿）
  下午处理：
            Anita 收到 {App, Con}。Anita 偏好 Bas > App > Con，
              两者中她最喜欢 App  => 保留 App，拒绝 Con。
            Bridget 收到 {Bas}     => 保留 Bas（无人可拒）。
            Chris 收到 {}          => 手上仍为空。
  傍晚划名单：Con 划掉 Anita。
  当前状态：Anita - App（保留）   Bridget - Bas（保留）   Chris - （空）

【第 2 天】
  上午提出：Con -> Bridget    （Con 划掉 Anita 后的下一个志愿）
  下午处理：Bridget 已有 Bas（保留），新收到 Con。
            Bridget 偏好 App > Bas > Con，在 {Bas, Con} 中取 Bas
            => 保留 Bas，拒绝 Con。
  傍晚划名单：Con 划掉 Bridget。
  当前状态：Anita - App   Bridget - Bas   Chris - （空）

【第 3 天】
  上午提出：Con -> Chris      （Con 划掉 Anita、Bridget 后的下一个志愿）
  下午处理：Chris 手上为空，收到 {Con} => 保留 Con。
  傍晚：本日无人被拒 => **算法终止**。
  当前状态：Anita - App   Bridget - Bas   Chris - Con

【输出匹配】 mu = {(App, Anita), (Bas, Bridget), (Con, Christine)}
【稳定性检验】 脚本穷举全部 6 对 (m,w) 检查，不稳定对 = 0 个 => 稳定 ✓
【提议总数】 5 次 <= n^2 = 9 ✓

第 4 个算例：官方 $n=4$ 最优性例子（2 天就结束）

偏好表：男士 1,2,3,4；女士 A,B,C,D
  1 : A > B > C > D        A : 1 > 3 > 2 > 4
  2 : A > D > C > B        B : 4 > 3 > 2 > 1
  3 : A > C > B > D        C : 2 > 3 > 1 > 4
  4 : A > B > C > D        D : 3 > 4 > 2 > 1

【第 1 天】
  上午：1->A, 2->A, 3->A, 4->A     （四人第 1 志愿全是 A！）
  下午：A 收到 {1,2,3,4}。A 偏好 1 > 3 > 2 > 4
        => 保留 1，拒绝 2, 3, 4。
  当前状态：A - 1（保留）；B, C, D 手上为空。

【第 2 天】
  上午：2->D, 3->C, 4->B           （各自划掉 A 后的下一志愿）
  下午：D 收 {2} => 保留 2； C 收 {3} => 保留 3； B 收 {4} => 保留 4。
        本日无人被拒 => **终止**。
  输出： mu = {(1,A), (2,D), (3,C), (4,B)}

【相较】 穷举 24 个完美匹配，稳定匹配恰好 2 个：
        S = {(1,A),(2,D),(3,C),(4,B)}   <- 算法输出（岗位最优）
        T = {(1,A),(2,C),(3,D),(4,B)}   <- 申请者最优
        本次提议总数 7 次 <= 4^2 = 16 ✓
        S 与 T 中每个岗位/每位申请者拿到的都是各自在稳定匹配下的最优，
        但注意 S != T，说明"岗位最优"与"申请者最优"一般不能同时达到。

定理 11.1（终止性，Termination）：提出-拒绝算法一定终止。

证明策略：计数 + 单调性。算法每一”天”（一轮）若不停机，则当天必有至少一位男士被拒；而每位男士最多被拒 $n$ 次（名单上只有 $n$ 位女士，被拒一次就划掉一个）。所以总拒绝次数 $\le n^2$，轮数 $\le n^2$。

逐步推导：

1. 假设第 $d$ 天算法没有终止。 按终止条件（某天无人被拒），这说明第 $d$ 天至少有一位男士被拒。
2. 每位被拒的男士，当天傍晚把自己名单上刚被拒的那位女士划掉（代码里是 next[m] 前进一位）。
3. 每位男士名单上总共只有 $n$ 个女士，所以每位男士一生最多被拒 $n$ 次。
4. 所有男士一生最多被拒 $n \cdot n = n^2$ 次。
5. 而每运行一天（未终止）至少消耗一次拒绝。因此算法的天数 $\le n^2$，必然在有限步内终止。$\blacksquare$

【证明机制解说】：这个证明是”有界递减的势函数“的标准范式。定义势函数 $\Phi = $ “所有男士名单上尚未被拒的女士总数”，则 $\Phi$ 初值为 $n^2$，每轮至少减 1，且永不为负，故只能运行有限轮。这个技巧在算法分析中无处不在（讲次 5 的欧几里得算法终止性用的是同型论证：余数严格递减）。注意这里用的是弱界：实际上总提议次数通常远小于 $n^2$，本讲两个例子分别只用了 5 次和 7 次。

引理 11.2（改进引理，Improvement Lemma）：若某男士 $m$ 在第 $k$ 天向女士 $w$ 提出了申请，则在此后每一天（包括第 $k$ 天），$w$ 手上保留的 offer 都来自一位她至少同样喜欢于 $m$ 的男士（即 $w$ 手中的对象在偏好序上从不下降）。

证明策略：对天数 $i$ 做归纳（$i \ge k$）。这是全讲最关键的引理，后面所有定理都靠它。核心机制是”offer 不会爆炸“——女士手上的 offer 只要不被她自己拒掉就会一直保留，所以她的”保底选项”永不消失。

逐步推导：

1. 基础情形（$i = k$）：第 $k$ 天 $w$ 至少收到了 $m$ 的申请。算法规定 $w$ 在下午”从所有收到的申请（加上手上的）中挑最喜欢的保留”。因此她在第 $k$ 天结束时保留的那位，要么就是 $m$，要么是一位她比 $m$ 更喜欢的男士。两种情况下她保留下来的都”至少不差于 $m$” ✓。
2. 归纳假设：设第 $i$ 天（$i \ge k$）$w$ 手上保留着一位男士 $m^{\prime}$，且 $m^{\prime}$ 在她看来至少不差于 $m$（形式上 $m^{\prime} \succ_w m$ 或 $m^{\prime} = m$）。
3. 归纳步骤（从 $i$ 到 $i+1$）：
   • 因为 $w$ 没有拒绝 $m^{\prime}$（$m^{\prime}$ 正是她手上保留的），$m^{\prime}$ 在第 $i+1$ 天不会向别人提申请（代码逻辑：只有被拒者才在下一天继续行动），而是继续向 $w$ 提出（offer 不能撤回、也不会过期）。
   • 所以第 $i+1$ 天 $w$ 收到的申请集合中包含 $m^{\prime}$。
   • 她在下午从”包含 $m^{\prime}$ 的集合”中挑最喜欢的，故选中的那位至少不差于 $m^{\prime}$，从而（由归纳假设）至少不差于 $m$。
   • 故第 $i+1$ 天 $w$ 手上的对象”至少不差于 $m$” ✓。
4. 由归纳法，引理对一切 $i \ge k$ 成立。$\blacksquare$

（引理的另一个证法：良序原理版） 假设引理不成立，则存在第一个反例日 $i > k$，那天 $w$ 手上要么空、要么是一位比 $m$ 差的男士 $m^*$。看第 $i-1$ 天：她手上有一位 $m^{\prime}$，且 $m^{\prime}$ 至少不差于 $m$。由”offer 不撤回”，$m^{\prime}$ 在第 $i$ 天仍然向 $w$ 提出，所以 $w$ 在第 $i$ 天至少有 $m^{\prime}$ 这个选项，她挑出的最好选项必然至少不差于 $m^{\prime}$，从而至少不差于 $m$，与”是反例日”矛盾。这里的”第一个反例日”之所以存在，正是良序原理；而”存在第一个反例 ⟹ 矛盾”这个推理模式本质上就是归纳法——我们证的是 $\neg(\exists i,\, \neg(P(i) \Rightarrow P(i+1)))$，再由排中律得到 $\forall i,\, P(i) \Rightarrow P(i+1)$。

【证明机制解说】：这是全讲最重要的一条引理，因为后面三个定理（完美匹配、稳定性、最优性）全部只靠它。它的作用是给女士方提供了一个”不可撤销的保底“：一旦某位男士向你提过申请，你从此就再也不会拿到比他更差的人。因此女士的幸福度沿时间单调不减。反过来，男士的处境沿时间单调不增（被拒后名单变短，剩下的选择只会更差）。官方 Note 把这个对称性形容为”两方面从两头向中间靠拢，最终必须相遇”——这个”相遇点”就是稳定匹配。特别注意”offer 不会爆炸/不能撤回”的作用：如果允许岗位撤回 offer，$w$ 的保底就会消失，整条链立刻崩塌。

定理 11.3（完美匹配，Perfect Matching）：提出-拒绝算法终止时，每个男士与每位女士都被配上（匹配是完美的）。

证明策略：反证法（假设有男士落单，导出”女士数 $<$ 男士数”的计数矛盾），关键工具是引理 11.2。

逐步推导：

1. 反设算法终止时存在一位单身男士 $m$（$m$ 没有任何女士配给他）。
2. 算法终止意味着 $m$ 已经用完了自己的名单：他向 $n$ 位女士全部提出过申请，并且全部被拒绝。（因为算法只有在某位男士被拒后才会让他继续提申请；他能走完整张名单，说明每一位都拒绝了他。）
3. 对这 $n$ 位女士中的每一位 $w$ 使用引理 11.2：$w$ 拒绝过 $m$，所以”$w$ 在 $m$ 向她提出的那一天起，手上一直保留着一位至少不差于 $m$ 的男士”。特别地，在算法终止时，$w$ 手上的那位男士 $\ne m$（因为 $w$ 若手上有 $m$，就不会”拒绝”他）。
4. 于是算法终止时，$n$ 位女士每一位手上都有一位不是 $m$ 的男士。这些男士两两不同（一位男士同一时刻只能被一位女士保留），所以至少需要 $n$ 位除 $m$ 之外的男士。
5. 加上单身汉 $m$ 自己，男士总数至少是 $n+1$。
6. 但题目假设男士恰好有 $n$ 位，矛盾。
7. 故不存在单身男士。对称地（同构论证）也不存在单身女士，因此输出的是一个完美匹配。$\blacksquare$

【证明机制解说】：第 3 步是”引理的杠杆点“：$m$ 向所有人提过申请这个事实，通过引理转化成”$n$ 位女士都手握一个比 $m$ 更好的候选人”这个更强的结论。第 4 步的”两两不同”也不可省——一位男士不可能同时被两位女士保留（算法规定他一次只向一位女士提申请，被保留后就不再行动）。另一种等价说法：由定理 11.1 知道算法终止时”当天无人被拒”，而若有男士落单他第二天还会提申请（名单未用完），矛盾。这个更简单的论证依赖”名单用完 ⟹ 该男士一定被所有人拒过”这一步，本质上与上面是同一套计数。

定理 11.4（稳定性，Stability）：提出-拒绝算法输出的匹配一定是稳定的。

证明策略：直接证明 + 反证法。思路取自官方 Note：”从男士的视角“证明任何男士都不可能是流氓对的一员。取定最终匹配中的一对 $(m, w)$，假设 $m$ 更喜欢另一位女士 $w^$，只需证 $w^$ 不愿意跟 $m$ 走（即 $w^$ 更满意自己的最终对象）——那么 $(m,w^)$ 就不是流氓对。

逐步推导：

1. 设算法输出的匹配为 $\mu$。任取 $\mu$ 中的一对 $(m,w)$，设 $m$ 在偏好表上更喜欢某位女士 $w^* \ne w$（即 $w^* \succ_m w$）。
2. $m$ 一定向 $w^$ 提过申请。** 理由：$w^$ 在 $m$ 的名单上排在 $w$ **之前；算法中男士严格按名单从上往下提出申请，所以 $m$ 向 $w$ 提出申请之前，必定已经向 $w^*$ 提出过。
3. 对 $w^$ 使用改进引理（引理 11.2）**：在第 $k$ 天（$m$ 向 $w^$ 提出申请的那天）之后的每一天，$w^$ 手上都保留着一位至少不差于 $m$ 的男士。特别地，**在算法终止时**（也就是最终匹配 $\mu$ 中），$w^$ 的配偶 $\mu(w^)$ 满足 \(\mu(w^*) \succeq_{w^*} m,\) 即 $w^$ 对最终配偶的喜欢程度不低于**对 $m$ 的喜欢程度。
4. 因为偏好是严格的且 $m \ne \mu(w^)$（$m$ 已经配给了 $w$），实际上有 $\mu(w^) \succ_{w^} m$，即 $w^$ 更喜欢自己的最终配偶，而不愿意跟 $m$ 走。
5. 所以 $(m, w^)$ 不构成流氓对。由于 $(m,w)$ 与 $w^$ 都是任取的，任何男士都不可能参与流氓对。
6. 因此 $\mu$ 中不存在流氓对，$\mu$ 是稳定匹配。$\blacksquare$

【证明机制解说】：证明的”灵光一现”是“只从一个方向证”。要证”没有流氓对”，需要排除 $M \times W$ 中所有未配对的组合，工作量看似很大；但官方 Note 指出：只要从男士视角证明”任何男士都不是流氓对的成员”，整个匹配就稳定了——因为流氓对必须同时包含一位男士和一位女士，男士全部”清白”，就没有流氓对。而”男士清白”这件事恰好由改进引理一步锁死：你更喜欢的女士，一定是在你遇到现任之前就遇到过你，而她从此再也不会看上比你差的人。 这里再次用到了”offer 不能撤回”。

定理 11.5（岗位最优性，Gale–Shapley 定理之一）：提出-拒绝算法（男士提出）输出的匹配是岗位最优匹配——即对每位男士 $m$，他得到的配偶 $w = \mu(m)$ 是在所有稳定匹配中 $m$ 能配到的最优对象。等价地：$m$ 的最优对象就是算法给他的那一位。

证明策略：先用一条关键引理（引理 11.5a，即”拒绝过即永不可能”）把”拒绝”这一事件的永久后果锁死，再用反证法 + 良序原理完成最优性论证。引理 11.5a 是全部关键，先证它。

引理 11.5a（关键引理：”拒绝过 ⟹ 任何稳定匹配中都配不到”）：若女士 $w$ 在算法运行过程中拒绝过男士 $m$，则在任何稳定匹配中，$w$ 都不会与 $m$ 配对。

引理 11.5a 的证明（反证法 + 改进引理 + 构造流氓对）：

1. 设 $w$ 在第 $k$ 天拒绝了 $m$。按算法，第 $k$ 天下午 $w$ 手上保留的是某位男士 $m^\dagger$，满足 \(m^\dagger \succ_w m. \tag{$\\star$}\) （$m^\dagger$ 可能是当天的某位新申请者，也可能是她原来手上那位；无论哪种，她优先于 $m$。）
2. 由改进引理（引理 11.2），从第 $k$ 天起 $w$ 手上的对象只会越来越好，所以算法终止时 $w$ 的最终配偶 $\mu(w)$ 满足 \(\mu(w) \succeq_w m^\dagger \succ_w m. \tag{$\\star\\star$}\) 也就是说：$w$ 的最终对象严格优于 $m$。
3. 反设存在一个稳定匹配 $S$，其中 $w$ 与 $m$ 配对，即 $S(w) = m$。
4. 设 $S$ 中 $m^\dagger$ 的配偶是 $S(m^\dagger) = w^{\prime}$，即 $\{(m,w), (m^\dagger, w^{\prime}), \ldots\} \subseteq S$。（注意 $w^{\prime} \ne w$，因为 $S(w) = m$。）
5. 证明 $m^\dagger$ 更喜欢 $w$ 而不是 $w^{\prime}$。 回忆算法中男士严格按名单从上往下提出申请，被拒一次就划掉一位。$m^\dagger$ 在第 $k$ 天向 $w$ 提出了申请，说明 $w$ 之前的所有女士都已经拒绝过 $m^\dagger$。
   • 现在问：$w^{\prime}$ 在 $m^\dagger$ 的名单上排在 $w$ 之前还是之后？
   • 反设 $w^{\prime} \succ_{m^\dagger} w$（$w^{\prime}$ 排在 $w$ 前面）。那么 $m^\dagger$ 会先向 $w^{\prime}$ 提出申请。若 $w^{\prime}$ 保留了 $m^\dagger$，则 $m^\dagger$ 就停在 $w^{\prime}$ 那里、永远不会向 $w$ 提出——与”$m^\dagger$ 在第 $k$ 天向 $w$ 提出”矛盾。若 $w^{\prime}$ 拒绝了 $m^\dagger$，则由引理 11.5a 的论证结构本身（这正是我们要证的引理，但可以在这里用更弱的形式：由第 2 步的同类推理，$w^{\prime}$ 拒绝 $m^\dagger$ 意味着 $w^{\prime}$ 在算法中的最终对象 $\mu(w^{\prime}) \succ_{w^{\prime}} m^\dagger$），$w^{\prime}$ 在任何稳定匹配中都配不到 $m^\dagger$——特别地 $S(w^{\prime}) \ne m^\dagger$，与 $S(m^\dagger) = w^{\prime}$ 矛盾。
   • 两种情况都矛盾，故 \(w \succ_{m^\dagger} w^{\prime}. \tag{$\\dagger$}\)
6. 构造流氓对：由 $(\star)$ 有 $w$ 更喜欢 $m^\dagger$ 而非 $m$（她在 $S$ 中的配偶）；由 $(\dagger)$ 有 $m^\dagger$ 更喜欢 $w$ 而非 $w^{\prime}$（他在 $S$ 中的配偶）。而 $S$ 中 $w$ 与 $m$、$m^\dagger$ 与 $w^{\prime}$ 各自配对。于是 $(m^\dagger, w)$ 是 $S$ 中的流氓对，与 $S$ 稳定矛盾。
7. 故不存在这样的稳定匹配 $S$，即凡是拒绝过 $m$ 的女士，在任何稳定匹配中都配不到 $m$。$\blacksquare$

（引理 11.5a 的绕行证法，避免自引用）：第 5 步中”若 $w^{\prime}$ 拒绝了 $m^\dagger$”那一支用到了引理自身，属于循环论证。绕开的办法是改用良序原理做整体反证：设 $(m,w)$ 是”被 $w$ 拒绝过、却仍出现在某个稳定匹配中”这一现象里算法天数最早的一例（第 $k$ 天），则 $m^\dagger$ 在 $w$ 处停留的时间不晚于第 $k$ 天，而对 $m^\dagger$ 与 $w^{\prime}$ 的同类现象若存在也必须在更早的日子发生（否则 $m^\dagger$ 不会留在 $w$ 处）——与”最早”矛盾。这就是官方 Note 在定理 11.5 与定理 11.2 中反复使用的”取最早一天 + 良序原理“的标准手法；具体细节可以按定理 11.5 主证明的第 2、5 步照搬。

引理 11.5a 的直观解读：拒绝是”终局裁决”，不是”暂时搁置”。 一位女士一旦对某位男士说了 no，她的处境从此只会变好（改进引理），所以她永远不可能回过头去觉得”当初其实该接受他”。这是”offer 不能撤回 + 女士总挑最喜欢”两条算法规则的合力。去掉任何一条，引理立刻失效——这也是为什么官方 Note 在算法描述里特意强调 “a job can’t withdraw an offer once an offer is made”。

逐步推导（定理 11.5 主证明）：

1. 反设算法输出的匹配不是岗位最优的。那么至少存在一天，某位男士被自己的最优对象拒绝了。（若从未发生过这种事，则每位男士最终要么配到自己的最优对象、要么配到比它更好的——但”比最优对象更好”就是”也在某稳定匹配中能配到”，与”最优”的定义矛盾。）
2. 取最早的这样一天，记为第 $k$ 天（良序原理保证”最早”存在）。在第 $k$ 天，男士 $m$ 被女士 $w^$（他的最优对象）拒绝，$w^$ 转而保留了男士 $m^$（即 $w^$ 更喜欢 $m^*$）。
3. $w^$ 更喜欢 $m^$：这是第 $k$ 天的事实——她在 {含 $m$ 的申请集合} 中挑了 $m^*$，故 \(m^* \succ_{w^*} m. \tag{a}\)
4. 由最优对象的定义，存在一个稳定匹配 $T$，其中 $m$ 与 $w^$ 配在一起。设 $T$ 中 $m^$ 的配偶是 $w^{\prime}$（即 $\{(m, w^), (m^, w^{\prime}), \ldots\} \subseteq T$）。
5. 关键一步：$m^$ 最喜欢 $w^$ 至少不差于 $w^{\prime}$。 因为第 $k$ 天是第一次有男士被自己的最优对象拒绝，所以在第 $k$ 天之前（含第 $k$ 天之前的所有日子），$m^$ 没有被自己的最优对象拒绝过。而 $m^$ 在第 $k$ 天向 $w^$ 提出了申请——这意味着 $w^$ *排在 $m^$ 的最优对象之前或就是它*（男士按名单从上往下提申请，既然他把申请递到了 $w^$，说明他此前的所有申请都已被拒，而他的最优对象还没拒绝过他，故最优对象只能是 $w^$ 或比 $w^$ 更靠后）。既然 $w^{\prime}$ 是 $m^$ 在某个稳定匹配中的配偶，$w^{\prime}$ 至多只能是 $m^$ 的最优对象，所以 \(w^* \succeq_{m^*} w^{\prime}. \tag{b}\) 又因偏好严格且 $w^* \neq w^{\prime}$（$w^$ 在 $T$ 中配给 $m$，而 $m \ne m^$），实际上 $w^* \succ_{m^*} w^{\prime}$。
6. 于是 $(m^, w^)$ 在 $T$ 中是流氓对：由 (a) $w^$ 更喜欢 $m^$ 而非 $m$（她在 $T$ 中的配偶），由 (b) $m^$ 更喜欢 $w^$ 而非 $w^{\prime}$（他在 $T$ 中的配偶）；而且他们在 $T$ 中并未配在一起。这与 $T$ 的稳定性矛盾。
7. 矛盾说明第 $k$ 天这样的日子不存在，即算法从不让任何男士被自己的最优对象拒绝。由第 1 步的逆否，算法输出的是岗位最优匹配。$\blacksquare$

【证明机制解说】：证明有两处关键的”灵光”。

• 第一处：用良序原理选”最早的那一天”。这个”最早”的性质被用在第 5 步——因为此前没有更早的同类事件，$m^$ 这个”配角”才能被推出”$w^$ 是他的最优对象或更好”。如果换成”任取一天”，这一步立刻失效。
• 第二处：把”$m^$ 在第 $k$ 天向 $w^$ 提出申请”翻译成”$w^$ 在 $m^$ 名单上的位置不劣于其最优对象”。这条翻译依赖男士严格按名单顺序申请这一算法细节。
• 第三处（结构上的）：证明是”用自己的算法行为去污染任何声称更优的稳定匹配“。这是算法最优性证明的经典套路：假定存在一个”更好的”解 $T$，然后从算法运行轨迹里抠出一对”私奔者”来摧毁 $T$。

定理 11.6（性别不平等：岗位最优 ⟹ 申请者最差）：若一个匹配是岗位最优的，则它同时也是申请者最差 (candidate-pessimal) 的。特别地，提出-拒绝算法（男士提出）输出的匹配是申请者最差匹配。

证明策略：反证法。设 $T$ 是岗位最优匹配。假设存在另一个稳定匹配 $S$，其中某位女士 $C$ 配到了比在 $T$ 中更好的岗位（即 $T$ 不是申请者最差的），导出 $S$ 不稳定。

逐步推导：

1. 设 $T$ 是岗位最优匹配（由定理 11.5，它就是算法输出）。取 $T$ 中的一对 $(J, C)$。
2. 反设存在稳定匹配 $S$，其中 $C$ 与某个岗位 $J^$ 配对，且 $J^$ 在 $C$ 的偏好表上比 $J$ 更靠前（即 $C$ 认为 $S$ 比 $T$ 好）。设 $S$ 中 $J$ 的配偶是 $C^{\prime}$，即 $\{(J^*,C),(J,C^{\prime}),\ldots\}\subseteq S$。
3. 由 $T$ 的岗位最优性（定理 11.5），岗位 $J$ 在任何稳定匹配中能配到的最优对象就是 $C$。既然 $S$ 也是稳定匹配、$J$ 在 $S$ 中配的是 $C^{\prime}$，必有 \(C \succeq_J C^{\prime},\) 即 $J$ 更喜欢 $C$ 而不是 $C^{\prime}$（严格地，$C \succ_J C^{\prime}$，因为 $C \ne C^{\prime}$）。
4. 另一方面，由第 2 步的假设，$C$ 更喜欢 $J$ 而不是 $J^$：$J \succ_C J^$。
5. 于是 $(J, C)$ 在 $S$ 中构成流氓对：双方都更愿意跟对方在一起，而他们在 $S$ 中并未配对。这与 $S$ 稳定矛盾。
6. 矛盾说明不存在比 $T$ 中更好的稳定匹配让 $C$ 受益，即 $T$ 使每位女士都拿到她在所有稳定匹配中的最差岗位。故岗位最优匹配一定是申请者最差匹配。$\blacksquare$

推论 11.7（岗位最优匹配唯一）：岗位最优匹配是唯一的——即”让每位男士都配上自己的最优对象”这个匹配作为一个集合被唯一确定。等价地：提出-拒绝算法输出的那个匹配，是唯一的岗位最优匹配。

证明：对每位男士 $m$，由定义 11.1，他的最优对象 $\mathrm{opt}(m)$ 是唯一确定的一位女士（偏好是严格全序，且”在所有稳定匹配中能与 $m$ 配对的最靠前者”这个集合非空——至少算法输出的那个稳定匹配给了一位）。于是映射 $m \mapsto \mathrm{opt}(m)$ 是唯一确定的。由定理 11.5，算法输出 $\mu$ 满足 $\mu(m) = \mathrm{opt}(m)$ 对一切 $m$；任何其他岗位最优匹配 $S$ 也必须满足 $S(m) = \mathrm{opt}(m)$ 对一切 $m$，故 $S = \mu$（作为 $M \to W$ 的映射完全一致）。岗位最优匹配唯一 ✓。对称地，申请者最优匹配也唯一。$\blacksquare$

重要澄清（一个常见的过度推广）：上述唯一性只说明”岗位最优”这一个稳定匹配唯一，它不意味着”每个男士在所有稳定匹配中的配偶都相同”——后者是错的。官方 $n=4$ 例子就是现成的反例：

【稳定匹配 S 与 T 中，男士 2 与 3 的配偶不同】

  岗位最优匹配 S = {(1,A), (2,D), (3,C), (4,B)}
  申请者最优匹配 T = {(1,A), (2,C), (3,D), (4,B)}
                          ~~~      ~~~
  岗位 1：S 中配 A，T 中配 A   -> 相同
  岗位 2：S 中配 D，T 中配 C   -> **不同！**
  岗位 3：S 中配 C，T 中配 D   -> **不同！**
  岗位 4：S 中配 B，T 中配 B   -> 相同

  结论：只有"岗位最优"这一个特殊匹配被唯一确定；
        一般的稳定匹配中，同一位男士完全可能拿到不同的配偶。
        正确的不变性质是"稳定匹配集构成一个格 (lattice)"：
        任意两个稳定匹配之间，不存在"男士 2 在 S 更好而在 T 更差、
        同时男士 3 反之"这样的交叉——偏好序在稳定匹配集上是
        同调变化的（S 与 T 的差异是"协调地"转移）。

反例（存在多个稳定匹配 + 稳定匹配不唯一）

验证方法论（本讲全部数值算例都用这套脚本复算，可直接运行）：

// 保存为 gs.js，用 `node gs.js` 运行
// P：提出方偏好（P[m] = 接收方的有序列表）；Q：接收方偏好（Q[w] = 提出方的有序列表）
// 返回 eng：接收方 -> 提出方 的匹配
function gs(P, Q) {
  const free = Object.keys(P), next = {}, eng = {};
  for (const m of free) next[m] = 0;
  while (free.length) {
    const m = free.shift();                    // 取一位待提出者
    const w = P[m][next[m]++];                 // 向他名单上下一个未拒绝过他的对象提出
    if (!(w in eng)) { eng[w] = m; }           // 对方空手 => 先留住
    else {
      const cur = eng[w];                      // 对方已有现任
      if (Q[w].indexOf(m) < Q[w].indexOf(cur)) { eng[w] = m; free.push(cur); }  // 换人
      else free.push(m);                       // 被拒，明天继续
    }
  }
  return eng;
}

// 稳定性检验：穷举所有未配对的有序对，找流氓对
function rogueCouples(P, Q, eng) {
  const mateOf = {};
  for (const w in eng) mateOf[eng[w]] = w;
  const bad = [];
  for (const m of Object.keys(P))
    for (const w of Object.keys(Q)) {
      if (mateOf[m] === w) continue;                                  // 已配在一起，跳过
      const mWantsW = P[m].indexOf(w) < P[m].indexOf(mateOf[m]);      // 他更想要她
      const wWantsM = Q[w].indexOf(m) < Q[w].indexOf(eng[w]);         // 她也更想要他
      if (mWantsW && wWantsM) bad.push([m, w]);                       // 双向 => 流氓对
    }
  return bad;
}

// 穷举全部完美匹配，筛出所有稳定匹配
function* perms(a) {
  if (a.length <= 1) { yield a; return; }
  for (let i = 0; i < a.length; i++) {
    const rest = a.slice(0, i).concat(a.slice(i + 1));
    for (const p of perms(rest)) yield [a[i], ...p];
  }
}
function allStable(P, Q) {
  const ms = Object.keys(P), ws = Object.keys(Q), S = [];
  for (const p of perms(ws)) {
    const e = {}; ms.forEach((m, i) => e[p[i]] = m);
    if (rogueCouples(P, Q, e).length === 0) S.push(e);
  }
  return S;
}

脚本跑出的关键数据（本讲所有数字的来源）：

实例                                      GS 输出            天数  提议数  流氓对  稳定匹配数
--------------------------------------------------------------------------------------------
官方 n=3 例子                              {Anita:App,
                                           Bridget:Bas,
                                           Christine:Con}       3     5      0        2
官方 n=4 最优性例子                         {(1,A),(2,D),
                                            (3,C),(4,B)}        2     7      0        2
自造 3x3 思考题 Q1 实例                     {(1,b),(2,a),
                                            (3,c)}              5     7      0        1
2x2 反例（男士提出）                        {(1,a),(2,b)}       1     2      0        2
2x2 反例（女士提出，cand->job）             {(1,b),(2,a)}       1     2      0        2
--------------------------------------------------------------------------------------------
随机压力测试：n=3 随机偏好表 400 组
   - GS 输出不稳定的次数：0
   - GS 输出非"提出方最优"的次数：0   （与穷举出的所有稳定匹配逐一比对）
   - 存在多于 1 个稳定匹配的实例数：106 / 400（约 27%）
--------------------------------------------------------------------------------------------

反例 A：$2\times 2$ 实例，恰有两个稳定匹配。 偏好如下：

两个完美匹配都是稳定的：

• $\mu = \{(1,a),(2,b)\}$：1 拿到第 1 志愿 a，2 拿到第 1 志愿 b。检验未配对的 $(1,b)$：1 的偏好是 $a \succ_1 b$，他更喜欢现任 a 而非 b，所以 1 没有动机。检验 $(2,a)$：2 的偏好是 $b \succ_2 a$，他更喜欢现任 b。所以无流氓对 ✓。
• $\mu^{\prime} = \{(1,b),(2,a)\}$：检验 $(1,a)$：1 更喜欢 a（$a \succ_1 b$）—— 1 有意愿；但 a 更喜欢 2（$2 \succ_a 1$），a 的现任正是 2，所以 a 不愿意，$(1,a)$ 不构成流氓对。检验 $(2,b)$：2 更喜欢 b（$b \succ_2 a$）—— 2 有意愿；但 b 更喜欢 1（$1 \succ_b 2$），b 的现任正是 1，所以 b 不愿意。故无流氓对 ✓。

【2x2 双稳定匹配图示：两个匹配互不相同但都稳定】

   偏好：1: a > b         a: 2 > 1
         2: b > a         b: 1 > 2

   匹配 mu:  1--a,  2--b        匹配 mu': 1--b,  2--a
             |       |                    |       |
             双方都拿到第 1 志愿           双方都拿到第 2 志愿
             => 稳定（"皆大欢喜"）         => 稳定（"互相让位"）

   这两个匹配的"幸福度"完全相反，却都满足稳定性定义。
   这正说明稳定性只是一个"局部无冲突"条件，不唯一确定结果。

   对照：Gale-Shapley（男士提出）在这些偏好上输出 mu
        （因为男士先提第一志愿，女士接受 --> 见脚本输出）

• 脚本穷举确认：$2! = 2$ 个完美匹配中恰有 $2$ 个稳定匹配，即两个都稳定。这直接反驳”稳定匹配唯一”的直觉。
• 另一层的反例：官方 $n=4$ 例子与 $n=3$ 官方例子也都各有两个稳定匹配（脚本穷举 $4!=24$、$3!=6$ 逐一验证）：
  • $n=3$：$\{(App,Anita),(Bas,Bridget),(Con,Christine)\}$ 与 $\{(App,Bridget),(Bas,Anita),(Con,Christine)\}$。
  • $n=4$：$\{(1,A),(2,D),(3,C),(4,B)\}$ 与 $\{(1,A),(2,C),(3,D),(4,B)\}$。

反例 B：室友问题（同类配对）可能完全没有稳定匹配。 见”核心概念的直观解释”中的四人表格，3 种配对全都不稳定。这告诉我们：稳定匹配的存在性证明必须用到”两类对象”这一结构——Gale–Shapley 算法恰恰是一个构造性的存在性证明，但它对室友问题无从下手（因为没有”提出方/接收方”的划分）。

反例 C：天真算法”迭代地配好流氓对”不终止/不收敛。 若从任意匹配出发，发现流氓对就把它们配到一起、重复，直觉上”流氓对数量会减少”。但这是错误的：配好一对会打散原来两对，可能创造出新的流氓对。官方 Note 通过室友问题这个反例说明这个推理不可靠（因为在室友问题上，若该推理有效就会推出”室友问题总有稳定解”，而事实相反）。在稳定匹配问题上，这条路径也不能用来说明存在性——正确路线是 Gale–Shapley。

与经典问题的联系

（1）住院医师匹配（The Residency Match）：本讲最真实的落地案例。 20 世纪初，美国医学住院医师项目（residency programs）成为医院廉价劳动力的来源，岗位数逐渐超过毕业生数，竞争激烈。医院竞相提前发 offer：到 1940 年代中期，offer 已经提前到医学院三年级，有的医院甚至考虑发给二年级学生。美国医学会 (AMA) 出手禁止医学院在四年级前公布成绩单与推荐信。结果医院改用”短引信 offer (short fuse offer)“——只给学生几小时决定，以便被拒后还能找替补。这种恶性竞争最终促成了 1950 年代初的全国住院医师匹配计划 (National Residency Matching Program, NRMP)：医院给住院医师排序、住院医师给医院排序，由中心化系统统一配对。

关键细节：NRMP 最初用的配对并不稳定；直到 1952 年才换用提出-拒绝算法，从此产出稳定匹配。这是一个”用数学建模修正制度缺陷“的经典案例。2012 年，Lloyd Shapley 与 Alvin Roth 因把提出-拒绝算法推广到更复杂的市场设计（包括医学院匹配、肾移植配对、公立学校择校）而获得诺贝尔经济学奖。某种意义上，Roth 的核心贡献正是实证地论证稳定性是市场能长期存活的关键：不稳定的匹配系统会被参与者”用脚投票”（撕毁 offer、私下另谈）而崩溃。

（2）问题的严格形式化（把现实搬到数学里）：$n$ 家医院 $\leftrightarrow$ $W$（接收方），$n$ 位申请者 $\leftrightarrow$ $M$（提出方），医院对申请者的偏好 $\succ_w$ 来自笔试/面试评分，申请者对医院的偏好 $\succ_m$ 来自地理位置/声誉/薪资。完整性假设：每个人对所有异性都有严格偏好序（不允许”我只想去某几家”）。这在现实中并不总是成立（有人宁可不去任何医院也不去某家差的医院），但 CS70 的模型做了这个简化——这是本讲模型的一个已知局限。

（3）临床心理学中的”匹配”（The Match）与稳定的实际价值。在 NRMP 里，稳定性意味着任何一对学生-医院都不会同时后悔。如果匹配不稳定，学生 A 和医院 H 会私下谈成协议，导致另一个学生被”挤出”、另一个岗位空缺——市场出现”震荡”。稳定性恰恰消除了这种震荡。因此 NRMP 的匹配结果一旦公布，参与者没有动机去违反。这就是官方 Note 强调的 “we want everyone to be happy enough that they all want to follow through on their final accepted offers.”

（4）谁提出，谁占优：制度设计的伦理含义（本讲最重要的现实教训）。 定理 11.5 与 11.6 合起来说的是：提出方拿到所有稳定匹配中最好的结果，接收方拿到最差的。因此 NRMP 的制度史就有了深刻含义：

• 直到 1990 年代之前，NRMP 一直是医院提出——于是匹配结果是医院最优（医院得利、学生吃亏）。
• 1990 年代角色反转，改为学生提出——于是匹配结果变成学生最优。
• 官方 Note 特别点出一个次序性教训：角色反转之所以可能，正是因为整套流程早已在计算机内部运行——现实世界里让医院”不占优”的制度根本不可能被采纳（医院谈判力远强于学生）。所以先让自动化匹配系统上线、再在系统内部反转角色，是唯一可行的改良路径。官方 Note 的原话大意是：一个非医院最优的自动匹配系统在当初根本不会被采用，那样的话”实习生最优”就永远只是空想。

（5）其他应用：Sperner 引理/校园择校（school choice，纽约、波士顿公立学校择校系统在 2000 年代改用学生提出的延迟接受算法）、肾脏交换（kidney exchange，Roth 团队）、以及更一般的”延迟接受 (Deferred Acceptance)“框架。所有这些都是 Gale–Shapley 的直接后代。

（6）算法复杂度与现实规模。算法最坏情况 $O(n^2)$ 次提议，对 NRMP 的规模（每年约 4 万申请者、数千个项目，规模不对称——属于”多对一”的医院/申请者模型，是 Gale–Shapley 的直接推广）完全可以秒解。这也解释了为什么这个 1962 年的算法至今仍在生产环境中服役。

与其他讲次的关联

• 讲次 2（Proof Techniques II，反证/逆否/分情形）：本讲的三大证明（完美匹配、稳定性、最优性）全部是反证法，尤其是最优性证明（定理 11.5）的最干净写法就是”反设算法不是最优 ⟹ 存在最早的被拒日 $k$ ⟹ 用最早性推出 $m^*$ 的最优对象位置 ⟹ 在 $T$ 中构造出流氓对 ⟹ 矛盾”。这是讲次 2 的反证法在算法领域最漂亮的范例。
• 讲次 3（Induction，归纳法与强归纳）+ 良序原理：改进引理（引理 11.2）是对”天数”的归纳，是全讲的技术支柱；官方 Note 还给出了它的良序原理版证明，并明确指出”良序原理 ⟺ 归纳法”，反证法里的 “first counterexample” 正是良序原理的直接应用。本讲的定理 11.5 也是”良序原理 + 归纳”的混合体。
• 讲次 9（Graphs，图论基础）与讲次 10（Graphs II）：稳定匹配问题的实例天然是完全二分图 $K_{n,n}$ 加边上的偏好序；”匹配”就是讲次 9 的匹配概念，”完美匹配”要求每个顶点度数为 1 的边覆盖全部顶点。讲次 10 的二分图语言与 $E\le 2V-4$ 之类结论虽不直接用于本讲，但为讨论”匹配存在性”提供了图形直觉。
• 讲次 14（Counting，计数）：完美匹配总数为 $n!$（男士的 $n$ 个配偶的全排列），本讲脚本对 $n=4$ 穷举 $24$ 个、对 $n=3$ 穷举 $6$ 个来寻找全部稳定匹配；”总提议次数 $\le n^2$”也是简单的计数上界。$n!$ 与 $n^2$ 的对比（指数级搜索空间 vs 平方级算法）是”算法为何重要”的最直观教材。
• 讲次 20（Expectations & Linearity，期望与线性性）：一个经典后续问题是”Gale–Shapley 的期望提议次数是多少”（随机偏好模型下约为 $n \ln n$），其分析正是期望线性性的应用——这是 CS70 概率部分与稳定匹配的一个自然接口。
• 讲次 26（Markov Chains & Conditional Expectation，马尔可夫链与条件期望）：延迟接受算法可以被看成”状态 = 当前保留关系”的确定性/随机过程；对随机偏好下的匹配过程做马尔可夫分析，会用到讲次 26 的工具。
• 讲次 5（Euclid, FLT, CRT）：”势函数每轮严格递减 ⟹ 有限步终止“这一终止性证明模板，与本讲终止性证明（定理 11.1）完全同型：欧几里得算法用余数递减，本讲用”未拒绝的名单项数”递减。

关键要点

1. 稳定性 = 无流氓对：不存在未配对的 $(m,w)$ 使双方都更愿意跟对方在一起。注意是双向条件——只要一方不愿意，就不构成不稳定。稳定性不唯一确定匹配：同一组偏好可以有多个稳定匹配。
2. Gale–Shapley 三条基本性质：① 一定终止（每轮至少一次拒绝，总提议数 $\le n^2$）；② 终止时是完美匹配（否则男士数 $\ge n+1$，矛盾）；③ 输出稳定匹配（由改进引理，从男士视角出发一步锁死）。
3. 改进引理是全讲的枢纽：一旦男士 $m$ 向女士 $w$ 提过申请，$w$ 此后手上的 offer 永不差于 $m$。它成立的物理基础是”offer 不会爆炸、不能被撤回“。完美匹配、稳定性、最优性三个定理全部只用它。
4. Gale–Shapley 定理（最优性）：提出方拿到所有稳定匹配中最好的对象（岗位最优 / 男士最优），接收方拿到最差的（申请者最差）。谁提出，谁得利。 想让申请者占优，就把算法改成申请者提出。
5. 良序原理 = 归纳法的孪生兄弟：反证时”取第一个反例”之所以合法，靠的是 $\mathbb{N}$ 的良序性。定理 11.5 的”取最早的被拒日 $k$”是整个证明的关键支点，去掉”最早”证明就断。
6. 两类性不可省：室友问题（同类配对）可以没有稳定匹配（四人反例，3 种配对全不稳定）。所以任何”稳定匹配必存在”的证明都必须用到”男士/女士两类”的结构。

常见误区与注意事项

1. 把”稳定”误解为”幸福”。稳定匹配不保证大家都拿到第一志愿。官方 $n=3$ 例子的稳定匹配里，Control Corp. 和 Christine 都配到了自己的最后志愿，但仍是稳定的——因为那些他们更喜欢的对象都不愿意要他们。稳定性是”没有共同改善空间“，不是”人人满意”。
2. 忘记稳定性是双向的。检验 $(m,w)$ 是否流氓对时必须同时看两边。官方 $n=3$ 的稳定匹配里，App 明明更喜欢 Anita，但 Anita 已经配了第一志愿 Bas，不愿换——所以不是流氓对。
3. 把必要条件当充分条件（最优性方向）。”$m$ 在算法中得到了对象 $w$”不意味着”$m$ 的第一志愿 $w^*$ 也可以配给他”。存在任何稳定匹配都配不到的组合（$n=4$ 例中岗位 2 与 A 就配不到，”最优对象”必须在所有稳定匹配的范围内取，而不是在整张偏好表上取）。
4. 声称”稳定匹配唯一”。$2\times 2$、$n=3$、$n=4$ 三个例子都各有两个稳定匹配（脚本穷举确认）。同时也要小心相反的错误：不是所有稳定匹配都对双方同等好——岗位最优匹配与申请者最优匹配在 $n=4$ 例中是不同的两个匹配（$S \ne T$）。
5. 忽视偏好严格性。若允许”并列”（弱偏好序），”男士最优匹配中每位男士的配偶唯一确定”就未必成立，稳定性定义也需要修正为”不存在双方都觉得对方严格更好的对”。CS70 模型里偏好是严格全序，别把它当小事。
6. 搞错算法细节导致证明失效。三个具体细节都不能改：① 男士必须严格按名单从上往下提申请（稳定性证明与最优性证明都依赖它）；② 女士手上的 offer 不能撤回、不会过期（改进引理依赖它）；③ 女士必须保留最喜欢的那个而不是先到先得（否则改进引理不成立）。把任一条改掉，本讲的结论都可能崩。
7. 误用”迭代配好流氓对”来证明存在性。这个天真算法的推理不成立：配好一对会打散两对，可能创造新的流氓对，不能保证单调改善。官方用室友问题这个反例说明该推理不可靠（它若成立会推出室友问题总有稳定解，而事实相反）。

思考题（带答案）

Q1（纯计算题）：对下面这个 $n=3$ 实例，手算 Gale–Shapley（男士提出）的逐日过程，给出最终匹配、总提议次数，并验证稳定性。

Q2（概念/证明题）：请完整证明改进引理，并说明如果允许”岗位在发出 offer 后可以撤回”，该引理的哪一步会失效、后续哪个定理首先崩掉。

Q3（概念/反例题）：请给出一个 $2\times 2$ 的例子说明”稳定匹配不唯一”，并回答：在这个例子里，男士提出的 Gale–Shapley 与女士提出的 Gale–Shapley 分别输出哪个匹配？这印证了本讲哪一条定理？

Q4（进阶/易错点）：（判断题）”若某位男士 $m$ 在算法结束时配到了女士 $w$，则 $w$ 就是 $m$ 偏好表上的第一志愿，或者 $m$ 的第一志愿把 $m$ 拒绝过。” 请判断并说明。