Matching Theory Rightly Matches Lloyd Shapley and Alvin Roth with Nobel Prize

On October 15, 2012, the Royal Swedish Academy of Sciences announced that Alvin Roth of Harvard Business School, and currently a visiting Professor at Stanford University, and Lloyd Shapley affiliated with departments of Mathematics and Economics of University of California, Los Angeles, have jointly won the 2012 Nobel Prize for Economics.

Though it has by now become a common practice of the Academy to award Nobel Prize jointly to two or more than two academicians, interestingly, this year’s pairing is cheered by everyone for it is quite apt since both the awardees have made their name by developing theories of “stable allocations and the practice of market design”, though independently and at different periods of time.

Lloyd Shapely is a grand old man of game theory—that part of economics which deals with strategic decision making which was brought into limelight by John von Neumann and became popular in the field of economics after World War II—making his presence felt quite often across the spectrum of economics with his fundamental contributions to economic theory and game theory ever since he took his PhD from Princeton University in the year 1953. His thesis and postdoctoral work that introduced ‘Shapely value’—the payoff that each agent participating in a cooperative game gets—and the ‘core’ solution has become central to the modern understanding of competitive behavior and its game theoretic underpinnings. This paper, “A Value for N-Person Games”, has been enormously influential by virtue of the widespread use of the Shapley value in several fields and also the inspiration it created in others to come up with newer values by tweaking the Shapley’s original axioms.

That aside, the development of the concept ‘core’—an allocation is said to be in the core if no coalition can improve on its members’ utilities—which is today the most commonly used cooperative solution concept in economics, has made economists believe that game theory provides a useful set of tools for analyzing economic problems. This was followed by another important paper in 1967—“On Balanced Sets and Cores”—in which Shapely introduced the notion of “balanced”, which remained a key notion to this day for understanding when games have nonempty cores. 

Now coming to his prize-winning work, it is his seminal paper, “College Admissions and the Stability of Marriage”, which he published in 1962 along with Gale studying matching games with nontransferable utility that won him the day. The central idea of this game theory is that a group of many pairings will be stable, if nobody in any pair has any incentive to square off with anyone else. For instance, let us assume there are two sets of agents, say workers and employers that are to be paired with each other. Presume a particular worker ‘A’ from the set is hired by the employer ‘X’, but A prefers to be employed by ‘Y’. And also presume that employer ‘Y’ too likes to employ ‘A’, but did not.  This situation, Shapely says, would result in unexploited gains from trade.  On the other hand, if A had been hired by Y, both of them would have been better off.  And according to Gale and Shapley, such a pairing would become stable, for there remained no unexploited gains from the trade.   

In an ideal market, workers and employers might work for such stable outcomes, provided they have unrestricted time and ability to make deals. But real-world markets are different from this.   It is to overcome this limitation, Gale and Shapley devised a “deferred acceptance algorithm” for finding a stable matching. To understand its functioning, let us take the example of hospitals as one set of agents of the market and medical students seeking internships as the other set. Now, presume that the hospitals make offers to medical students. Each student evaluates the offer that he received and holds on to the one that he prefers and rejects the rest. The critical element of this whole algorithm is that the desirable offer is not accepted immediately by the student but he simply holds on to it: deferred acceptance. The hospital whose offer was rejected by a student can make a new offer to a different student.Of course, hospitals enjoy the right not to issue an offer to an unacceptable student.This procedure continues till there is no hospital wishing to make another offer. It is at this time that the students accept the proposals they hold.

This way, each hospital starts offering internship to the best student it wants to hire, and in case it is rejected, it then makes an offer to the next best student. As this process is continued, the operation of the algorithm lowers the hospital’s expectations further and further down till its requirements are met. Conversely, since students always hold on to the most desirable offer they have received and as the hospitals cannot withdraw the offer once made, students’ satisfaction too monotonically increases as the algorithm operates. Thus Gale and Shapley proved that their deferred-acceptance algorithm will always produce a stable matching. As Shapley claims, this algorithm can be applied to any market such as school admissions, even to mass weddings. It is this algorithm that won him the Nobel for Economics, though Shapley considers himself “a mathematician” and claims to have “never, never in my life took a course in economics.”

It is about twenty years later, Alvin Roth, with a PhD in Operations Research from Stanford University, noticing that something very close to Gale and Shapley's algorithm is in fact being used in the US market for new doctors, undertook an empirical investigation and came up with an article in 1984, clarifying how the concept of stability provides an organizing principle which enables us to understand why markets sometimes work well and sometimes fail. Using this frame work in combination with empirical studies, controlled laboratory studies and computer simulations, Roth studied the functioning of markets and, based on these findings and using Gale and Shapley algorithm in modified/improved form, came up with newer institutions that help markets function better. Thus emerged a new branch of economics: Market Design

.

Designing a new algorithm—applicant-proposing deferred-acceptance algorithm—which is not only fully incentive compatible for the applicants, but also applicant optimal, Roth solved the most daunting problem of matching New York City public high schools with the preferences of students to the satisfaction of all the parties involved in 2003, and the Boston public school system in 2005.

Lloyd Shapley’s work on cooperative game theory has strengthened its theoretical foundations besides enhancing its utility in policy making. Launching the theory of matching markets, Shapley hoped that one day it would have practical applications. His hope has been fulfilled by subsequent researchers, notable among them being Alvin Roth. These two game theorists, Lloyd Shapley and Alvin Roth, having thus made socially enriching contributions, richly deserve the Nobel.