新泽西普林斯顿高等研究院（Institute for Advanced Study in Princeton）的经济学家马斯金（Eric Maskin）表示：“罗斯非常出色，他不仅是一位备受尊崇，要想大致了解该算法都不可饶过的机智的理论家，同时也敢于参与直接的实践。他已经通过极为巧妙的方法，在现实情境中应用了他的理论。”马斯金曾凭借市场设计领域的理论研究与他人分享了2007 年的诺贝尔经济学奖。
在伊利诺伊大学厄本那 - 香槟分校（Universityof Illinois at Urbana-Champaign）和匹兹堡大学（University of Pittsburgh）工作过一段时间后，罗斯在 1998年受聘于哈佛大学。早在1990年，他就出版了一本著作，现已被博弈论专家们广泛研读。1995年之前， 罗斯的所有工作还仅限于学术范围，而在此之后，他便将自己的理论付诸实践。罗斯首先解决的是医学院的分配问题，利用他设计的系统可以顺利地将医学院毕业生分配到全美的2.5万个住院培训岗位。
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.
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.
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.
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.
