By James Case
Who Gets What—And Why. By Alvin E. Roth, Houghton Mifflin Harcourt, New York, 2015, 272 pages, $28.00.
Who Gets What—And Why. By Alvin E. Roth. Courtesy of Houghton Mifflin Harcourt.
In this exciting new book, Alvin Roth—McCaw Professor of Economics at Stanford University, joint winner of the 2012 Nobel Prize in Economics, and one of the world’s leading experts on market design and game theory—discusses the ongoing proliferation of electronic markets. In particular, he describes the several ways in which he and his colleagues have extended the Gale-Shapley matching algorithm to apply to a growing variety of real-world problems.
Roth seems proudest of his life-saving efforts to match voluntary kidney donors with transplant candidates. Though the first kidney exchange took place in the year 2000, the procedure was seldom performed in the months and years that followed. Previously, patients had often been obliged to wait a long time for a compatible donor, and more than a few died before a donor could be found. Family members were frequently willing to donate but were not always compatible. In such cases, a donor exchange in which \(A\)’s willing donor gives a kidney to \(B\) and \(B\)’s willing donor gives one to \(A\) can sometimes save lives. However, all four individuals must be located in nearby operating rooms at (more or less) the same time, which isn’t always easy to arrange. Additional lives can be saved with three-way exchanges, though these are trickier to organize since the cycle \(A \rightarrow B \rightarrow C \rightarrow A \) has to close, and all three patient-donor pairs must be in the same place at the same time. Four-way exchanges have also taken place.
Transplant candidates may receive kidneys from altruistic donors or deceased organ donors. When a patient \(A\) who is paired with a willing but incompatible donor receives a kidney from a deceased or altruistic donor, \(A\)’s designated donor becomes free to donate to a compatible \(B\) and so on, setting up the possibility of a (potentially) endless chain and eliminating the need for multiple simultaneous transfers.
Working with a pair of graduate students, Roth devised an algorithm that identifies potential cycles and chains within a pool containing both altruistic donors and patient-donor pairs. This work helped found the New England Program for Kidney Exchange (NEPKE) in 2004, which organized the fourteen kidney transplant centers in New England into a consortium for helping incompatible patient-donor pairs find matches. There is also now a National Kidney Registry, designed to increase the size of the pool that identifies potential chains and cycles of viable kidney transplants.
As Roth notes, some 17,000 kidney transplants are now performed each year in the United States alone. But, because there are more than 100,000 people awaiting transplants, much remains to be done. At present, each of the 11,000 deceased-donor kidneys per year produces only a single transplant. If they were used instead to start chains, the number of transplants could be increased significantly.
Roth entered the matching algorithm business in 1995, and joined the faculty of Harvard University a few years later. Here he learned of the Boston Pool Plan for matching incipient medical school graduates with hospital residencies. The Plan had performed admirably for many years, but was having difficulty managing the growing number of married couples among the new graduates demanding same-city appointments. Roth discovered that the existing plan utilized a matching algorithm equivalent to the Gale-Shapley algorithm—published in 1962, exactly ten years after the Boston Pool Plan’s initiation—for producing stable matchings.
In an article entitled College Admissions and the Stability of Marriage, written before the days of same-sex marriage, David Gale and Lloyd Shapley1 defined a matching of prospective brides and grooms to be stable if none of the assigned brides (seekers) could be reassigned to a groom (seekee) she would prefer, and who would in turn prefer her to his assigned bride. That definition extends, in a more or less obvious manner, to colleges and college applicants, jobs and job seekers, etc. According to Roth, there now exists a considerable body of empirical evidence that stable matchings are longer lasting, and on the whole more satisfactory, than unstable ones.
To produce a stable matching, both the Gale-Shapley algorithm and the Boston Pool Plan require each prospective seeker and seekee to submit a list of potential partners in order of preference. Working with Elliott Peranson, the engineer who had previously computerized the Boston Pool Plan and was intimately acquainted with its inner workings, Roth was able to produce an algorithm applicable to situations in which some of the seekees are located in different cities, while some pairs of seekers must be assigned to the same city. Now known as the Roth-Peranson algorithm, it employs the Gale-Shapley algorithm to produce a preliminary matching of newly minted doctors and residency programs, before trying to placate dissatisfied pairs one by one. Though examples exist in which no stable matching is possible, the possibility is rarely encountered in practice. It is “virtually never the case that a stable matching cannot be found,” writes Roth.
In 2003, Roth was called in to streamline the complicated, paper-based process that assigned some 90,000 eighth graders to New York City’s high schools. Although the number of applicants was roughly the same as the number of openings, the process was not working well. Whereas some 17,000 applicants were receiving multiple letters of acceptance from schools on their preferred list of up to five (and exhausting the allotted time before making a decision), as many as 30,000 were receiving no letters at all from the schools they had listed. As a result, these “unsuccessful applicants” were often not assigned to a school until late August. Both parents and children were reporting high levels of anxiety.
Roth, together with two co-workers, increased the number of schools a student was allowed to list, designed an applicable version of the Roth-Peranson algorithm, and set out to explain the new system to all interested parties. In the first year of operation, the number of students unassigned to one of the schools on their preferred list declined from 30,000 to 3,000. And in the first three years of operation, the number of students who got their first choices increased steadily, as did the number who got their second through fifth choices. Today, “New York’s high school choice system is holding up well,” writes Roth. The algorithm is also being imitated, with varying degrees of success, in several other cities!
Throughout the book, Roth is careful to describe matchmaking venues—in which nothing is either bought or sold—as “markets,” and to inquire after the conditions likely to promote either success or “market failure.” He identifies five critical factors; markets should be thick, uncongested, safe, simple, and efficient. By “thick,” Roth implies that markets should contain numerous potential parties and counterparties. Participants in “uncongested” markets should be able to avoid interfering with one another, and those in “safe” markets have nothing to lose by revealing their true preferences to the “yenta” in the computer. “Simple” markets allow the entire process to be understood clearly and quickly, and “efficient” markets do not expend undue quantities of energy – psychic or otherwise.
In closing, it should be mentioned that by classifying matchmaking venues as markets, Roth gives the impression that economists are uniquely qualified to design and modify them, though nothing in the traditional economics curriculum seems particularly relevant. On the contrary, students of combinatorics, computer science, and/or operations research (in which Roth himself received his doctoral degree) would seem at least as well prepared for the task. The authors of Freakonomics and SuperFreakonomics are guilty of similar territorial aggression, seeking to coopt consulting opportunities from the statisticians upon whose methods they almost exclusively rely. Nevertheless, Who Gets What—And Why presents an interesting account of the way algorithmically-driven electronic markets are beginning to eliminate the barriers that so often impede desirable commerce
1 Shapley, who received the Nobel prize for economics in 2012, died recently at the age of 92.
James Case writes from Baltimore, Maryland.