The matchmakers

The Nobel Prize in Economic Sciences for 2012 was jointly awarded to Alvin E Roth, then at Harvard University and Lloyd S Shapley, then at the University of California, Los Angeles "for the theory of stable allocations and the practice of market design".

Alvin Roth finished his undergraduate studies in operations research from Columbia University's School of Engineering and Applied Sciences in 1971. After this, he did his Masters in 1973 and PhD in 1974, in operations research itself from Stanford University. After his PhD, he taught business and economics at the University of Illinois from 1974 to 1982. In 1982, he moved to the University of Pittsburgh where he stayed till 1998. Thereafter, he joined Harvard as a professor, and moved to Stanford in 2012.

Shapley began his undergraduate studies in mathematics in 1943 at Harvard University, but had to drop out because he was drafted to serve in the US Air Force during World War II. After the war, he continued his studies and received a bachelor's degree in mathematics in 1948. He did his PhD in mathematics from Princeton University in 1953. After his PhD, he joined RAND Corporation where he had worked briefly before beginning the PhD programme. He stayed at RAND till 1981. In 1981, he moved to University of California, Los Angeles, where he was professor of economics and mathematics.

In this article, we will review the main works of Roth and Shapley and see how they are applied in various areas of public policy.

Main works of Alvin Roth

Roth's work built largely on the work of Shapley and Gale: more specifically, he applied the Gale-Shapley algorithm and its modification in a number of areas. We may recall that the algorithm was a tool to allow potential partners to find their optimal match in the marketplace. Of course, this is not the usual impersonal marketplace, where price works as the match-maker. This is the marketplace which is more personal, involving, for example, students and universities, doctors and hospitals, houses and tenants etc. The basic ideas of this matching and the stability of the marketplace was captured in the 1962 paper of Lloyd and Gale and the 1974 paper of Shapley and Scarf. In these papers, the authors used game theory to define the idea of a core: if a particular match was in the core, then the two partners couldn't do better on their own than in the marketplace. In other words, all the outcomes in the core are stable and the marketplace has to provide for stable outcomes. Roth based most of his research on these papers. The areas for which Roth was best known were: job markets, interns at hospitals, school choice and kidney transplants.

Applying the algorithm to school choice, Roth found that it provides a central clearing house for matching students to various schools and following a process of iteration, until you come to a point where there is no school-student pair not matched to each other, that would rather be matched to each other. Roth applied this to the New York and Boston public school systems. In Roth's words, the algorithm works as follows:

That is how the algorithm works. At each step, any student who has been rejected applies to his next choice. Each school looks at the people who have applied so far, keeps the best ones who have applied so far, and rejects the rest. And the algorithm stops only when no student is rejected anymore, which must eventually happen because no student applies twice to any school. When the algorithm stops, the schools finally admit all the students whose applications they are holding. That is why Gale and Shapley ('62) called this a deferred acceptance algorithm, since acceptances are deferred until the end, when all applications have ceased.

What does it mean for the algorithm to result in a stable match? It means there isn't a student and a school, not matched to each other who would rather be matched to each other. Suppose I am a student, and I end up matched to my third-choice school. The matching would be unstable if my second-choice school would rather have me than someone who they have been matched with, because I would prefer my second choice to my third choice, which is what I have got. If they also preferred me, we would be a blocking pair. We would be able to get together and produce a better match for ourselves, instead of accepting the match produced by the clearinghouse.

In matching interns to hospitals, Roth analysed the National Resident Matching Program which was set up in the US in the 1950s. It was a clearing house for interns. Roth found that the system worked according to the Gale-Shapley algorithm and provided stable intern-hospital matches. Later, in 1995, Roth improved the algorithm to accommodate medical couple interns, who wanted to be posted together. He applied this algorithm to the interns in the UK as well.

Roth also set up the New England Programme for Kidney Exchange using the same algorithm to match donors and recipients in the US. This was useful in the US, because there is no market for kidneys in the conventional sense. Roth noted that often people are stranded with incompatible partners: the donor wants to donate his kidney but his loved one can't accept it because of medical incompatibility. If there are many such incompatible partners, Roth reasoned that a modified algorithm could match the donors and recipients. And the only way to do so was by simultaneous surgeries — since there was no contracting here.

Other applications which Roth designed include a matching mechanism for fresh PhD economists with various universities and dating websites, where he suggested the use of signals by the applicants.

Ultimately, Roth was concerned with the functioning of decentralised free markets and what a market design might be. He found that well-defined rules and regulations and efficient institutions are critical ingredients of this market design.

Main works of Lloyd Shapley

Shapley was primarily a game theorist and is best known for a concept known as 'Shapley value', which he proposed in 1953. The Shapley value is nothing but the fairest distribution of payoffs in a cooperative game to players who have made unequal contributions. It may be recalled that a cooperative game is one where a coalition or group of players can make binding commitments and also define how the payoffs will be distributed. On the other hand, in a non-cooperative game, individual players negotiate to maximise their utility.

The other major contribution of Shapley, as noted above, was the Gale-Shapley algorithm, which was intended to solve matching problems such as pairing suitable mates for marriage or prospective students with high schools. The simple objective of the algorithm was to ensure that there should be no two agents who prefer each other over their current partners. In other words, the current pairing is the most optimal. We saw many more applications of this algorithm — also called the deferred acceptance algorithm. In 1974, Shapley and Herbert Scarf used the algorithm to prove that stable allocations are possible even when there are one-sided transactions.

Shapley also did a lot of work in the area of voting. In 1962, he worked on the voting power of the states in the US in a voting game called the electoral college. He also interpreted the US Presidential election as a game among millions of voters. In 1984, he collaborated with Bernard Grofman on giving weights to voters based on the likelihood of making the right decision. With Guillermo Owen, he designed a spatial game, in which voters are points in a multidimensional space.

In addition to the major works described above, Shapley was prolific in his contributions to game theory. He produced a rich body of work in complex areas, and collaborated with other game theorists such as Shubik (for the Power Index, which measures the power of players in a voting game), Aumann (for extending the Shapley value to infinite games, which was then used in analysing many financial and insurance problems captured in the book 'Values of Non-Atomic Games') and Harsanyi (to give an alternative way to divide the payoffs).

Shapley did stellar work in other areas of game theory and is rightly called as one of the 'giant figures' in game theory. As his son mentioned at the Nobel ceremony:

Over the years, my father also did important work in the development of the core, the development of stochastic games, abstract side-payment games, potential games, oceanic games, convex games, and other fields. Most of these, and the above, involve some extremely complex mathematics, a world apart from "College Admissions and the Stability of Marriage," with its simple logical reasoning. But the common thread is that he was solving mathematical problems.

Conclusion

While Lloyd laid the theoretical grounds of game theory in many complex areas as noted above, Alvin Roth applied this theory in a number of areas. Roth also paid glowing tributes to Shapley in his Nobel speech. To quote him:

We all know the wonderful image popularised by Isaac Newton, of how he could see so far only because he stood on the shoulders of giants. That image describes well how my work has built on that of my predecessors, particularly Lloyd Shapley, with whom I share this prize, and the late David Gale.

There is no doubt that the works of the two laureates have helped in various public policy areas. What started out as an exercise to match potential partners for marriage, soon expanded to areas such as education, healthcare and finance as we discussed above.

The writer is an IAS officer, working as Principal Resident Commissioner, Government of West Bengal. Views expressed are personal.