Gale-Shapley 算法用于寻找一个二分图（bipartite graph）的稳定匹配（stable matching）。该算法不但给出了稳定匹配的存在性证明，同时给出的匹配拥有一些最优化性质。这是一个经典的算法问题，经常会被算法课老师拿出来讲，正好做一下笔记给有需要的人。
问题描述
其实有三种比较经典的问题描述，不过都是套了同一个皮，我们就以医院和病人举例描述问题。
有 N 个医院和 N 个病人，每个医院对于 N 个病人有一个“倾向排序”，每个病人对于 N 个医院也有一个“倾向排序”。一个完美匹配（perfect matching）是说，医院和病人之间两两匹配，形成不相交的 N 对组合。
现在用一个例子简单消化一下已经提到的概念：假设医院是A、B、C，病人是X、Y、Z，并且他们的“倾向排序”列表如下。
| 医院 | 1st | 2nd | 3rd |
|---|---|---|---|
| A | X | Y | Z |
| B | Y | X | Z |
| C | X | Y | Z |
| 病人 | 1st | 2nd | 3rd |
|---|---|---|---|
| X | B | A | C |
| Y | A | B | C |
| Z | A | B | C |
表中靠左表示“更加倾向”，假设一个匹配 M={A-Z, B-Y, C-X} （在表中用黑体字表示），由于ABC与XYZ各只出现了一次，因而是一个完美匹配。
一个组合<P-Q>是不稳定对（unstable pair）当且仅当：
- <P-Q’> ∈ M，并且对于P来说，Q优先于Q’
- <P’-Q> ∈ M，并且对于Q来说，P优先于P’
例如表中的<A-Y>（表中用下划线表示）就是一个不稳定对。直观理解就是，如果一个组合，在两张表中均处于黑体字的左侧，这个组合就是不稳定对。
理解上述概念之后，就不难理解：稳定匹配是一个不包含不稳定对的完美匹配。
Gale-Shapley 算法
这是一个生成稳定匹配的算法。我们先抛开对于上述定义性质的疑问，例如稳定匹配是否唯一或者是否存在等等，先引入这个算法，之后解释和证明会容易理解很多。
算法伪代码：
INIT: M = {}
WHILE (存在一个医院h尚未匹配到对应的病人 ∧ h尚未征召所有病人)
p0 <- h的“倾向列表”中第一个未被h征召的病人
（h对p0进行征召）
① IF (p0尚未被匹配)
M = M ∪ <h, p0>
② ELSE IF (<h0, p0>在M中 ∧ 对p0来说h>h0)
M = M \ <h0, p0>
M = M ∪ <h, p0>
③ ELSE
p0 拒绝了 h（无事发生）
RETURN M
注意用①、②、③标记了三个分支，用于解释后续证明。
算法性质
有穷性
这个算法一定会终止。
当所有医院h对每一个病人p都进行一次征召之后，循环将会结束，至多执行n^2次征召过程。
完美性
算法产生的结果一定会使得所有医院和病人都获得匹配。
证明（反证法）：
如果某个医院h0未被匹配，那么一定存在一个病人p0也未匹配。
算法过程显示：
- 如果一个病人获得了匹配，那么他将不会失去匹配；
- 如果一个病人没有被匹配，并且被某所医院征召，那么他会获得匹配
所以p0一定未被征召过，包括：p0未被h0征召过。
而h0会征召所有未被匹配的病人，产生矛盾。
稳定性
算法会产生一个稳定匹配。
对于任何不在M中的对<h, p>：
- h从未对p征召过
- 那么h的匹配病人p_left一定在p之前（因为h是按照倾向度降序征召的）
- 因而<h, p>不是不稳定对
- h曾经征召过p
- 如果征召的时候p尚未匹配，那么<h, p>将会临时在M中，随后h被替换成对p来说更优先的h_left
- 如果征召的时候p已经被匹配，那么：
- h可能比现有p的匹配h_right要优先，<h, p>会顶替<h_right, p>出现在M中，但是由于<h, p>最终也没有出现在M中，所以一定有<h_left, p>顶替了<h, p>，因而<h, p>不是不稳定对
- p的现有匹配h_left已经优于h，那么之后p的匹配也只会换成更优先的h_left_left而不会降级，因而<h, p>同样也不是不稳定对
通过排除法说明了所有不在M中的对都不是不稳定对，那么根据定义，M就是一个稳定匹配。
最佳与最劣分配
首先认识到一点，对于一组“倾向排序”，稳定匹配不一定是唯一的。
| 医院 | 1st | 2nd | 3rd |
|---|---|---|---|
| A | X | Y | Z |
| B | Y | X | Z |
| C | X | Y | Z |
| 病人 | 1st | 2nd | 3rd |
|---|---|---|---|
| X | B | A | C |
| Y | A | B | C |
| Z | A | B | C |
S1 = {A-X, B-Y, C-Z}
S2 = {A-Y, B-X, C-Z}
可以很容易验证S1与S2是上述“倾向排序”的两个不同的稳定匹配。
但是，不论以什么顺序遍历医院，Gale-Shapley算法产生的M是唯一的。
并且这个匹配M，一定是对医院来说的最佳匹配（hospital-optimal），并且是对病人来说的最劣匹配。
先简单介绍一下什么叫最佳匹配。首先需要引入一个概念叫正当搭档（valid partner）。
正当搭档：对于一组“倾向排序”，如果存在一个稳定匹配，h与p匹配在一起，那么就说h与p在这组“倾向排序”下互为正当搭档。
最佳匹配：上述例子中，医院最佳匹配说的是，每一个医院在GS算法产生的结果M中，均能匹配到自己最倾向的正当搭档。
证明（反证法）：
- 假设：存在一个医院没有匹配到自己的最佳正当搭档。
- 由于每个医院在征召过程中根据倾向降序进行遍历征召，所以一定有一个医院在征召过程中被正当搭档拒绝。
- 注意这个拒绝有两种情况：一种可能是走了分支②，在临时匹配到其搭档后，搭档匹配到了更优的搭档；另一种是走了分支③，对其征兆时，搭档已经与更优的搭档匹配。
- 假设算法执行产生的结果记作M。H与P是第一对走了分支②或③的正当搭档，再次强调是正当搭档。
- 分支②：<H, P>原本在临时结果Mt中，而H_left征兆到了P并抢走了P
- 分支③：<H_left, P>原本在临时结果Mt中，而H在征兆P过程中被P拒绝
- 这两种情况都可以得出推论，在P的“倾向排序”中，H_left优于H
- 因为<H, P>是正当搭档，所以存在另一个稳定匹配M*包含<H, P>
- 继续讨论第一对正当搭档走了分支②或③并处理完的时点
- 最终Mt留下了<H_left, P>，P“拒绝”了H，H_left优于H
- 在M*中也会有一个P0与H_left匹配。
- 即<H_left, P0> ∈ M*，那么自然H_left与P0也是一组正当搭档
- 考虑H_left的征召顺序
- 如果H_left在此（就是发生第一次拒绝的时点）之前已经征召过P0，那么一定会被同意，因为现在正当搭档之间没有被拒绝的情况。
- 但是进一步想，在此（第一次拒绝的时点）之前均没有任何正当搭档被拆散，那么<H_left, P0>就会保留到这个时点，可是这个时点H_left与P匹配，产生矛盾
- 结论：H_left在此（第一次拒绝的时点）之前尚未征召过P0
- 推论：因为H_left也是按照降序征召，那就说明对H_left来说P优先于P0
- 观察划线的两个推论，通过定义就知道<H_left, P>在M*中是一个不稳定对，矛盾
同样，Gale-Shapley算法会产生病人最劣匹配，通过之前最优匹配的结论可以推出。
证明（反证法）：
- 如果<H, P>在M中匹配，但是H不是P的最差搭档
- 那么P应该有一个更差的搭档H_right，<H_right, P>属于某个稳定匹配M*
- 对P来说，H优于H_right
- 假设<H, P0>在M*中
- 由于<H, P>在M中，所以P是H的最佳匹配，所以对于H来说，P优于P0
- 因而<P, H>在M*中是一个不稳定对，矛盾