每年凤凰花开、蝉鸣绿叶的季节，都是毕业的季节，也是同学们找工作的季节。很显然，学生和雇主之间从来都是双向选择的关系，然而学霸们往往先人一步，早早地就抓了一把offer。无奈，即便是学霸也分身无术，最终只能选择一个offer。毫无疑问，学霸们会根据自己的偏好对offer排队，选其中最好的一个。有时候我会想，其他也给了学霸offer的公司岂不是少了一个名额？显然我是多虑了，其实这些雇主公司也有一个偏好列表作为备用，如果空出了名额，他们会从这个备用的偏好队列中再选一个。但这总归不是一个最高效的资源配置方式，大量的撤销和重新选择会浪费很多社会资源。有没有一种方法，在双向选择公开透明的基础上，按照资源配置的最优原则给学生和雇主配对，直接得到一个学生和雇主之间的完备匹配或稳定匹配？ 幸运的是，确实有人在研究稳定匹配问题（stable matching problem）。戴维•盖尔（David Gale）和劳埃德•沙普利（Lloyd Shapley）就是两位这样的专家，他们从20世纪60年代就开始研究这个问题。他们最早研究的问题是稳定婚姻问题（stable marriage problem），其实这适用于所有带偏爱或优先选择的双向选择问题。本章我们就以稳定婚姻问题为例，介绍一下盖尔和沙普利研究的稳定匹配算法（Gale-Shapley算法）的原理，并给出一个解决舞伴匹配问题的Gale-Shapley算法实现。 7.1 稳定匹配问题 1962年，盖尔和沙普利发表了一篇名为“大学招生与婚姻的稳定性”[1]的论文，首次提出了稳定婚姻问题，该问题后来成为研究稳定匹配的典型例子。在介绍稳定匹配问题之前，我们先来了解几个概念。 7.1.1 什么是稳定匹配 假设n个未婚男人的集合M={m1,m2,…,mn}和n个未婚女人的集合W={w1,w2,…,wn}，令M×W为所有可能的形如(mi,wi)的有序对的集合，其中mi∈M，wi∈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的一个不稳定因素。 稳定匹配满足两个条件：首先，它是一个完美匹配；其次，它不含有任何不稳定因素。在给定的众多复杂关系中，如何求得一个稳定匹配？盖尔和沙普利在1962年提出的Gale-Shapley算法就是一种著名的稳定匹配算法，接下来我们就来简单介绍一下Gale-Shapley算法的原理。 7.1.2 Gale-Shapley算法原理 盖尔和沙普利的策略是一种寻找稳定婚姻的策略，不管男女之间有何种偏好，这种策略总可以得到一个稳定的婚姻匹配。先来看一下Gale-Shapley算法实现的伪代码： 初始化所有的m∈ M，w∈ W，所有的m和w都是自由状态; while (存在男人是自由的，并且他还没有对每个女人都求过婚) { 选择一个这样的男人m; w = m的优先选择表中还没有求过婚的排名最高的女人; if (w 是自由状态) { 将(m, w)的状态设置为约会状态; } else /*w 已经和其他男人约会了*/ { m' = w当前约会的男人; if (w 更喜爱m' 而不是m) { m 保持单身状态（w不更换约会对象）; } else /*w 更喜爱m 而不是m'*/ { 将(m, w)的状态设置为约会状态; 将m' 设置为自由状态; } } } 输出已经匹配的集合S; 看起来总是男人主动选择，女人被动接受，事实上这个算法并没有做这个假设。基于男女平等的原则，也可以是女人主动选择，男人被动接受，这就是这个算法常被提到的两个策略，即“男士优先”还是“女士优先”。 从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算法的正确性。