showcraft

http://www.ecocn.org/thread-160561-1-1.html
[Free exchange] [2012.10.20] Game, set and match 博弈，设置与匹配
【导读】肾不仅仅可以卖掉换iphone，还牵扯到分配效益最大化的课题。经济学家想利用算法完成牵线搭桥的工作，让每个群体和个体的小算盘都尽量得到满足，这真的可能么？

Free exchange
自由交流版块

Game, set and match
博弈，设置与匹配

Alvin Roth and Lloyd Shapley have won this year’s Nobel for economics
埃尔文·罗斯与劳埃德·沙普利共获今年的诺贝尔经济学奖

Oct 20th 2012 | from the print edition



IN MOST countries it is illegal to buy or sell a kidney. If you need a transplant you join a waiting list until a matching organ becomes available. This drives economists nuts. Why not allow willing donors to sell spare kidneys and let patients (or the government, acting on their behalf) bid for them? The waiting list would disappear overnight.

在大多数国家，买卖肾脏都是非法的。如果你需要器官移植，就必须先加入等候者的队伍，直到有匹配的器官轮到你为止。这简直要让经济学家们抓狂了。为什么不能允许自愿捐献者出售他们可供移植的肾脏，让病人（或是政府代表他们）来竞价购买呢？这样一来等候者的名单一夜之间就会不复存在。

The reason is that most societies find the concept of mixing kidneys and cash repugnant. People often exclude financial considerations from their most important decisions, from the person they marry to the foster child they adopt. Even some transactions that do involve money are not really about price. Universities in America do not admit students based on who pays the most, for example. Rather, they select students based on complex criteria that include grades, test scores and diversity. Similarly, students choose their university on more than just financial factors.

不这么做的原因在于，多数社会厌恶把肾和钱这样的东西混为一谈。人们在做重大决定的时候往往会把与钱有关的事儿放在一边，不论是迎娶妻子还是收养孩子皆是如此。甚至于一些涉及金钱的交易也并非真正是为了价格。比如，美国的大学不会看谁付的钱最多就录取谁。相对的，他们会根据平时成绩、考试分数、有何与众不同之处等多重指标来选择学生。与之相似的，学生们也会根据经济之外的多重因素来选择他们的学校。

Money is not essential to a market. After all, economics is about maximising welfare, not GDP. But the absence of a price to allocate supply and demand makes it harder to know whether welfare is being maximised. This year’s Nobel prize in economics went to two scholars—Alvin Roth, who has just joined the economics department at Stanford University, and Lloyd Shapley, a retired mathematician at the University of California, Los Angeles—who have grappled with that very problem.

金钱并非市场的本质。说到底，经济学追求的是社会福利的最大化，而非GDP的最大化。但若没有价格来分配供应和需求，我们很难知道社会福利是否正趋于最大化。本年度的诺贝尔经济学奖授予了一直致力于解决该问题的两位学者——一位是刚刚就职于斯坦福大学经济系的埃尔文·罗斯，另一位是加州大学洛杉矶分校已退休的数学家劳埃德·沙普利。

In 1962 David Gale (who died in 2008) and Mr Shapley, now 89, published a playful paper called “College Admissions and the Stability of Marriage”. They noted the similarity between college admissions, in which students and universities are trying to pair up to their mutual satisfaction, and the marriage market, in which a fixed number of men and women are trying to find a match. In romantic comedies, each man and woman marries their own true love. In real life, some people settle for second-best, which can lead to lots of trouble. If John and Mary love each other but are married to other people, they will be tempted to leave their current partner and marry each other. But if John loves Mary, while Mary loves her husband more than John, both will stay put.

1962年，戴维·盖尔（2008年去世）和现年89岁的沙普利发表了一篇饶有趣味的论文，题为《高校招生与婚姻的稳定性》。他们指出了高校招生和婚姻市场上的相同之处：在高校招生时，学生和校方尝试配对，使双方都能满意；在婚姻市场上，固定数量的男人和女人尝试找到和自己搭对儿的人。浪漫喜剧片里的男人和女人总能找到自己的真爱。而在现实生活中，一些人只能退而求其次，从而引来种种麻烦。如果约翰和玛丽彼此相爱但却双双与别人结为婚姻，那他们就会甘愿离开现有的配偶然后两人重新结婚。但如果约翰深爱玛丽，但玛丽更爱她的丈夫，那两个人就将维持现状。

Mr Gale and Mr Shapley devised an algorithm for matching an equal number of men and women that would guarantee this second, more stable outcome. Each man and woman ranks their preferred partners. Each man proposes to his highest-ranked woman. Each woman rejects all the proposals she gets except the highest-ranked among them. But she does not accept the proposal, in case a man she prefers even more proposes next time. The algorithm is rerun until all women have a satisfactory proposal.

盖尔和沙普利设计了一种算法来为同样数量的男人和女人配对，从而确保上述情况趋于第二种、更为稳定的结果。每一个男子和女子都排出自己中意的伴侣。每位男子向自己首选的女子求婚。每位女子会拒绝求婚者中排首位男子之外的所有求婚。但如果有她更喜欢的男子会在下一次向她求婚的话，她就不会接受之前的求婚。这个算法会反复运算，直到所有的女子得到满意的结果。

