AWARDEES: Alvin Roth, David Gale, Lloyd Shapley
SCIENCE: Market Design
FEDERAL FUNDING AGENCY: Office of Naval Research, National Science Foundation
“Take care of him. And make him feel important. And if you can do that, you’ll have a happy and wonderful marriage. Like two out of every ten couples.”
When playwright Neil Simon joked about marital compatibility, he had no idea that one day people like him – kidney transplant recipients – would benefit from federally funded research on how to match up partners. Thousands of people in the United States are living with transplanted kidneys today thanks, in large part, to a kidney donor matching program that grew out of federally funded research on matching pairs by mathematicians David Gale and Lloyd Shapley. Their work, which used marriage as a model, provided the foundation for economist Alvin Roth and others to develop numerous practical market applications, and their subsequent research on matching was the basis for today’s kidney matching program that has saved so many lives.
In 1962, Gale and Shapley developed the Gale-Shapley deferred acceptance algorithm. They used a theoretical construct of pairing men and women in stable matches, even if the couple did not agree on who would make the best partner. In a landmark paper titled, “College Admissions and the Stability of Marriage,” made possible through work funded by the Office of Naval Research, the pair noted the similarities between students seeking the perfect college and individuals seeking the perfect partner. They were able to demonstrate, in a manner worthy of a Neil Simon romantic comedy, that if two groups of men and women were matched based on a system in which each individual ranked their potential mates, a formula could be used to ensure that every individual ended up with the person they preferred most who also preferred them, thus maximizing the number of strong matches (and eliminating the possibility of two individuals both preferring each other to their mate). The process they developed was called the deferred acceptance algorithm. (For an interactive demonstration of the stable marriage problem, see the website created by Gale: http://mathsite.math.berkeley.edu/main.html.)
Building upon the work of Gale, Shapley, and others, Al Roth, an economist funded by the National Science Foundation, was able to apply the deferred acceptance algorithm to many other market contexts, such as public school choice systems in New York, Boston, and other cities, and the National Residency Match Program, which matches new doctors graduating from the nation’s medical schools with appropriate hospitals around the country.
Gale, Shapley, and Roth would intersect again, also with the support of the National Science Foundation, when Shapley (working with Yale economist, Herbert Scarf) built upon further work by Gale in market design, describing a system in which large items, such as houses, could be exchanged without money changing hands. While anyone with a mortgage might see this as a seemingly irrelevant construct, Roth, joined by his colleagues Tayfun Sonmez and Utku Unver, recognized its application to organ donation. Paying for organs is strictly forbidden in the United States, so here was a market in which something of great value – life-saving transplants – needed to be allocated without the use of money.
Imagine a loved one has been struck with kidney disease and is desperately in need of a transplant. You would like to donate a kidney, but yours does not match your loved one’s immune system. However, you are not alone. There are pairs in the same predicament all over the country. How does society maximize the number of patients who are matched up with willing, compatible donors? In 2004, together with Sonmez and Unver, Roth devised a system based on the housing exchange market model that could arrange complicated, multiple-person matches on a nationwide basis, resulting in the most efficient exchange to save lives. This work was also funded by the National Science Foundation. Last year, in the largest exchange ever, a nationwide chain involving 60 people resulted in 30 kidney transplants. In 2012, Alvin Roth and Lloyd Shapley shared the Nobel Prize for economics. (David Gale passed away in 2008.)
In a recent interview in Stanford Magazine, Roth joked about his graduate-level class on market design. “This class will take the romance out of a lot of things.” Given the romantic origins of these economic theories, one may beg to differ.