整个算法可以简单地描述为： 每个人都去做自己想做的事情 。
对于男性来说 ， 从最喜欢的女子开始追起是顺理成章的事；对于女性来说 ， 不断选择最好的男子也正好符合她的利益 。 因此 ， 大家会自动遵守游戏规则 ， 无须担心有人虚报自己的偏好 。
历史上 ， 这样的“配对游戏”还真有过实际应用 ， 并且更有意思的是 ，这个算法的应用居然比算法本身的提出还早 10 年 。
早在 1952 年 ， 美国就开始用这种办法给医学院的学生安排工作 ， 这被称为“全国住院医师配对项目” 。
配对的基本流程就是 ， 各医院从尚未拒绝这一职位的医学院学生中 选出最佳人选并发送聘用通知 ， 当学生收到来自各医院的聘用通知后 ， 系统会根据他所填写的意愿表自动将其分配到意愿最高的职位 ， 并拒绝掉其他的职位 。 如此反复 ， 直到每个学生都分配到了工作 。
当然 ， 那时人们并不知道这样的流程可以保证工作分配的稳定性 ， 只是凭直觉认为这是很合理的 。 直到 10 年之后 ， 盖尔和沙普利才系统地研究了这个流程 ， 提出了稳定婚姻问题 ， 并证明了这个算法的正确性 。
这套理论成功地解决了诸多市场资源配置问题 ， 罗伊德·沙普利也因此获得了 2012 年诺贝尔经济学奖 。 很可惜 ， 戴维·盖尔没能与他共享这一荣誉——他在 2008 年就已经离开人 世了 。
盖尔–沙普利算法还有很多有趣的性质 。 比如说 ， 大家可能会想 ， 这种男追女女拒男的方案对男性更有利还是对女性更有利呢？答案是 ，这种方案对男性更有利 。
事实上 ， 稳定婚姻搭配往往不止一种 ， 然而上述算法的结果可以保证 ， 每一位男性得到的伴侣都是所有可能的稳定婚姻搭配方案中最理想的 ， 同时每一位女性得到的伴侣都是所有可能的稳定婚姻搭配方案中最差的 。 受篇幅限制 ， 我们略去证明的过程 。
当然 ， 为了得到一种对女性最优的稳定婚姻搭配 ， 我们只需要把整个算法反过来 ， 让女孩儿去追男孩儿 ， 男孩儿拒绝女孩儿就行了 。
这个算法还有一些 局限性 。 例如 ， 它无法处理 2?? 个人不分男女的稳定搭配问题 。
一个简单的应用场景便是宿舍分配问题：假设每个宿舍住两个 人 ， 已知 2?? 个学生中每一个学生对其余 寻找一个稳定的宿舍分配？此时 ， 盖尔 2?? ? 1 个学生的偏好评价 ， 如何 –沙普利算法就不再有用武之地了 。
而事实上 ， 宿舍分配问题中很可能根本就不存在稳定的搭配 。 例如 ， 有 A、 B、C、D 四个人 ， 其中 A 把 B 排在第一 ， B 把 C 排在第一 ， C 把 A 排在第 一 ， 而且他们三人都把 D 排在最后 。 容易看出 ， 此时一定不存在稳定的宿舍分配方案 。 倘若 A、D 同宿舍 ， B、C 同宿舍 ， 那么 C 会认为 A 是更好的室友（因为 C 把 A 排在了第一） ， 同时 A 会认为 C 是更好的室友（因为他 把 D 排在了最后） 。 同理 ， B、D 同宿舍或者 C、D 同宿舍也都是不行的 ， 因而稳定的宿舍分配是不存在的 。
此时 ， 重新定义宿舍分配的优劣性便是一个更为基本的问题 。 稳定婚姻问题还有很多其他的变种 ， 有些问题至今仍然没有一种有效的算法 。 这些问题都是图论当中非常有趣的话题 。
* 本文摘自 《神机妙算：一本关于算法的闲书》一书 ， 欢迎阅读此书了解更多有关算法的内容！
推荐阅读

文章图片

《神机妙算：一本关于算法的闲书》
顾森 著 ， 蔡雪琴 绘