Sadly, “co-operative game theory” has not yet had the opportunity to transform the marriage market. But Mr Roth spotted practical applications in other areas. In the 1940s the competition for new doctors sometimes saw hospitals making offers to students years before they graduated and thus before their qualifications were truly known. The National Resident Matching Programme was devised to match doctors to hospitals in a way that maximised their satisfaction. This programme, Mr Roth noted in a 1984 paper, was a real-life example of the “deferred-acceptance” algorithm of Messrs Gale and Shapley. The tests of a well-designed market are that participants are satisfied enough that they don’t go around it, and that there is little incentive to game the system—by, for example, lying about their preferences. This was true of the resident-matching programme, Mr Roth said.

可悲的是，“合作博弈理论”尚未有机会改变婚姻市场。但罗斯发现了该理论在其它领域的实际应用。在上世纪40年代，为了争夺新医生，有时医院在学生毕业前几年，也就是在了解他们的实际资质之前就会向其递出工作邀请。人们设计了全国住院医师匹配项目来将医生匹配至各医院，使双方都能达到最大的满意程度。罗斯曾在1984年的一篇论文中提及这个匹配项目，称其为盖尔、沙普利“延迟接受”算法的应用实例。考察一个市场是否设计完好，要看参与者是否足够满意而不需左顾右盼，而且几乎不存在让参与者在系统中博弈的刺激因素（比如瞒报自己的偏好等）。住院医师匹配项目便正是如此，罗斯说。

Other systems worked far less well. Both the New York and Boston public-school systems used to assign students according to their preferred choices, but students often had to decide before knowing all their options. Thousands ended up at schools for which they had expressed no preference. Mr Roth helped both design algorithms that significantly reduced these mismatches.

其它系统运作得远没有那么好。纽约和波士顿的公立学校系统曾根据学生自己的最优选择来为他们安排学校，但学生们往往要在得知所有可选学校之前做出决定。数以千计的学生最后匹配的是自己并不偏好的学校。罗斯协助这两座城市设计了匹配算法，显著减少了这些误匹配情况。

He also applied his expertise to organ donation. A man who would not donate a kidney in other circumstances may do so if his wife needs one. If their blood types do not match, they can be paired with a couple in the mirror-image position. The New England Programme for Kidney Exchange, which was partly designed by Mr Roth, incorporates much more complex chains of donors and recipients and raises the supply of kidneys by making a donor more confident his loved one will find a match.

罗斯同样把自己的专业知识应用到器官捐献上。一个不愿捐肾的人如果碰上自己妻子需要肾源的话就可能会捐肾。如果血型不匹配，他们可以与处于同样境地的夫妇匹配。部分由罗斯设计的新英格兰肾脏交换计划并入了更为复杂的器官捐赠者和接受者的关系链，通过让捐赠人对自己的爱人能找到匹配器官更加充满信心，从而建立起对肾脏的供应。

I love you, subject to the next algorithm
我爱你与否，要看下一个算法的结果

In time the internet could make formal matching systems viable for even more transactions. Existing systems cannot always be improved upon, however. Utku ünver at Boston College, who helped develop the kidney-exchange programme with Mr Roth, points to the allocation of law students to federal-judge clerkships. Judges have complete control over whom they hire, and many students to choose from, so there are fewer benefits to a formal clearing-house system. When economics departments hire new PhDs, their preferences are too difficult to codify in a matching system. And in many cases such systems should only facilitate transactions, not execute them. Mr Unver and his colleagues are developing a way of recommending foster children to adoptive parents in Pennsylvania, but the final decision is left to social workers and the families.

假以时日，互联网会让正式的匹配系统适用于更多的交易事务。不过，现存的系统并不总是能持续优化改善的。波士顿大学的乌特库·昂弗曾帮助罗斯开发肾脏交换计划，他以学法律的学生分配给联邦法官做办事员为证说明了这一点。法官对雇佣谁拥有完全的控制权，而且有许多学生可供选择，所以正式的信息交换系统不会带来多少好处。当经济系招收新博士生时，他们的偏好很难编写到匹配系统里。并且在很多案例中，该匹配系统应当促进交易进行，而不是终结交易。乌特库和他的同事们正在宾夕法尼亚州开发一个为领养父母推荐被领养儿童的方法，但最终的决定还是要留给社工和家人们。

In their 1962 article Mr Gale and Mr Shapley noted that their algorithm was not particularly complicated, illustrating a larger point about their discipline: “any argument that is carried out with sufficient precision is mathematical.” The recognition of Mr Shapley’s and Mr Roth’s work is also a reminder: that for all the bad press economics has received since the crisis, the discipline still brims over with insights that can solve real-life problems.

在1962年的论文中，盖尔和沙普利指出他们的算法并不是特别复杂，并阐明了一个有关其研究领域的更大的要点：“任何足够精确的论据都是建立在数学之上的”。诺贝尔奖对沙普利和罗斯的认可也给了我们提了个醒：尽管经济危机以来经济学遭受了种种责难，但这个研究领域依旧充满着能够解决实际问题的深刻见解。



Sources
College admissions and the stability of marriageby D. Gale and L.S. Shapley, American Mathematical Monthly, 1962

Stable Allocations and the Practice of Market Designcompiled by the Economic Sciences Prize Committee of the Royal Swedish Academy of Sciences, 2012

The evolution of the labour market for medical interns and residents: A case study in game theory,by A.E. Roth, Journal of Political Economy, 1984

Economist.com/blogs/freeexchange