74第7章稳定匹配与舞伴问题.PDF

74 第7 章 稳定匹配与舞伴问题 第 7章 稳定匹配与舞伴问题 每年凤凰花开、蝉鸣绿叶的季节，都是毕业的季节，也是同学们找工作的季节。很显然，学 生和雇主之间从来都是双向选择的关系，然而学霸们往往先人一步，早早地就抓了一把 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={m ,m ,…,m }和 n 个未婚女人的集合 W={w ,w ,…,w }，令M ×W 1 2 n 1 2 n 为所有可能的形如(m ,w )的有序对的集合，其中 m ∈M ，w ∈W。根据上述定义，我们给出匹配 i i i i 7.1 稳定匹配问题 75 的概念，匹配 S 是来自 M ×W 的有序对的集合，并且具有以下性质：每个 M 的成员和每个 W 的 1 成员至多出现在 S 的一个有序对中。接下来是完美匹配的概念，完美匹配 S是一个具有以下性质 的匹配：M 的每个成员和 W 的每个成员恰好出现在 S 的一个对里。S 和 S这两个定义的差别就是 “至多”和“恰好”两个词，对很多人来说，区分这两个概念就像区分落基山大角羊和沙漠大角 2 羊一样困难。我来解释一下，可以将 S 理解为 M 和 W 的成员配对结婚，但是 M 和 W 中不一定所 有成员都能配对成功，还有剩余的男人和女人是单身。而完美匹配 S则是 S 的一种特殊情况，即 S是所有人都配对成功，不存在落单的男人和女人。 3 很显然，盖尔和沙普利研究的稳定婚姻问题是在一夫一妻制度下男人和女人的配对关系，每 个男人最终都要和一个女人结婚。现在在完美匹配的背景下引入优先或偏好的概念，每个男人都 按照个人喜好对所有女人排名，如果某个男人 m 给女人 w 的排名高于给 w 的排名，就可以理解 4 为 m 喜欢 w 胜过 w 。反过来也一样，每个女人也按照自己的喜好对所有的男人排名。以上排名 必须区分先后顺序，不能有排名并列的情况出