Published on November 12th, 2012
0Why Divorces Never Happen! Nobel Prize in Economics for Theories and Applications of Matching
By Jon Olaf Olaussen, Trondheim Business School
The Nobel Prize in Economic Science 2012 winners Alvin Roth and Lloyd Shapley have both contributed to several fields of economics. This article presents the main ideas developed by Shapley in the period from the 1950s to 70s, and the ongoing development of these ideas by Roth since the early 80s as well as the numerous practical applications of their combined efforts.
1. Introduction
In 2012, Alvin Roth and Lloyd Shapley were awarded with the Nobel Prize in Economic Science. Lloyd Shapley, a mathematician specialized in Game Theory, is an Emeritus Professor at UCLA, and Alvin Roth is a professor at Stanford (having just moved from Harvard). He has a PhD in operation research and is sometimes called an engineering economist due to his focus on practical problem solving issues. In 2011, The Boston Globe wrote a profile on Roth entitled “The Matchmaker: The Harvard economist that stopped just studying the world and began trying to fix it.”
2. The GaleShapley Algorithm
So why is theory and application of matching worthy of a Nobel Prize? The simplest answer is perhaps that matching is an important aspect that affects us all in everyday life. So what is matching all about? Let us start with one of the examples provided by Shapley and Gale in an article from 1962. Consider a situation in which there are three females and three males considering getting married. Let us further say that each man and woman has well defined preferences for which partner of the opposite sex he or she prefers. This means that each man and woman is able to rank the opposite sex with respect to whom they want to marry. An unstable match is then a situation where there is a man and woman who are not married to each other but prefer each other to their actual mates. Shapley and Gale then asked, “Is it possible to find a stable set of marriages for any pattern of preferences? That is, is it possible to find a set of preferences whereby no partners would prefer each other to their actual mates are not married?” The answer turns out to be no!
To show this result, they put up a matrix of potential preferences. Let us first look at the original matrix from Shapley and Gale’s work revealing the choices of three males, α, β, and γ and three females A, B, and C.
Table 1: The original GaleShapley matrix
A 
B 
C 

α 
1,3 
2,2 
3,1 
β 
3,1 
1,3 
2,2 
γ 
2,2 
3,1 
1,3 
The first number in each cell of the table reveals the choice preference of the males, while the second reveals the choice of the females. Hence, male α prefers female A before female B and finally has female C as his last choice (it is assumed that all participants prefer being married to not being married at all). Female A on the other hand prefers male β to male γ, and has male α as her third choice. So how is this marriage market going to end? Which are the stable sets of marriages? It turns out that there are actually three stable and three unstable marriage sets. The first stable set is that all the males get their first choice (α=A, β=B, and γ=C). The second is that all the females get their first choice (α=C, β=A, and γ=B). The third stable potential solution is that everyone get their second choice (α=B, β=C, and γ=A). One very interesting aspect of this is to see which of the three stable sets we end up with. If males propose to females, the males get their first choice. If, on the other hand females propose, then females get their first choice (socalled first move advantage). In everyday life, this means that with the western pattern where males traditionally propose marriage, males are more likely than females to be satisfied with the outcome! Let us look a little further into why (α=A, β=B, and γ=C) is a stable solution even if the females end up with their least preferred mate. Female A would prefer to be married to male β and γ, rather than α. Even so, looking at her options, if she rejects α, she will not have another proposal, since both male β and γ prefer other females over A. Hence, she cannot do better than α.
Let us further consider a possibly more realistic case in which the preferences are more similar.
Table 2: Identical preferences for both females and males
A 
B 
C 

α 
1,1 
2,1 
3,1 
β 
1,2 
2,2 
3,2 
γ 
1,3 
2,3 
3,3 
Here, all the males and females have the same preferences. All the males prefer female A, all the females prefer male α and so forth. In this case, no matter who proposes, we will always end up with the only stable set of marriages being α=A, β=B, and γ=C. To show that there will always exist at least one stable set of marriages, let us now add another male, δ, and female, D, to the picture.
Note that, with equal numbers of males and females, every male or female will eventually end up getting a proposal. If there are more females than males, for example, the lowest ranked females will not get an offer, but the completed marriages will still be stable.
Table 3: Extension to four couples
A 
B 
C 
D 

