The Nobel prize for economics is often awarded for relatively abstract theoretical work. Rather less often, it is awarded for work with clear practical relevance. This year, the committee responsible for awarding the economics prize — or more precisely, the Sveriges Riksbank Prize in Economics Sciences in Memory of Alfred Nobel — has struck an impressive balance between the two. The prize has been awarded to two American economists, Lloyd Shapley and Alvin Roth, for their theoretical and practical work on matching problems. As a member of the Nobel prize committee put it, the prize is awarded this year for a “beautiful example of a sophisticated economic theorem being put to practical use”.
Matching problems arise in many cases where traditional economic markets do not do a good job of allocating resources, often because prices cannot be used. Examples include the matching of organ donors with transplant recipients and the matching of students with universities. In these cases, we cannot reply on supply and demand and the adjustment of prices to ensure that we get a desirable outcome. We need other mechanisms instead.
Lloyd Shapley is a mathematician and economist who has made numerous contributions to game theory: many theorems, ideas and concepts in economics bear his name. He is best known for his work in the area of cooperative game theory. As the name suggests, this is the study of possible outcomes in situations where groups of people (say, college students and university admissions staff) look for arrangements that are, in some precise sense, mutually satisfactory.
The challenge of cooperative game theory is that different groups of individuals can form coalitions, so it is not enough to think about cooperation by the group as a whole. The theory has to examine what different coalitions can achieve. A key notion in cooperative bargaining is known as stability. An outcome of a bargaining process is stable if it is not possible for any single individual or group of individuals to make themselves better off by going it alone.
As sometimes happens, even though the prize is officially awarded to two people, there is a third person who will be in the mind of most economists when they learn of this prize: David Gale, who died four years ago.
Half a century ago, Gale and Shapley published a paper in American Mathematical Monthly, entitled “College Admissions and Stability of Marriage”. The title makes it clear that they were inspired by practical problems, and their paper is a small marvel of simple yet elegant reasoning. There is almost no formal mathematics in it; anyone unafraid of clear logical thinking could read and understand the paper.
(As they observed in a conclusion that reads very quaintly by the standards of modern scientific publications, “any argument which is carried out with sufficient precision is mathematical, and the reason that your friends and ours cannot understand mathematics is not because they have no head for figures, but because they are unable to achieve the degree of concentration required to follow a moderately involved sequence of inferences.”)
In the paper they considered matching problems, such as the admission of students to universities or marriage matching. They began by talking about college admissions, and then moved on to the “marriage problem”. They imagined a situation where an equal number of men and women seek to marry, and where each individual can rank the members of the other sex in order of preference. They showed that there will always be a way of marrying off everyone so that the marriages are stable (in the mathematical sense!), meaning that no two individuals would prefer to leave their current partners to be with each other. There might, however, be more than one stable set of marriages.
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”.