The Sveriges Riksbank Prize in Economic Sciences in Memory of Alfred Nobel 2012
Alvin E. Roth, Lloyd S. Shapley
Presentation Speech by Professor Torsten Persson, Member of the Royal Swedish Academy of Sciences, Member of the Economics Sciences Prize Committee, 10 December 2012.
Your Majesties, Your Royal Highnesses, Laureates, Ladies and Gentlemen,
It is important to make the right choices in life. In many critical situations, however, such as among options for school, university, profession or spouse, it is not enough to choose. You also have to be chosen. The key question in this kind of matching is: who gets what?
In August 2011, a 66 year-old man in Livingston, New Jersey, gets a new kidney. The donor is a complete stranger, a 44 year-old man from Riverside, California, who offers his left kidney as a genuinely altruistic gesture. The recipient’s niece is prepared to donate one of her kidneys to her uncle, but belongs to the wrong blood group. Instead, the niece is asked to donate her kidney to an unknown woman in Wisconsin, whose ex-boyfriend in turn donates one of his kidneys to another anonymous patient in Pittsburgh. The chain does not come to an end until 60 coordinated transplants have taken place across the entire United States. Four days before Christmas Eve, a 30th patient with chronic kidney failure, a 45 year-old man in Chicago, resumes a normal life after a difficult year of dialysis.
This success story reflects not only achievements in nephrology, but also innovative research in matching theory. Thirty kidneys can be allocated among thirty patients in an almost infinite number of ways. But only a few of these potential matches are truly great, because the human body is so prone to reject foreign organs.
It was only eight years ago that Alvin Roth and his colleagues published their first scientific study on the most efficient way to manage the benevolence of organ donors. The following year, in collaboration with physicians, they established the first centre for matching kidney donors with patients: the New England Program for Kidney Exchange.
At this point in time, Roth was not a novice in the field of matching. In 2003, he had been commissioned to redesign the annual procedure which matches more than 90,000 prospective high-school students in New York with hundreds of schools – a problem with a staggering number of potential solutions. The outcome was so successful that several other metropolises adopted similar systems for school choice. In the mid-1990s, Roth had already been asked to reconstruct the clearinghouse which each year pairs 20,000 new doctors with hospital internships throughout the U.S.
The story of matching theory goes back much further, however. Exactly 50 years ago, the mathematician David Gale wrote a letter to some of his colleagues about a tricky mathematical problem. Assume that a large number of students are to be accepted at a much smaller number of universities. Is there always a stable matching, whereby each student will be admitted by the university she ranks the highest among those which are willing to accept her, and vice versa for the universities? Lloyd Shapely replied by return mail. He not only proved that the answer is "yes", but also proposed a specific algorithm that always results in a stable solution in similar, two-sided matching problems. Several decades later, this is precisely the algorithm Roth built upon when he reformed both the clearinghouse for new doctors and school choice in New York.
In the 1970s, Shapely solved another abstract problem, that of one-sided matching. If a number of individuals each own a house, is there any specific procedure which permits them to exchange houses up to a point where no further improvement is possible, given their housing preferences? Shapley’s elegant solution demonstrates that this is indeed the case. Three decades later, Roth built precisely on this result in his work on chains for kidney exchange.
Dear Professors Roth and Shapley,
Professor Shapley: Your contributions to cooperative game theory are legendary among game theorists and economists. You and David Gale are the founders of matching theory, and the deferred-acceptance algorithm you discovered is the cornerstone on which theory and applications rest.
Professor Roth: Your innovative work comprises theory, empirical evaluation, laboratory experiments, and design of actual markets where prices cannot be used, for ethical or legal reasons. It is this feedback between theory and practice that makes market design such a flourishing field.
You have never worked together. But together your contributions constitute one of those unexpected journeys, from basic research motivated by sheer curiosity, to practical use for the benefit of mankind. It is an honour and a privilege to convey to you, on behalf of the Royal Swedish Academy of Sciences, our warmest congratulations. I now ask you to receive your Prize from his Majesty the King.