α 
1,3 
4,2 
2,4 
3,2 
β 
1,4 
4,3 
2,2 
3,1 
γ 
2,2 
1,4 
3,3 
4,3 
δ 
3,1 
1,1 
2,1 
4,4 
Here, it is easily verified that the bold underlined marriages are stable, and that it does not matter if males or females propose first (which, as we have seen, is not a general result). If males propose first, females A and B both get a proposal in the first round. Female A rejects the proposal from male β, but does not accept male α yet, rather keeping him on a string to allow for the possibility that someone better comes along at a later stage (don’t we all know that feeling). For female B it is slightly different, as she gets a proposal from her first choice in the first round, and hence accepts the proposal from male δ right away. However, since male γ is rejected by female B, he now turns to his second choice, female A. She is now rewarded for keeping male α on a string as she now rejects α and rather keeps γ on a string. Or, if she is informed that her first choice δ already has married his first choice, she can just accept γ right away as she now cannot do better than her second choice, and so on. The crucial assumption here is that it is possible to keep a potential partner on a string.
Let us assume it is not possible to keep a potential partner on a string. In this case, when γ is rejected by B and turns to his second choice A he learns that she is already married to α. Moreover, to make things even worse, since β was also turned down in round one, he has turned to female C and gotten accepted, so when male γ turns to his third choice, she is already married as well, and he has to settle with his fourth choice D in a unstable (unhappy?) marriage. What if the potential partners knew that their potential second choice may already be taken if they ask their first choice first? Then we would suspect strategic behavior. It would then be likely that e.g. none of the males would go for their first choice in fear of ending up with their fourth choice, as male γ did. In fact, this is exactly the advice given to participants in such priority matching mechanism systems. For example, the guidelines for applying to the Boston Public School in 2004 claimed, “for a better chance of getting your ‘first choice’ school … consider choosing less popular schools”. Hence, if some or all of the males go for their second choice first, what would happen? Generally, we will then not end up with stable couples. To see this, just go back to Table 2 and verify that if all males ask their second choice first, and the females cannot hold males on a string, male γ would end up in a marriage with female B even if his first choice A would have been achievable. The marriage between α and B would clearly be unstable since both α and A would prefer being married to each other.
In their 1962 paper, Gale and Shapley consider two applications, the marriage problem and admission to college. How should the application process be organized to ensure that every student get into the best college they possibly can? They argue that this can be done by allowing students (or colleges) to postpone the decision to accept until all rankings are done and the students can accept the offer from the highest ranked college on their list, in a manner completely analogous to the marriage problem. With this routine, known as the GaleShapley algorithm, they proved that the outcome of this matching procedure would result in the optimal stable matching of students and colleges.
3. Extensions. The RothPeranson algorithm
The algorithm was later generalized with applications to matching at the labor market by the second Nobel Prize receiver, Alvin Roth, in 1984. In 1985, Roth showed that the marriage problem and the college admission problem are in fact conceptually distinct if at least one college accepts more than one student. He further showed that it was not always preferable for the colleges to state their true preferences. This was quite a breakthrough and a surprise, since all literature succeeding the GaleShapley paper, including that of Gale and Shapley themselves, had considered them to be analogous problems. What Roth showed was that the result from Roth’s earlier work on the marriage problem in 1984, in which he demonstrated that all participants in the marriage problem would have incentives to reveal their true preferences, would not generally hold in the college admission problem. He now showed that, following the GaleShapley algorithm, the colleges would be able to improve their set of students by not revealing their true preferences for students when allocations were being made.
In another paper from 1984, Roth analyses the problem of allocating medical interns to hospitals. The procedure was developed in 1952, 10 years before it was proved to be an optimal stable procedure by Gale and Shapley. Today this centralized clearinghouse is known as the National Resident Matching Program (NRMP). The original algorithm proposed for the medical clearinghouse by Mullen and Stalnaker in 1952 was an unstable mechanism that also made it risky for students to list their true preferences. It was replaced at the last minute with another algorithm, adapted from a prior regional clearinghouse, called the Boston Pool. This was actually employed beginning in 1952, the first year that matches were decided through the clearinghouse. This change of algorithms was not well documented, however. In fact, Gale later told Roth that he was unaware of the intern allocation process until he was told about it in 1976. Hence, one could say that the problem was already solved when Gale and Shapley developed their algorithm. In 1984, Roth went on to prove that such an allocation process produces stable matching unless married intern couples are involved. The problem of couples applying together and the general complexity of the medical intern application process increased the misbelief and pressure against the NRMP system that had prevailed since 1952. In 1995, Alvin Roth was asked to redesign the system in order to solve the allocation issue with respect to, for example, couples applying for residency together. In 1998, the new system was applied by NRMP, and Roth and Peranson showed that the new design of the system was doing better than the 1952 system. However, even Roth admits that the RothPeranson algorithm of 1999 is not bulletproof theoretically. Nevertheless, as Roth noted in 2008, this is probably negligible when it comes to practical purposes: “my understanding is that in the last ten years there have been fewer than half a dozen occasions on which no stable matching was found”
Roth has himself provided the best examples to show how the GaleShapley and RothPeranson algorithms can be applied for a number of important markets such as schoolstudents matching, organ donors and recipients, and how such systems should be designed in order to give organ donors incentives to donate and optimize the donorrecipient matches, for example. Even though the subtitle of The Boston Globe profile on Alvin Roth in 2011 (“The Harvard economist that stopped just studying the world and began trying to fix it”) may seem to be in some ways a kick in the shin to the rest of the profession, the title appears well deserved.
4. Lessons learned
What can we learn from the Nobel Prize winners? In order to improve their outcome on the marriage market, females should start proposing! It is a mathematical fact that, as long as the partner being proposed to has ice in the stomach and does not accept proposals right away, marriages will be stable! Finally, and by no means the least important, as academics, there is nothing wrong with getting our hands dirty by actually becoming involved in practical problem solving.
5. Epilogue
In addition to the problems described being interesting and important enough by themselves, both the award winners may also be viewed as founders of broader branches of economic fields. For example, in applying tools from both cooperative and noncooperative game theory, their work, especially Roth’s, may be seen as one of the most important contributions to the field of market design. Alvin Roth is also one of the main contributors to the area of controlled laboratory experiments in economics. Lloyd Shapley has had several game theoretic theorems and algorithm named after him. He is also considered one of the main founders of Cooperative Game Theory. For example, the most important singlevalued solution concept in Cooperative Game Theory is known as the Shapley value.
Further reading:
Gale, D. and L. Shapley (1962). College Admissions and the Stability of Marriage. American Mathematical Monthly 69: 915.
Kelso, A.S. jr., and V. P. Crawford (1982). Job Matching, Coalition Formation, and Gross Substitutes, Econometrica 50
Mullin, F. J., and Stalnaker, J. M. (1951). The Matching Plan for Internship Appointment. J. Medical Educ. 26: 34 l45.
Mullin, F. J., and J. M. Stalnaker (1952). The Matching Plan for Internship Placement: A Report of the First Year’s Experience. J. Medical Educ. 27: 193200.
Neyfakh, L. (April 3, 2011). The Matchmaker: The Harvard economist who stopped just studying the world and began trying to fix it, Boston Globe
Roth, A. E (1982). The Economics of Matching: Stability and Incentives. Math. Oper. Res. 7: 617628
Roth, A. E. (1984). Misrepresentation and Stability in the Marriage Problem, .J. Econ. Theory 34: 383387.
Roth, A. E. (1984). Stability and Polarization of Interests in Job Matching, Econometrica 52: 4757.
Roth, A. E. (1984). Stability and Polarization of Interests in Job Matching. Econometrica 52: 4757.
Roth, A. E. (1984). The Evolution of the Labor Market for Medical Interns: A Case Study in Game Theory. Journal of Political Economy 92: 9911016
Roth, A.E. (1985). The College Admissions Problem is not Equivalent to the Marriage Problem. Journal of Economic Theory 36: 277288.
Roth, A. E. (2008). Deferred Acceptance Algorithms: History, Theory, Practice, and Open Questions. International Journal of Game Theory. Special Issue in Honor of David Gale on his 85th birthday, 36, March, 2008: 537569.
Roth, A.E. and E. Peranson (1999). The Redesign of the Matching Market for American Physicians: Some Engineering Aspects of Economic Design. American Economic Review 89 (4): 748780.
Roth, A. E., T. Sönmez, and M. U. Ünver (2005). A Kidney Exchange Clearinghouse in New England. American Economic Review, Papers and Proceedings 95: 376380.
Shapley, L. S. (1953). A Value for Nperson Games. Annals of Mathematics Study 28
Shapley, L. S. and M. Shubik (1972). The Assignment Game I: The Core. International Journal of Game Theory 1: 111130.
1,158 Fans Like
1,157 Followers Follow