什么是稳定匹配
假设 n 个未婚男人的集合 M ={ m 1 , m 2 ,…, m n }和 n 个未婚女人的集合 W ={ w 1 , w 2 ,…, w n }，令 M × W 为所有可能的形如( m i , w i )的有序对的集合，其中 m i ∈ M ， w i ∈ W 。根据上述定义，我们给出匹配的概念，匹配 S 是来自 M × W 的有序对的集合，并且具有以下性质：每个 M 的成员和每个 W 的成员至多出现在 S 的一个有序对中。接下来是完美匹配的概念，完美匹配 S' 是一个具有以下性质的匹配： M 的每个成员和 W 的每个成员恰好出现在 S' 的一个对里。 S 和 S' 这两个定义的差别就是“至多”和“恰好”两个词，对很多人来说，区分这两个概念就像区分落基山大角羊和沙漠大角羊一样困难。我来解释一下，可以将 S 理解为 M 和 W 的成员配对结婚，但是 M 和 W 中不一定所有成员都能配对成功，还有剩余的男人和女人是单身。而完美匹配 S' 则是 S 的一种特殊情况，即 S' 是所有人都配对成功，不存在落单的男人和女人。
很显然，盖尔和沙普利研究的稳定婚姻问题是在一夫一妻制度下男人和女人的配对关系，每个男人最终都要和一个女人结婚。现在在完美匹配的背景下引入优先或偏好的概念，每个男人都按照个人喜好对所有女人排名，如果某个男人 m 给女人 w 的排名高于给 w' 的排名，就可以理解为 m 喜欢 w 胜过 w' 。反过来也一样，每个女人也按照自己的喜好对所有的男人排名。以上排名必须区分先后顺序，不能有排名并列的情况出现。那么什么是稳定匹配呢？ 稳定匹配 就是在引入优先排名的情况下，一个完美匹配 S 如果不存在不稳定因素，则称这个完美匹配是稳定匹配。什么是不稳定因素呢？假设在完美匹配 S 中存在两个配对（ m , w ）和（ m' , w' ），但是从优先排名上看， m 更喜欢 w' 而不喜欢 w ，同时 w' 也更喜欢 m 而不喜欢 m' ，如图 7-1 所示。在这种情况下，我们称这个完美匹配 S 是不稳定的，像（ m , w' ）这样有“私奔”倾向的不稳定对（unstable pair）就是 S 的一个不稳定因素。
图7-1 不稳定因素示意图
稳定匹配满足两个条件：首先，它是一个完美匹配；其次，它不含有任何不稳定因素。在给定的众多复杂关系中，如何求得一个稳定匹配？盖尔和沙普利在 1962 年提出的Gale-Shapley算法就是一种著名的稳定匹配算法，接下来我们就来简单介绍一下Gale-Shapley算法的原理。
Gale-Shapley算法原理
盖尔和沙普利的策略是一种寻找稳定婚姻的策略，不管男女之间有何种偏好，这种策略总可以得到一个稳定的婚姻匹配。先来看一下Gale-Shapley算法实现的伪代码：
看起来总是男人主动选择，女人被动接受，事实上这个算法并没有做这个假设。基于男女平等的原则，也可以是女人主动选择，男人被动接受，这就是这个算法常被提到的两个策略，即“男士优先”还是“女士优先”。
从Gale-Shapley算法的策略来看，男人们一轮一轮地选择自己中意的女人，女人则可以选择接受追求者，或拒绝追求者。只要女人是单身的自由状态，男人的追求就不会被拒绝，但这并不表示男人总是能选到自己最中意的女人，因为女人是可以毁约的。男人被拒绝的情况有两种，一种情况是男人追求的女人已经有约会对象，并且女人喜欢自己的约会对象胜过当前追求她的男人；另一种情况是女人面对另一个男人的追求时，如果她喜欢这个追求她的男人胜过自己当前的约会对象，女人会利用毁约的权利拒绝当前约会对象。男人每被拒绝一次，就只能从自己的优先选择表中选择下一个女人。男人不能重复尝试约会那些已经拒绝过他的女人，因此这种选择总是无奈地向越来越不中意的方向发展。每一轮选择之后都会有一些男人或女人脱离单身的自由状态，当某一轮过后没有任何一个男人或女人是单身状态时，这个算法就结束了。在Gale-Shapley算法中， n 个男人共需要进行 n 轮选择，每一个男人需要向 n 个中意对象求婚，因此，算法最多需要 n * n 轮循环就可以结束。
这个算法的流程非常简单，但是是否有效呢？也就是说Gale-Shapley算法结束后得到的一个匹配一定是稳定匹配吗？稳定匹配首先是完美匹配，其次是要求没有不稳定因素。下面我们就从这两方面分别证明一下这个算法的结果是否是稳定匹配。
首先，我们要证明Gale-Shapley算法结束得到的是一个完美匹配。直接证明这个问题比较困难，所以我们采用反证法。假设算法结束后有一个男人 m 还是单身，因为规则是一个男人只能和一个女人约会，这就意味着必定有一个女人 w 也是单身。根据算法规则，女人只要是单身，一定会接受男人的求婚，现在 w 是单身，说明 w 没有收到任何求婚请求。这时就出现矛盾了，因为根据算法流程， m 肯定是向包括 w 在内的所有女人都求过婚的，所以假设应该是不成立的，也就是说，能够证明Gale-Shapley算法得到的是一个完美匹配。
接下来证明Gale-Shapley算法的结果没有任何不稳定因素，仍然采用反证法。假设匹配结果中存在不稳定因素，也就是说，存在 m 和 w ，他们各自都已经有了伴侣，但是 m 喜欢 w 胜过喜欢自己现在的伴侣，同样， w 也喜欢 m 胜过喜欢自己现在的伴侣。但是根据算法规则， m 肯定是向 w 求过婚的，如果 w 更喜欢 m ， w 应该选择 m 而不是当前的伴侣，因此这个假设也是不成立的。
由以上证明可知，Gale-Shapley算法的结果是一个稳定匹配，也就证明了Gale-Shapley算法的正确性。
