情人节特别课堂: 稳定婚姻问题

趁着情人节的气氛,给大家介绍一个有趣的问题:稳定婚姻问题,青春期的GGMM一定要看…hehe会有收获的^^
这个问题曾在一个OIER的空间里看到过,他讲得是班级的男女生谈朋友的配对==….其实就是这个问题,可惜现在找不到那个空间了orz…不过这两天发现科学松鼠会的一篇文章我要我们在一起介绍了这个问题,于是自己修改了下,来给GGMM们上课啦,有空还准备编个程玩玩。
(PS:以前还讨论过最佳约会策略(摘取最大麦穗),也推荐青春期的GGMM去受教~~)

稳定婚姻问题The Stable Marriage Problem最早是由两个美国数学家David Gale&Lloyd Shapley于1962年在American Mathematical Monthly上提出的,这个问题和图论有关(求完全二分图的稳定完备匹配,这是一个NP问题)。对于以前没有接触过这个问题的人,这个理论最出人意外的结论是:传统的求爱、结婚过程是male-optimal(男生主动)的,也就是说,男性能够得到尽可能好的心上人,女性却不然。这里我们就不科普了,直接上问题:

给定若干个男生和同样多的女生,他们每个人都对所有的异性有一个心理的偏好次序(无并列)。具体点说就是每个男生都凭自己好恶给MM排个名次:我最爱a,其次爱b,再次爱c…同样,每个MM也同样给每个男生打分。
问题1:是否存在一种男女配对组合构成一种稳定的组合关系? 稳定组合的意思是说,不存在两个非伴侣的异性对彼此的评价比对各自伴侣的评价还要高。
问题2:在已知每个人对异性的偏好顺序的情况下,怎样求出这种稳定组合方式?(如果它存在的话)

对于以上两个的问题的答案当然是肯定的。Gale 和Shapley不但提出了这个问题本身,而且给出了一种著名的解法Gale-Shapley算法(延迟认可算法)
激动人心求婚过程是这样进行的(如果觉得太快了的话,那就认为是表白吧):
第一天,让这些男生去向他们最心仪的女生表白。等所有男生表白完毕后,所有的收到表白女生们都从自己的表白者中选择自己最喜欢的人接受为男朋友。没人表白的女生只能暂时等一等了,不要着急,表白会有的。以上过程称为“一轮”。之后的每一轮都按照类似的方式进行。
第二天还处于单身状态的男生们每个人再次向自己还没有表白过的女生中自己最喜欢的人表白(无论人家是否已经有了男朋友),然后,等所有单身男生表白完毕后,所有的收到表白女生们都从自己的表白者中选择自己最喜欢的人接受为男朋友。如果原来有男朋友而表白者中有自己更喜欢的,不要犹豫,换之。等到尘埃落定之后,再开始如上所述的新的一轮表白。
依此类推。可以证明的是,这个过程一定是会终止的,也就是说,不会陷入任何死循环。并且一旦终止,每个人都会找到一个伴侣。更关键的是,这个过程最终得到的一定是如前所述的“稳定组合”。

真正有趣的部分还在后面。一般来说,给定若干个男生女生和他们之间的偏好关系,稳定组合存在不止一种。上述“算法”只是给出了所有可能的稳定组合其中之一而已。但是这个特定的解具有某些特别的性质:可以证明,上述方式得到的稳定组合和所有其他的可能的稳定组合相比,是对男生最优而对女生最劣的。
对每个男生来说,按照这种方式最后找到的伴侣,是在所有的稳定组合中自己可能具有的伴侣中自己评价最高的(male-optimal)。比如说最后有二十个女生拒绝了他,他仍然能够得到剩下的八十个女生中他最爱的那一个。——注意这并不等于说每个男生都能追到自己最喜欢的女生,而只是说,他一定能追到“有可能和他在稳定组合中在一起的女生”中自己最喜欢的。有些女生虽然很好,但是和她在一起是不可能形成稳定组合的。这就是人生啊……
对每个女生来说,按这种方式最后找到的伴侣是在所有的稳定组合中自己可能具有的伴侣中自己评价最低的(female-pessimal)。同样的,这也不等于说每个女生都只有和自己最不喜欢的男生在一起,而只是说她最后的男朋友会是所有“有可能”的男生中自己觉得最勉强的。不过这样听起来也已经很悲惨了。

这两个结论并不直观,因为看起来在上面所描述的过程中,女生是相对占有优势的。作为男生,需要很辛苦地去不断表白,然后被拒,再表白,再被拒……而女生只要随心所欲挑选就好,而且还有随时更换男友的权利(在上面的规则里男生是不能主动提出分手的)。为什么结局会是这样?
因为如果仔细思考上面所描述的规则,会看到男生至少有一样优势——也许是至关重要的优势:他们是主动方。主动的好处是,即使一次又一次的被拒,他也仍然可以和剩下的女生中自己最喜欢的在一起。而对于女生来说,纵然有再多挑选的自由,可是一个女生也许永远也等不到自己最喜欢的男生来追自己——或者在她等到之前,游戏就已经结束了。

所以说这个问题对GGMM有指导意义的:主动方是占优的,要做”攻”不要做”受”,也许最后会失败,可是至少尝试过。

当然,这只是个理想化的模型,并不能真的用来描述爱情——数学家们还没有这么疯狂。但它确确实实有其特定的数学价值和应用背景,比如大学录取、公司招聘、医院床位安排等一类通用的two-sided matching场合……但是数学家们怎么会放过如此八卦的一个名字呢?于是它就这样流传下来了。

“情人节特别课堂: 稳定婚姻问题”的5个回复

发表评论

电子邮件地址不会被公开。 必填项已用*标注