2012诺贝尔经济学奖理论(速配算法).pptVIP

* 罗伊德·沙普利（Lloyd S. Shapley ），1923年6月2日生于美国麻省剑桥，是美国杰出的数学家和经济学家。毕业于普林斯顿大学与哈佛大学，任美国加州大学洛杉矶分校数学和经济学名誉教授，对数理经济学、特别是博弈论理论做出过杰出贡献，被很多专家认为是博弈论的具体化身。沙普利使用合作博弈的方法来研究和比对不同的匹配方法。埃尔文·罗斯意识到了沙普利的理论计算结果可以让实践中重要市场的运作方式变得更清晰，并成功地通过系统性的实验室实验支持了这个结论。 埃尔文-罗斯（Alvin E. Roth），生于1951年12月19日，是一位美国经济学家，目前在哈佛商学院担任经济及工商管理乔治-冈德（George Gund）教授。罗斯在博弈论、市场设计和实验经济学领域都曾作出重大贡献。 获奖者简介 获奖原因 主要是奖励他们在“稳定匹配理论和市场设计实践”方面的贡献。 他们研究什么？什么是匹配问题？ 今年的经济学奖是理论和应用完美结合的一个典型例子 。 　1962年，David Gale(已经去世) 和Lloyd Shapley提出了下面的问题：“给定若干男生和若干女生(数量相同)，他们每个人都对所有的异性有一个稳定的偏好排序。是否存在一种男女匹配组合构成一种稳定的组合关系？” Gale和Shapley提出了一种名为“延后接受”（deferred acceptance）的方法，能够达到“妙点鸳鸯谱”的功用，解决N男N女“速配” 问题。该算法被称为GS算法。 是合作博弈论的世界头号人物，为经济学理论和博弈论做出了基础性的贡献，对于理解竞争行为及其博弈的理论支撑起到了核心的作用。 罗斯从1995年应用理论改革美国医学院毕业生分配体系开始，他一直着手于解决现实问题。将这里的男女换成医生和医院、工作岗位和员工、学生和学校、课程和老师、研究员和行业、病人和人体器官，等等都完全适用。 是少见的既有精深理论贡献，又非“纸上谈兵”的经济学家 。 开创一门新学科——设计经济学 。 完美结合 不妨借“非诚勿扰”来解释这种让N男N女“速配”成功的GS算法： 第一轮，每位男生都向自己最倾心的女生“亮灯”——即向她提出要约：求婚；女生们选择为自己亮灯的男生中最有好感的，并拒绝其他人。 第二轮，还处于单身状态(也就是被拒绝过)的男生们，每个人再次向自己还没有求过婚的女生中自己最喜欢的人求婚(无论自己喜欢的女生是否已经有男朋友)。所有收到求婚的女生们现在从自己的求婚者中选择自己最喜欢的人接受为男朋友。如果原来有男朋友但现在的求婚者中有自己更喜欢的，则拒绝原来的男朋友，选择现在自己更喜欢的求婚者。 第三轮(如果有的话)还是按照这样的规则来。一直进行到不再有男生求婚了为止。然后所有被接受的男生和接受他的女生结婚。如果有剩下的单身男生和单身女生，那么他们仍然保持单身。匹配过程全部结束。 理解GS算法——“延迟接受算法”（deferred-acceptance algorithm） 该算法一个关键之处在于，合意的要约不会立即被接受，而只是被“抓住”（hold on to），也就是“延迟接受”。 要约被拒绝后，男生才可以向另一名女生发出新的要约。 整个程序一直持续到没有男生再希望发出新的要约为止，到那个时候，女生们才最终接受各自“抓住”的要约。 以上匹配是稳定的：在匹配过程中，每个男生首先向被自己列为第一位的女生发出要约，也就是最想结婚的那个女生。如果这个要约被拒绝，该男生才能向被自己列为第二位的女生发出要约，依次类推。因此，在该算法的操作中，男生的预期随着要约对象所处偏好排序降低而下调（当然，男生不会对不可接受的女生发出要约）。反过来说，由于女生总是抓着所接收要约中最合意的那个，且要约不能被撤回，因此每个学生的满意度在该算法的操作中是单调递增的。 女 男 假定有三医生(1、2、3)和三医院(a、b、c)，医生1和医生2的偏好排序相同，都是a、b、c；医生3的排序是医院a、c、b；医院a的偏好依次是1、2、3；医院b的偏好排序依次是1、3、2；医院c的偏好排序是1、2、3。 　　假定是医生开始求职，医院只考虑接受与否。第一轮，医生1、2、3都向医院a求职，医院a接受医生1，拒绝2和3。第二轮，医生2向医院b求职，医生3向医院c求职。医院b和医院c分别接受医生2和医生3的求职。　　匹配结束。最终匹配结果是医生1和医院a、医生2和医院b、医生3和医院c。 * * *