Stable matching: Theory, evidence, and practical design
This year’s Nobel Prize to Lloyd Shapley and Alvin Roth extends from abstract theory developed in the 1960s, over empirical work in the 1980s, to ongoing efforts to find practical solutions to real-world problems. Examples include the assignment of new doctors to hospitals, students to schools, and human organs for transplant to recipients. Lloyd Shapley made the early theoretical contributions, which were unexpectedly adopted two decades later when Alvin Roth investigated the market for U.S. doctors. His findings generated further analytical developments, as well as practical design of market institutions.
Traditional economic analysis studies markets where prices adjust so that supply equals demand. Both theory and practice show that markets function well in many cases. But in some situations, the standard market mechanism encounters problems, and there are cases where prices cannot be used at all to allocate resources. For example, many schools and universities are prevented from charging tuition fees and, in the case of human organs for transplants, monetary payments are ruled out on ethical grounds. Yet, in these – and many other – cases, an allocation has to be made. How do such processes actually work, and when is the outcome efficient?
The Gale-Shapley algorithm
Analysis of allocation mechanisms relies on a rather abstract idea. If rational people – who know their best interests and behave accordingly – simply engage in unrestricted mutual trade, then the outcome should be efficient. If it is not, some individuals would devise new trades that made them better off. An allocation where no individuals perceive any gains from further trade is called stable. The notion of stability is a central concept in cooperative game theory, an abstract area of mathematical economics which seeks to determine how any constellation of rational individuals might cooperatively choose an allocation. The primary architect of this branch of game theory was Lloyd Shapley, who developed its main concepts in the 1950s and 1960s.
Unrestricted trading is a key presumption underlying the concept of stability. Although it allows clear analysis, it is difficult to imagine in many real-world situations. In 1962, Shapley applied the idea of stability to a special case. In a short paper, joint with David Gale, he examined the case of pairwise matching: how individuals can be paired up when they all have different views regarding who would be the best match.
Gale and Shapley analyzed matching at an abstract, general level. They used marriage as one of their illustrative examples. How should ten women and ten men be matched, while respecting their individual preferences? The main challenge involved designing a simple mechanism that would lead to a stable matching, where no couples would break up and form new matches which would make them better off. The solution – the Gale-Shapley “deferred acceptance” algorithm – was a set of simple rules that always led straight to a stable matching.
The Gale-Shapley algorithm can be set up in two alternative ways: either men propose to women, or women propose to men. In the latter case, the process begins with each woman proposing to the man she likes the best. Each man then looks at the different proposals he has received (if any), retains and Shapley had shown theoretically, the proposing side of the market (in this case, the hospitals) is systematically favored. In 1995, Roth was asked to help design an improved algorithm that would eliminate these problems. Along with Elliott Peranson, he formulated an algorithm, built on applicant proposals and designed to accommodate couples. The new algorithm, adopted by the NRMP in 1997, has worked well and over 20,000 positions per year have since been matched with applicants.
The research underlying the revised design prompted the development of new theory. It seemed that applicants could manipulate the original algorithm – by turning down offers which they actually preferred and keeping those which were worse – in order to achieve a better outcome. In several theoretical papers, Roth showed how misrepresentation of one’s true preferences might be in the interest of the receiving side (students in the original NRMP) in some algorithms. Drawing on this insight, the revised NRMP algorithm was designed to be immune to student misrepresentation. Furthermore, computer simulations verified that, in practice, it was not sensitive to strategic manipulation by the hospitals.