How do you make a perfect match—between doctors and hospitals, between schools and students, and even between kidneys and patients? Lloyd Shapley and Alvin Roth have won the 2012 Nobel Prize in economics for helping to answer that question. Shapley, 89, is a professor emeritus at the University of California, Los Angeles, and Roth, 60, is a professor at Harvard University and Harvard Business School in Boston.
The Nobel committee awarded the prize to the two economists "for the theory of stable allocations and the practice of market design." Shapley pioneered theoretical concepts to understand and solve the matching problem; Roth clarified those ideas and applied them to engineer algorithms that are now widely used in the real world.
Working in the 1950s and 1960s, Shapley used cooperative game theory to explore matching. Trade between a group of rational actors, Shapley reasoned, would reach a stable state if no individual had anything further to gain by making a new trade. Along with an economist and mathematician named David Gale, Shapley applied this idea of stability to the case of marriages, setting up an example of pairing 10 women and 10 men into couples.
The two came up with a matchmaking method called the "deferred acceptance" algorithm, which could proceed in either of two ways. In one scenario, the men propose to the women, and each woman rejects the men she finds unsuitable while holding on to—but not yet accepting—the proposal she likes best. In the next round, the rejected men propose to their second-best choice, and the women again retain or choose what they view as the best offer while rejecting the rest. Over several rounds, the pairings become stable.
In an alternate scenario, the women propose to the men. This leads to a different set of pairings. Although stable matching emerges as an outcome in both scenarios, Gale and Shapley showed that the matching is more favorable to women when the women propose and vice versa. Gale died in 2008.
In the 1980s, Roth explored matching between medical interns and hospitals, and showed that the algorithm then in use by the National Resident Matching Program (NRMP)—a clearinghouse that matched residency applicants to hospitals—was successful because it followed principles similar to those encoded by the Gale-Shapley algorithm. In the mid-1990s, Roth was called upon to improve the NRMP algorithm to make matching more efficient and to better accommodate special needs such as placing dual-doctor couples in the same hospital. Roth delivered an improved algorithm, working with Elliott Peranson, the founder of the Toronto, Canada-based company National Matching Services Inc.
Roth went on to apply the Gale-Shapley algorithm to redesign the admission process used by public high schools in New York City. The new process has led to better matching between schools and students, reducing by 90% the number of students assigned to schools not on their list of preferences.
The Gale-Shapley algorithm has also been applied—with important modifications—to matching kidneys with patients. New versions of the algorithm are also now being used to conduct Internet auctions in which search companies sell advertising space. The Nobel committee's announcement of the prize this morning describes the work being honored as "an outstanding example of economic engineering."
Roth's keenness to seek out real world problems to solve makes him stand out among academic economists, Peranson says, who has been a personal friend of Roth for years and has watched him speak at university symposiums. "The Ph.D. students are very enamored with Roth because when they hear him talk, they realize, 'Not only am I studying something that's interesting, but it could have real impact.' "
Roth, who is moving to Stanford University next year, is the author of a popular blog on market design. "Blog may be delayed today," he posted on Monday morning, shortly after getting that life-changing phone call from Stockholm. "Count me as surprised."