我来讲恋爱中的博弈,不,我来讲恋爱中的算法,不,我来讲算法!!
有个著名的问题,叫做stablematching。早年是一个可爱的俄罗斯老头在图论课上教我的,印象非常深刻,拿出来娱乐下大家。因为这个算法应用太广泛了,这个算法的两位发明人David Gale和Lloyd Shapley,在2012年因为这个算法获得诺贝尔经济学奖。
先说结论:女生遇到心动的男人一定要追!!!!!我马上就要来证明!
前方高能预警!!!含大量数学图论及计算机编程算法知识,萌妹子请直接退散。
假 设,有一个平行世界,我们姑且叫这个世界,平行世界999号,这个世界有n个男人,还有n个女人,然后每一个男人,都有一个对喜欢的女人的排序,比如男 A,有一个排序(女A,女B,一直到女N),每一个女人都有一个喜欢的男人的排序,比如女A,有一个排序(男A,男B,一直到男N)。每个男的都会试图去 追求自己的排序里头排的最高的女性,每个女的都会接受自己排序里头最高的男性的追求。
再假设这个平行世界999号,有以下追求方法(算法):
1.这个世界上只有男人能够追求女人,女人收到一个男人的追求,可以选择说“你做我男友吧”,或者“你滚犊子”。当女人说“你做我男友吧”的时候,这个男人和女人进入了男女朋友模式,当女人说,“你滚犊子”的时候,这个男人恢复单身。
2.每个男人只能在单身的时候追求女人,而每个女人最多只能有一个男朋友
3.每个男人都会追求自己名单上排位最高的女人,当被拒之后,会追求排位次高的女人,被拒之后再追第三高的女人,以此类推。每个女人,如果没有男朋友,收到追求,会立刻说,“你做我男友吧”,如果有男朋友,会将现有男朋友与追求者比较,选择其中排位更高的,甩掉排位更低的。
4.每个男人都会锲而不舍的一直把整个排序追求完,直到脱离单身状态为止。
5.当每个男的和女的都有一个女、男朋友的时候,会所有人一起结婚。
怎样,是不是和现实很像?让我喝口水继续写!
我的结论是,这个世界里头,一定会有这么一个组合,使得,这n个男的,和n个女的,会形成一个稳定的一一对应的婚姻关系。也就是说,这N个男人和女人,都合理的选择了自己名单上最高的排位的那个对象。
我说的有点乱,我先来简化问题:
一、假设这个世界上只有1个男人,1个女人;那不用想了,排什么排,去滚床单,裸奔,过没羞没躁的生活去吧。
二、假设这个世界上有2个男人(男A,男B),2个女人(女A,女B);这就开始复杂了;
如果,男A和男B的排序都是(女A,女B),女A和女B的排序都是(男A,男B)。那么很简单,男A和男B一起去追女A,男B迅速杯具,男A和女A在一起,男B和女B在一起,故事完结。
如果,男A和男B的排序都是(女A,女B),女A和女B的排序都是(男B,男A)。那么也很简单,男A和男B一起去追女A,男A迅速杯具,男B和女A在一起,男A和女B在一起,故事完结。
如果,男A的排序是(女A,女B),男B的排序是(女B,女A),女A的排序是(男B,男A),女B的排序是(男A,男B)呢,那怎么办?那么现在,男A会去追求女A,女A会说,“你做我男友吧”,男B会去追求女B,女B会说“你做我男友吧”。
于是大家都结婚了。
所以现在的组合是,男A和女A,男B和女B。
但是!!!但是!!!
你们发现了问题没有???
每个男的都追求到了自己最喜欢的女士,每个女士却只赢得了自己最不喜欢的男士!这就是这个算法的一个弊端,就是追求者,有占优的可能性。如果反过来,平行世界999里,只允许女人追求男人,会出现下面情况:
女A去追求男B,男B会说,“你做我女友吧”,女B去追求男A,男A会说“你做我女友吧”。
于是大家结婚了。
现在的组合是男A和女B,男B和女A。这同样是一个稳定的匹配。
但是!!!但是!!!现在每个女士都追求到了自己最喜欢的男士,每个男士却只赢得了自己最不喜欢的女士!!!
三、推广到N男N女,也是一样的推论。
简 单的说,就是因为这是一个单向筛选,每个男的都会确保会向自己的排序中最高的女性表白。然而男性被“滚犊子”的唯二可能性,是因为这个女性有一个她心目中 排序更高的男朋友,或者当了一段时间男朋友,但一个排序更高的男人向她表白。(当然现实中大家也懂,你就是没戏的了,而且是你本来就没戏);因此,确保了 男性一定能追求到自己喜欢的名单里头,排位最高的女性。也就是说,在这个追求关系里头,主动的那一方更能够找到自己更喜欢的异性,而被动那一方,却没有这 样的优势。
所以结论就是,妹子们,遇到喜欢的男人,一定要主动!!!!
要是说的不对,还请多指教。
来源:知乎网友尼克余
转载请注明:小康的个人主页~ » 算法说:妹子遇到喜欢的男人,要主动呀