PERFECTLY MATCHED PAIR - The Nobel prize in economics

An SMS doing the rounds states “Juicy hamburgers for $6 only. Nobel Peace prize thrown in for free.” This is of course a sarcastic comment on the award of this year’s Nobel Peace Prize to the European Union, and reflects the sense of disbelief which most of us felt when we heard about this particular award. Of course, we should have not been so surprised. After all, the peace prize has also been awarded to a well-meaning but completely untested individual not so long ago — President Barack Obama in 2009. Clearly, the Nobel Peace Prize has been devalued quite sharply.

Fortunately, the committees responsible for awarding the other Nobel prizes have almost always chosen very deserving candidates. This is certainly true of this year’s prize for economics, which has been awarded jointly to two Americans, Lloyd Shapley (picture, right) and Alvin Roth (picture, left). In fact, the award to Shapley rights a wrong committed against him at least once if not twice. The prize in 2005 went to Robert Aumann and Tom Schelling “for having enhanced our understanding of conflict and cooperation through game-theory analysis”. The omission of Shapley from the list of winners raised many eyebrows because Shapley has been the principal architect of modern cooperative game theory, which is, loosely speaking, the study of what outcomes can be expected to emerge when individuals decide to cooperate instead of indulging in cut-throat competition. In fact, aficionados of cooperative game theory were quite disappointed much earlier when John Nash of Beautiful Minds fame and two others were jointly awarded the prize in 1994 for their contributions to the other (but admittedly more popular) branch of non-cooperative game theory.

Unlike in other disciplines, the Nobel prize in economics has seldom been given to an individual for a single paper or piece of work, notable exceptions being Kenneth Arrow for his fundamental contribution to social choice theory and John Nash, whose equilibrium concept laid the foundation for non-cooperative game theory. Shapley, too, belongs to this rare breed. In a paper written as early as 1953, he derived the notion of what has come to be called the Shapley value. This has become the overwhelmingly dominant prescription of what is a fair way of distributing the surplus from cooperation.

Quite surprisingly, the Nobel citation for Shapley does not mention the Shapley value. Instead, the citation mentions that Roth and Shapley have been jointly honoured for their work on matching theory or what has now come to be called market design. This body of economics primarily applies to situations where different agents, institutions or even objects have to be matched or assigned to one another without recourse to prices and through a centralized procedure. For instance, students are assigned to schools or colleges or medical interns are matched to hospitals through centralized matching procedures in many countries (though not India). A more striking example is the procedure to assign donor organs such as kidneys to patients. Can algorithms be designed so as to ensure that the outcomes are bilaterally stable in the sense that no two individuals would want to discard their current partners and want to match with each other? Can we ensure that no agent has an incentive to lie about his or her preferences in order to secure a more preferred outcome? These are some of the issues which are central to the burgeoning field of market design.

This area of research was initiated by Shapley in a remarkably elegant paper written in 1962 with the late David Gale, a mathematician in the University of California, Berkeley. They developed what has come to be called the deferred acceptance algorithm. In this algorithm, agents on one side of the market — say hospitals — make offers to prospective interns. Each intern chooses the offer she likes best, and rejects the rest. A crucial part of the algorithm is that offers are not immediately accepted but simply held on to — hence the name deferred acceptance. Any hospital whose offer is rejected can make a new offer to interns who have previously not rejected the hospital. The algorithm terminates when no hospital wants to or can make a new offer and produces a stable outcome — no pair of a hospital and intern wants to form a new match.

This simple algorithm has proved to be the backbone for much of the subsequent work in the theory of matching. Its powerful implication was first discovered in 1984 by Al Roth who pointed out that the Gale-Shapley algorithm provided the theoretical foundation of the American national resident matching programme that was used to assign medical interns to hospitals. Roth showed that this centralized procedure worked very well for unmarried interns but not for couples whose preferences over hospitals obviously have special features. Roth later redesigned the NRMP programme to make it more suitable for couples.

Even neoclassical economists do not believe that markets solve all allocation problems. In particular, there are many allocation problems where goods or services should not necessarily go to the highest bidders. Al Roth has worked on a variety of such allocation problems, including admission to the public school systems in New York City and Boston. Earlier, schools in New York and Boston allocated seats through a complicated process with the objective of assigning students to their top choices as far as possible. If some students did not get their top choices because of inadequate positions, then their second ranked schools were taken into account, and so on. The system was very cumbersome and involved repeated student applications, and much heartburn.

It also led to strategic behaviour. Parents applied first to less popular schools to make sure they got in, leaving students with none of their top choices. Roth realized that the matching process could be improved dramatically by applying a version of the Gale-Shapley algorithm. He designed a clearing house system, which continues to be used today.

Perhaps, Roth’s most far-reaching contribution — in terms of its effect on human lives — is his work on kidney exchange. A common problem for patients needing kidney transplants (indeed all organ transplants) is that often the donor may be the spouse who has a different blood group. Of course, incompatible donor pairs can often exchange kidneys with other such pairs. Using ideas from matching theory, Roth and co-authors showed how larger scale exchanges of this kind can be conducted in an efficient and incentive compatible manner. Their ideas resulted in a kidney exchange clearing house for patients needing transplants.

Roth and Shapley have made a perfect match. The latter may well have been labelled an ivory tower economist. But Roth has shown that good theory can have important real world applications. The Nobel economics prize could not have gone to a better matched pair.

The author is professor of economics, University of Warwick