七夕，诺奖得主用算法教你如何脱单

小莹莹

发布于 2018-04-20 07:42:04

5690

文章被收录于专栏：PPV课数据科学社区PPV课数据科学社区

七夕来袭，又到了情侣们大秀恩爱，单身狗们咬牙切齿的季节。本着人道主义关怀，先给大家唱一曲单身狗之歌——

雌雄双兔傍地走，你还是条单身狗；

两个黄鹂鸣翠柳，你还是条单身狗；

路见不平一声吼，你还是条单身狗；

问君能有几多愁，你还是条单身狗。

听完是不是很想组个复仇者联盟，早上去卖花，晚上去卖套，凌晨去卖药？

还是你认为社会资源就这么多，拆散一对是一对，于是整晚都在大街上溜达，看哪一对不顺眼就冲上去扇姑娘一巴掌然后问她“不是说你爱我吗？”

还是你打算宅在家里重播非诚勿扰，幻想自己站在台上和24位姑娘演皇上选后妃的戏码？

如果你还在琢磨这些事情，恭喜你，弱爆了。

因为获得稳定的感情不仅仅是单身狗的个人问题，更是一个数学问题和经济问题——稳定匹配问题 (stable matching problem)。针对这个问题，早在1962年的时候，两位美国数学家和经济学家 David Gale 和 Lloyd Shapley（2012年诺贝尔经济学奖得主）给出了著名的 Gale-Shapley 算法。

什么是稳定匹配？

1962年，Gale 和 Shapley 发表了一篇名为大学招生与婚姻的稳定性 (College Admissions and the Stability of Marriage) 的论文，首次提出了稳定婚姻问题，研究在一夫一妻制度下并且每个男士最终都要和一个女士结婚时，男士和女士的配对关系。这个问题后来成为研究稳定匹配的典型例子。

他们所研究的问题是要促成 n 个男士和 n 个女士之间的 n 对婚姻（所有人都是异性恋）。为了使这些婚姻稳定，我们要求所有人都把n 个异性按照自己喜欢的程度排列出来，然后根据对异性的偏好顺序来安排婚姻，最终希望找到一个稳定的匹配方案。所谓稳定匹配，满足两个条件：首先，它是一个完美匹配（所有男士都娶到了唯一的老婆，所有女士都找到了唯一的老公）；其次，它不含有任何不稳定因素（没人会离婚，没人会私奔）。

举个例子。如果我们要撮合许仙、法海、白素贞和小青四位组成两对夫妻，并且他们各自的偏好列表如下

因为只有两男两女，所以只可能有两种方案。

1.（许仙，小青），（法海，白素贞）

2.（许仙，白素贞），（法海，小青）

不管从任何角度出发，把许仙和白素贞分开都是一件残忍的事，法海他老人家因为当年干了这事，还被后人指责为不懂爱，数学当然也不会为拆散有情人提供理论依据。根据定义，第一个方案是不稳定的，原因是许仙和白素贞把彼此视为第一选择，如果强加给他们不同的配偶，在他们心里，依然把对方放在第一位，从而大大增加了出轨的可能性，所以第一个方案是不稳定的。

第二个方案是稳定的。稳定方案并不意味着每一个人都会和自己最爱的心上人在一起，在这个例子里，白素贞和小青都更加青睐许仙，但是许仙只有一个，这个时候起决定性因素的是她们各自在许仙心目中的地位。两对婚姻关系确定后，就算小青对许仙念念不忘，也只能是单相思，最多也就是在家拿法海出出气，逼他还俗、逼他吃肉、逼他减肥等等，如果小青不想单身就只能接受这段姻缘。这是婚姻关系在现实社会里的一个真实写照，并不是每个人都能和最爱的人在一起，这时候，人们的选择是自己所能追求到的最佳伴侣。

Gale-Shapley算法

根据Gale和Shapley，任何一个稳定婚姻问题都有解的，也就说至少一个方案是稳定的。具体算法如下：

(1) 确定每一位男士和每一位女士都是单身。

(2) 让每一位单身男士 m 向他名单里排位最靠前并且还没有发出过交往请求的女士 w 发出交往请求：

如果这位女士 w 单身，就接受交往请求，并把他们的状态都改为交往中；
如果这位女士已经是在交往中了，那么比较 m 和正在与 w 交往的男士m'，如果 m 比 m' 在 w 的名单里更靠前，那么 w 就会和 m 开始交往，m' 恢复单身；
如果 m' 比 m 更靠前，那么 w 就继续和 m' 交往，而 m 继续向他名单里的下一位女士发出交往请求。

(3) 当所有人都在交往中的时候，就让他们结婚吧！

如果算法读起来有点绕，那就看代码。假设 n 个未婚男士的集合 M 和 n 个未婚女士的集合 W。

再举个例子

这次出场的是唐僧师徒四人加上龙王三太子（白龙马）和中国古代四大美女西施、貂蝉、王昭君、杨玉环再加上才女蔡文姬。他们对各位异性的心仪顺序如下：

欢迎读者自行应用 G-S 算法，最后的结果是方案1：

（唐僧，西施），（悟空，昭君），（八戒，文姬），（沙僧，玉环），（三太子，貂蝉）

在这个例子中，无论是从那一个男士开始配对，或是在算法进行中改变配对顺序，得到的结果将是一样的。也就是说男士们的行动顺序对最终结果没有丝毫影响。能够影响结果的只有每个人心中的那一份排序。因此对每个男士而言，除了祈祷自己的竞争对手不要太强以外，最重要的就是提升自己在心仪姑娘心目中的地位。与其抢着出手，不如多花点时间提高自身的实力，以博得心仪姑娘更多的好感。

此外，如果有一男一女，都将对方视作第一人选，那么有情人必成眷属，比如例子中的文姬与八戒。在这种情况下，只要不把他们放在一起，就会引起方案的不稳定。所以只要我最爱的人最爱我，足矣。

在放心使用 G-S 算法之前我们还需要证明它给出的方案是稳定的。第一，这个算法是有限的，不会出现死循环或是没有结果的状况，原因是每个男士最多向 n 个女士求交往，所以最多 n*n 次请求后，算法结束。1997年，这个上界被美国数学家 Knuth 降低到 n*n - n +1。第二，证明稳定性。假设在 Gale-Shapley 算法产生的方案中有一位男士 m 向一位女士 w 求交往被拒绝，那么 w 必定正在和一位她更喜欢的男士 m' 交往，因此不可能出现 m 与 w 对彼此好感度都大于自己伴侣的可能性。

男士优先还是女士优先？

俗语有云，“男追女，隔层山；女追男，隔层纱。” 如果我们让女士们采取主动，而让男士们静候佳音，Gale-Shapley算法会不会更容易一点呢？会不会带给我们不同的结果呢？用上面的例子，这次让女士们选择男士交往，得到结果方案2：

（唐僧，昭君），（悟空，玉环），（八戒，文姬），（沙僧，貂蝉），（三太子，西施）

和男生先选的方案1进行比较 (括号里是心仪顺序)