打字猴:1.700515611e+09
1700515611 当时沙普利就被这个奖项逗乐了,他说:“我认为我是一个数学家,而这个奖是颁给经济学家的。”很显然,他对委员会的决定感到惊讶,他说:“我一生中从未上过经济学课程。”但是,他编写的数学算法已经对经济和社会产生了深远的影响。
1700515612
1700515613 沙普利和盖尔一起研究的稳定婚姻问题,感觉跟前沿经济理论没什么联系,更像是一个填字游戏。为了准确地描述该问题,我们假设有性取向正常的四位先生和四位女士,并按照他们的兴趣喜好对四名异性进行排序。该算法的难点在于如何给他们配对,并实现建立稳定婚姻关系的目的。稳定的婚姻关系意味着使所有的人获得较为满意的伴侣,不应该有任何一位成员因不满意算法分配的伴侣而选择在某个时刻离开,与其他人私奔。乍一看,即便只有四对关系,也很难安排得妥妥当当。
1700515614
1700515615 我们举个实例来看看盖尔和沙普利是如何利用系统和算法的方式来保证稳定的配对关系。这四位先生分别用扑克牌中的K来表示,黑桃K、红桃K、梅花K和方块K;同样地,四位女士分别用Q来表示。每一位K和Q都列出了自己的偏好和习惯等参数。
1700515616
1700515617 对于K来说,选择方案如图4-5所示:
1700515618
1700515619
1700515620
1700515621
1700515622 图 4-5
1700515623
1700515624 对于Q来说,选择方案如图4-6所示:
1700515625
1700515626
1700515627
1700515628
1700515629 图 4-6
1700515630
1700515631 现在,假设提议每个K与同花色的Q配对。这肯定是不稳定的配对关系,为什么呢?梅花Q把梅花K列为她的末选对象,她和其他三个K在一起都会很开心。我们再来看看红桃K的列表:红桃Q是末选对象,方块Q是他的首选对象。在这种局面下,我们都可以想象到:某一日,风和日丽,梅花Q和红桃K私奔了。显然,同花色的配对关系不是稳定的婚姻方案。
1700515632
1700515633 我们该如何配对,才不会有私奔的状况出现呢?下面就是盖尔和沙普利所做的:利用多轮分析找到最终的稳定配对。第1轮中,Q都向其首选对象求婚:黑桃Q首选为红桃K,红桃Q首选为梅花K,方块Q首选为黑桃K,梅花Q首选为红桃K。似乎红桃K更受欢迎,有两个Q向其求婚。而红桃K选择他更青睐的梅花Q,所以拒绝了黑桃Q。因此,这一轮有三个待选和一个拒绝。
1700515634
1700515635 第1轮结果如图4-7所示:
1700515636
1700515637
1700515638
1700515639
1700515640 图 4-7
1700515641
1700515642 被拒绝的Q必须放弃她的首选K,并在下一轮中向她的次选对象黑桃K求婚。这时,黑桃K有两个选择,第一轮中待选的方块Q以及新求婚的黑桃Q。对于黑桃K来说,他更偏爱黑桃Q,所以他会残忍地拒绝方块Q。
1700515643
1700515644 第2轮结果如图4-8所示:
1700515645
1700515646
1700515647
1700515648
1700515649 图 4-8
1700515650
1700515651 接下来是第3轮。每一轮中被拒绝的Q都会向下一位K求婚,K们总是会选择相对更好的Q,所以这一轮,被拒绝的方块Q向方块K求婚(方块K一直孤单地等待,像是一个没有被选入足球队的孩子)。尽管方块Q在方块K的选项中排名很低,但他也没有更好的选择,因为其他三个Q更喜欢其他的K。
1700515652
1700515653 第3轮结果如图4-9所示:
1700515654
1700515655
1700515656
1700515657
1700515658 图 4-9
1700515659
1700515660 我们用了一个可爱的Q与K配对的游戏来展现这个算法。最终,每个人都配对成功,所有的婚姻关系都很稳定,很圆满的大结局!这个算法目前在世界各地广泛使用:在丹麦用于小朋友匹配幼儿园;在匈牙利用于学生择校;在纽约用于给犹太教堂分配拉比[2] ;在中国、德国和西班牙用于大学招生和学生择校;在英国被英国国家医疗服务体系(National Health Service)用于病人与器官捐赠配对,挽救了许多病人的生命。
[ 上一页 ]  [ :1.700515611e+09 ]  [ 下一页 ]