Perhaps more importantly, their proof also gave a practical method for finding a stable set of marriages. The key idea is that the members of one group, say the women, each make a proposal to their preferred match. Any man who receives more than one proposal rejects all but his favourite among those who have proposed. However, he does not yet accept his favourite; he waits to see what will happen next. Then the women who have been rejected propose to their second choices. At this stage, some men may prefer the new proposer to their current best option. Again, men holding multiple proposals reject all but their favourite, and so on. Eventually, this process will end up with a stable set of marriages.
Finally, Gale and Shapley showed that their procedure was optimal for those doing the proposing, in the sense that every proposer is at least as happy with the outcome of this procedure as they would be in any other stable arrangement of marriages. However, were the men to do the proposing rather than the women, then the outcome might be a different stable set, which could be less desirable for some or all of the women and more desirable for some or all of the men.
Gale and Shapley concluded as follows. “In making the special assumptions needed in order to analyse our problem mathematically, we necessarily moved further away from the original college admission question, and eventually in discussion of the marriage problem, we abandoned reality altogether and entered the world of mathematical make-believe. The practical-minded reader might rightfully ask whether any contribution has been made towards an actual solution of the original problem. Even a rough answer to this question would require going into matters which are nonmathematical, and such discussion would be out of place in a journal of mathematics. It is our opinion, however, that some of the ideas introduced here might usefully be applied to certain phases of the admissions problem.”
And this is where, about two decades later, Al Roth came in. Like Shapley, he has written a very large number of significant academic papers, but his recognition by the Nobel committee is primarily because he also went beyond the theory and applied the ideas of Gale and Shapley (as refined by himself and others) to very practical settings.
In particular, he looked at the US’ National Resident Matching Program, which matched up medical students with residency programs in hospitals. Roth discovered that this program was, in essence, using Gale and Shapley’s method, and thus was delivering stable outcomes. However, other clearinghouses that he studied, such as some that existed in regional medical markets in the United Kingdom, were not so well-designed and were not delivering stable outcomes.
Even though the US program was delivering a stable outcome, that did not mean it was a perfect mechanism. For one thing, the mechanism had been set up in a way that favoured hospitals, because they were the ones making the offers. A second concern was whether hospitals or medical students had any incentive to game the system by misrepresenting their preferences. Another practical complication was that married couples would want to obtain internships at the same hospital.
Roth was hired in 1995 to help redesign the mechanism to address these problems; in 1997 his new method (designed with Elliott Peranson) was put into place. Hundreds of thousands of medical students have now been matched through this mechanism, and many other labour markets have adopted Roth’s method.
Similar techniques have since been applied to other matching problems, such as the matching of children to schools. Roth (together with his co-authors Atila Abdulkadiro?olu, Parag Pathak, and Tayfun Sönmez) helped the New York and Boston school systems design better matching schemes; similar schemes have since been adopted by other school districts. Perhaps most strikingly, Roth also looked at the matching of kidney donors with those needing a kidney transplant, and, with colleagues, founded the New England Program for Kidney Exchange, once again improving the efficiency of matching.
Roth’s contributions go beyond these specific practical applications as well. He is a pioneer in what economists call market design: the study of how to construct mechanisms that help firms and governments solve difficult allocation problems. His insights have also provided a foundation for the design of auctions.
One of Alvin Roth’s articles is entitled The redesign of the matching market for American physicians: Some engineering aspects of economic design. Economics is not usually thought of as akin to engineering, but in the case of Roth’s practical work, building on his own contributions and those of Shapley (and, it should be said, many other distinguished economists such as Herbert Scarf, Martin Shubik, and others), the term is apt.
Roth has taken abstract economic theory and used it to make markets function in a fairer and more efficient way — and thus he has made the world a significantly better place. As the Nobel prize committee concluded, the 2012 Nobel prize in economics has been awarded “for an outstanding example of economic engineering”.
Andrew John is an associate professor of economics at Melbourne Business School.
This article was first published at The Conversation.
