可以预见的是
很长一段时间，大家会弄混两个螺丝
本来的大热门–斯蒂芬罗斯没有获奖，这个罗斯创立了大名鼎鼎的套利定价理论。我现在看的教材就是他的。为他打抱不平！
获奖的是另一个螺丝—大家记清楚以备茶余饭后谈资
后一个罗斯的理论颇为拗口，先占楼。待续
——————————————-
再次致敬约翰纳什！这次的热点又是博弈论
下面是 我不知 百度之 环节
沙普利使用合作博弈方法来研究和对比不同的匹配方法，其关键在于保证配对是稳定的。所谓稳定，指的是不存在这样两个市场主体，它们都更中意于他人，胜过它们当前的另一半匹配对象。
沙普利和他的同事找到了所谓的GS算法(Gale-Shapley算法)。这一方法还限制了市场主体操纵匹配过程的动机。沙普利所设计的方法能系统性地对两个市场主体至少其中一方有利。
罗斯意识到了沙普利的理论和计算可让实践中重要市场的运作方式变得更清晰。在一系列的实验性研究中，罗斯和他的同事表明，为了理解某个特定市场制度为何成功，研究其稳定性是关键所在
我们定位在GS算法上，发现这个是关键，似乎别的都是废话。
好，现在上经典得不能再经典的例子
给定一组男人和一组女人，每个人在心目中都对所有的异性有一个倾慕度排序，从最喜欢到最不喜欢依次排序1、2、3。现在给出问题，如何对这些男女进行配对使得在分配好后不出现偷情的现象。
算法
可以有男人优先和女人优先两种算法。以男人优先为例，为代码如下：
1. while 存在男人m是自由的且还没对每个女人都求过婚
2. 选择这个男人m
3. 令w是m的优先表中还没求过婚的最高排名的女人
4. if w是自由的
5. （m，w）变成约会状态
6. else w当前与m1约会
7. if w更偏爱m1而不爱m
8. m保持自由
9. else w更偏爱m而不爱m1
10. （m，w）变成约会状态
11. m1变成自由
12. endif
13. endif
14. endwhile
需要特别注意的是！虽然从第9、10行来看，女人能够选择更好的伴侣。但从第3行来看，男人能够优先选择排名最高的女人。实际上，第9、10行只是为了保证婚姻的稳定性。
我们看-完代码就明白了，这个GS就是为了确保匹配稳定！
不难推出，学生入学，骨髓捐献都是这个求婚拒绝算法的扩展甚至生搬硬套
沙普利的牛逼之处，在于他证明了任意两个集合，这样的匹配总是存在的
以下是高校录取的例子
我们将看到Gale-Shapley解决高校录取问题的一个例子：
a. 假设有5个高校 U = {W, X, Z, Y, V}，每个高校只能录取4个学生，一共录取20个学生
b. 总共有20个考生，为了方便将他们按成绩排序好 S = {sA, sB, sC,…, sS, sT}
c. 每个高校对考生的偏好相同，都希望得到最好的学生，即偏好都是(sA > sB > sC … > sS > sT)
d. 每个考生对五个高校都有一个偏好排序，例如 sa 对五个学校好感度排名是 （W > X > Z > Y > V）,按照上一节的方法对偏好表扩充，变成（W1 > W2 > W3 > W4 > W5 > X1 > X2 …> V4 > V5）。
将我们的所有学生的偏好列成下面的表格：
经过我们用python语言（强烈推荐解决小问题时用此种语言）写的小程序来实现Gale-Shapley算法，最终给出了最稳定匹配如下：
学校 W 的录取名单是 （sA, sB, sD, sF）
学校 X 的录取名单是 （sC, sI, sJ, sP）
学校 Z 的录取名单是 （sE, sM, sR, sS）
学校 Y 的录取名单是 （sH, sK, sQ, sT）
学校 V 的录取名单是 （sG, sL, sN, sO）
如果Gale-Shapley算法是有效的话，那么我们可以肯定这组录取结果必定达到了“社会最优”。
So What？
搞研究的人最怕别人问：so what? 所以接下来，我们来看看结果揭示了一个什么重要启示。
首先，我们的算法是好的。因为每一位被录取的同学都能在自身成绩之上获得最大的满足：他们当中没有人被自己最不喜欢的学校录取！
其次，注意 sA, sB, sC, sD 等成绩名列前茅的同学，他们都被自己的第一志愿录取了，也就是说他们都能够去自己的dream school！ 话语权最是归牛人的，对吧？
再来看看成绩最差的两位同学，sS, ST同学成绩虽然不怎么样，但是一个被自己的第三志愿，另一个被自己的第二志愿录取了，结果还是很理想的。所以，选学校的确很重要，避开牛人们哄抢的学校是一种不错的策略。
搞清楚这个算法，大致就知道这个稳定匹配是个啥东西了。
想到了再补充 欢迎拍砖！
———————————
个人吐槽，这个理论看似很玄乎，但数学上对于这个匹配的问题似乎早有研究。而且证明唯一性从数学的角度是一个难度很低的活。这项工作也更偏实用而非理论。经济学奖颁给这个工作，我个人持保留意见。我认为套利定价是难得一见的理论，斯蒂芬罗斯更值得授予诺贝尔奖。这个奖，我只能说，约翰纳什太TM碉堡了
———————–
再补充点 从数学的角度
算法的可终止性可证：每个男人按照自己的偏爱序一个个求婚下来，一定有一个女人会要他——试想一个男人被一百个女人拒绝掉了，那他的偏爱序中已经没有人可以求婚了，所以他得不到配对，对应地对面也肯定有一个剩女，可是这个剩女曾经拒绝过他呀，也就是说她有更好的追求者呀，她怎么可能成为剩女呢？
算法的正确性也可证：假设有A男和B女私奔了。那么A在B的偏爱序中必然比B的丈夫靠前，按照算法，女人最后选择的一定是所有向她求婚的男人中她最喜欢的，这就是说A没有向B求过婚（要不然B选的就是他了）。然而，男人是按照自己的偏爱序依次求婚的，而A又喜欢B甚于自己的老婆，所以A又必然向B求过婚。推出矛盾，故不可能出现私奔。
来源：知乎 www.zhihu.com
作者：陈行
【知乎日报】千万用户的选择，做朋友圈里的新鲜事分享大牛。
点击下载
此问题还有 5 个回答，查看全部。
延伸阅读：
2013 年诺贝尔经济学奖得主 Eugene Fama、Lars Hansen 和 Robert Shiller 对于经济学的发展做出哪些贡献？
诺贝尔经济学奖得主有哪些是名不副实的？
