2 From U.S. Win Nobel in EconomicsBy CATHERINE RAMPELLPublished: October 15, 2012

Two Americans, Alvin E. Roth and Lloyd Shapley, were awarded the Nobel Memorial Prize in Economic Science on Monday for their work on market design and matching theory, which relate to how people and companies find and select one another in everything from marriage to school choice to jobs to organ donations.

Their work primarily relates to markets that do not have prices. In classical economics, prices are the main mechanism through which resources are allocated. The laureates’ innovations involve figuring out how to properly assign people and things to stable matches when prices are not available to help buyers and sellers agree on matches.

Mr. Roth, 60, has put these theories to practical use, in his work on a program that matches new doctors to hospitals and more recently for a project matching up kidney donors. Public school systems in New York, Boston, Chicago and Denver, among other cities, use an algorithm based on his work to help assign students to schools. A professor at Harvard, he recently accepted a new position at Stanford.

“Al has spent the last 30 years trying to make economics more like an engineering discipline,” said Parag Pathak, an economics professor at M.I.T. who has worked on school matching systems with Mr. Roth. “The idea is to try to diagnose why resource allocation systems are not working, and how they can be engineered to produce something better.”

Mr. Shapley, 89, a mathematician and economist long associated with game theory, is a professor emeritus at the University of California, Los Angeles. He made some of the earliest theoretical contributions to research on market design and matching, in the 1950s and 1960s. He looked at why, in a free market, it was sometimes difficult for individuals to come to an agreement about proper matches.

In a paper with David Gale in 1962, Mr. Shapley explained how individuals can be paired together in a stable match even when they disagree about what qualities make the right match. The paper focused on the puzzle of marriage: that is, how mates find one another in a fair and stable way, so that no one who is already married would want (and be able to) break off and pair up with someone else who is already married.

In the 1980s, Mr. Roth applied this work to matches for medical residency programs and eventually school choice. He was interested in how to keep matches fair and how to keep more sophisticated players from manipulating the system to their advantage.

In older matching systems, a student would apply to his first choice school, which was often popular. If the student did not get in, then the application would be sent on to the student’s second choice. But if that was also a popular choce, then that school’s program would have already filled up by the time the application was even considered, and the process would repeat itself with his third choice school and so on.

Even if students were qualified to get into one of their top schools, they could be shut out because they did not rank their preferences strategically. All this gave an incentive for students to try to game the system by listing a less-popular school as their first choice — even if they really preferred somewhere else — because that way they figured they would at least have a chance of getting in somewhere.

Mr. Roth’s innovation was to develop and apply matching theory so that students would have an incentive to tell the truth about where they wanted to go. A centralized system could then assign them to a school best suited for them, based both on their own preferences and the preferences of the schools they were applying to.

The school systems he helped create use a “deferred acceptance algorithm,” which was developed by Mr. Shapley.

The algorithm works by tentatively accepting students to their top-choice school. It holds off on the final assignment until going through all the other applications to make sure there are not other students who have a higher claim to a spot at that given school (because those other students might have higher test scores, a sibling at the school, or whatever other criteria the school prioritizes) even if those students happened to rank the school lower on their list of preferences.

“The idea is to level the playing field,” said Mr. Pathak. “You want to make sure that not only do sophisticated players not have to spend the time learning the strategies and different heuristics that will get them ahead, but also that unsophisticated players are not hurt by the fact that they are not aware of all this information.”

This same sort of system is used to match new medical school graduates to medical residency programs, which was once a messy process that led to a lot of unhappy candidates. Now all residency assignments are posted simultaneously. Mr. Roth later tweaked the system to help figure out how to match married couples who were jointly looking for jobs at hospitals, an additional complication that was not accounted for in the original Gale-Shapley literature.

Mr. Roth has also helped build a system that assigns kidney donation swaps, to better allocate the scarce resources of organs and save lives.

For example, a husband in Boston may need a kidney, and his wife is willing to donate one of hers but she is not a match. Across the country there is a couple in the same position, and it turns out that the wives are a match for the husbands in the opposite couple. In this simple case, the two couples essentially barter their kidneys: wife A gives her kidney to husband B, and wife B gives her kidney to husband A. Two patients who might not have otherwise found a generous donor are saved.

It is rare that two couples will serendipitously match each other’s kidney donation needs this way, and there are often more pairs of donor-recipients involved. The longest chain of kidney recipients and donors involved 60 people, or 30 pairs.

But hospitals prefer to limit, if possible, the number of pairs involved in organ exchanges, since they cannot handle an infinite number of transplants simultaneously. Mr. Roth’s system helps find the most efficient exchange of organs so that the most patients can be saved with the fewest number of pairs involved in a given trade.

http://www.nytimes.com/2012/10/16/business/economy/alvin-roth-and-lloyd-shapley-win-nobel-in-economic-science.html