稳定匹配

这篇文章将介绍一个1962年提出的经典算法问题：稳定匹配。

1. 问题起源

在1962年，经济学家 David Gale 和 Lloyd Shapley 提出：能否设计一个高校录取过程，能够自我执行（self-enforcing）形成一个最佳的匹配效果。

算法的 C++ 实现代码请移步 Github：https://github.com/hotelll/CS222Note/tree/master/StableMatching

2. 问题描述

给出一个 $n$ 个男性的集合 $M$ 和 $n$ 个女性的集合 $W$，找到一个“稳定”匹配。

• 每位男性根据对女性的心仪程度从高至低进行排名；

• 每位女性根据对男性的心仪程度从高至低进行排名。

3. 名词定义

3.1 匹配

匹配 $S$ 是一个包含有序数对 $m-w$ 的集合，其中 $m\in M$ 且 $w\in W$，其中：

• 每个男性最多出现在一个数对中；
• 每个女性最多出现在一个数对中。、

3.2 完美匹配

如果$|S|=|M|=|W|=n$，则匹配 $S$ 是完美匹配。

3.3 不稳定对

给出一个完美匹配 $S$，男性 $m$ 和女性 $w$ 是不稳定的，如果同时满足下列条件：

• $m$ 相比起当前配偶，更喜欢 $w$;
• $w$ 相比起当前配偶，更喜欢 $m$。

3.4 稳定匹配

一个不包含不稳定对的完美匹配。

3.5 正当配偶 Valid Partner

如果存在一个稳定匹配中男性 $m$ 和女性 $w$ 匹配在一起，则称女性 $w$ 是男性 $m$ 的正当配偶。

3.6 稳定匹配问题

给出 $n$ 个男性和 $n$ 个女性的喜好列表，寻找一个稳定匹配。

注意事项： 稳定匹配不一定存在，同时也不一定是唯一的。

4. Gale-Shapley 算法

4.1 伪代码实现

4.2 算法性质

4.2.1 总体设计

• 男性根据喜好降序向女性求婚；

• 一旦一位女性找到配偶，她将不会再单身，只会替换成更好的。

4.2.2 有穷性：算法最多在 $n^2$ 次 while 迭代后一定会结束。

证明：

while 循环中每次男性向一位女性求婚，最多只有 $n^2$ 次求婚。

4.2.3 完美性：算法中所有男性和女性都匹配完毕。

证明（反证法）：

• 假设：存在男性 Z 在算法终止后仍然未匹配到女性

• 由此可知，一定有一位女性，假设为 A，也没有匹配到男性

• 根据算法，一位单身女性一定会同意向她求婚的男性，且女性一旦有配偶就不会再次单身（特征2），所以女性 A 一定没有被求过婚

• 根据算法 while 循环条件，男性 Z 一定向所有女性求过婚算法才会终止

• 因此男性 Z 向女性 A 求过婚

• 3与5产生矛盾，假设不成立，证明完毕

4.2.4 稳定性：算法产生的匹配中，不会有不稳定对

证明：

• 假设：GS 匹配 $S^*$ 不包含数对 A-Z

• 情况1：Z 从未向 A 求婚

  • Z 比起 A 更喜欢 GS 算法得到的配偶 B
  • A-Z 是稳定对

• 情况2：Z 向 A 求过婚

  • A 拒绝了或抛弃了 Z
  • A 比起 Z，更喜欢 GS 算法得到的配偶 Y
  • A-Z 是稳定对

• 因此 GS 匹配中不包含的对一定是稳定的，即GS匹配中没有不稳定对

4.2.5 男性最佳分配 Man-optimal Assignment

GS 算法中每个男性都能分配到最佳的正当配偶，所以 GS 算法得到的分配一定是男性最佳分配。

证明：

• 假设：一位男性与一位女性匹配，该女性不是最佳正当配偶
• 因为男性根据喜好降序求婚
  • 所以有男性在 GS 算法中被正当配偶拒绝
• 令 Y 是第一个这样的男性，同时令 A 是第一个拒绝他的正当配偶
• 令 $S$ 是一个包含 A-Y 的稳定匹配
• 在 GS 中，当 Y 被 A 拒绝时，A 与男性 Z 配对
  • 所以，A 比起 Y 更喜欢 Z
• 在 $S$ 中令 B 是 Z 的配偶
• GS 中，Z 在 Y 被 A 拒绝的时候，还没有被任何正当配偶拒绝（因为我们令 Y 和 A 是第一对这样的男女）
• A-Z 和 B-Z 都是正当配偶，现在已知在 GS 中 Z 与 A 配对
• 如果 Z 在向 A 求婚时，如果已经向 B 求过婚，一定被拒绝了，上上条矛盾
• 因此，当 Z 向 A 求婚时，他还没有向 B 求过婚
  • 所以，Z 比起 B 更喜欢 A
• 因此，A-Z 在 $S$ 中是不稳定的。
• 因此假设不成立，GS 算法是男性最佳策略

4.2.6 女性最劣分配

GS 算法中女性一定分配到的是最差的正当配偶。

证明：

• 假设： A-Z 在稳定匹配 $S^*$ 中匹配，但是 Z 不是 A 的最差正当配偶
• 那么，存在稳定匹配 $S$，其中 A 与 Y 配对，且 Y 是更差的正当配偶
• 所以 A 比起 Y 更喜欢 Z
• 在 $S$ 中，令 B 是 Z 的配偶，根据男性最优性，A 是 Z 的最佳正当配偶
• 所以 Z 比起 B 更喜欢 A
• 因此，A-Z 在 $S$ 中是不稳定对，存在矛盾

关键：主动发起求婚的一方总是获得优势。