The practical power of game theory

7/8/2010 - Northwestern Memorial Hospital announced April 28 that doctors completed eight kidney transplants — a total of 16 surgeries — over the course of three days. Aside from its significance as a medical feat, the series of life-saving procedures provided tangible evidence that game theory — a very theoretical field — can produce practical outcomes.

	Related Video   Alvin Roth, George Gund Professor at Harvard

Alvin Roth, the George Gund Professor of Economics and Business Administration at Harvard University, illustrated the practical power of game theory and market design in his May 26 talk at the 2010 Nancy L. Schwartz Memorial Lecture. Roth was the 28th scholar featured in the annual lecture series.

During his lecture, “Market Design,” Roth drew upon his eight-year research in kidney donor exchanges and his work in the New York City public schools, Boston public schools and the National Resident Matching Program. He explained that economists “are starting to take an active role in design” in nontraditional markets, including medicine and education.

Roth singled out three general features of good market design. First, markets must be “thick” — they must attract enough buyers and sellers to encourage good transactions. Second, markets must avoid congestion to allow time for participants to make judicious transactions. Third, markets must be “safe” for participants — in other words, the market’s rules must be consistent with participants’ incentives — to ensure their complete participation.

Markets also face the issue of “repugnant” transactions, such as the use of money in kidney transplants, Roth said. He pointed out that some transactions are not repugnant until money enters the equation. That’s because money objectifies what is being bought or sold, creates some coercion, and/or leads to a slippery slope.

When money is used in a nontraditional market — such as a school or hospital — it assumes a function different from when it is used in a typical commodity market, Roth said. For example, universities don’t raise tuition until they have attracted the desired number of prospective students. Kidney exchanges also fall into this market category. “In kidney exchanges,” he explained, “money is ruled out by law.”

Typically, finding a willing and compatible donor is extremely difficult — a situation that echoes a classic problem in economics, the “double coincidence of wants.” But a kidney exchange can help solve this problem by bringing all patients and willing donors to the same table, increasing the probability of finding matches.

Figure 1

A simple kidney exchange would work like this: Recipient 1 requires a kidney, but her partner — Donor 1 — is incompatible. Recipient 2 and Donor 2 face the same problem. But Donor 1 is compatible with Recipient 2 — and Donor 2 is compatible with Recipient 1. The two parties — who otherwise might never have had an interaction — exchange kidneys, 1 to 2, and vice versa (see Figure 1).

To keep the exchange functioning smoothly, surgeries are carried out simultaneously; this avoids the potentially disastrous scenario of a donor backing out after his or her partner has received a kidney. A two-way exchange, then, involves four concurrent surgeries: two kidney removals and two transplants. This logistical constraint makes it difficult to run large exchanges with multiple surgeries occurring at the same time.

Roth is involved in several programs and initiatives, such as the New England Program for Kidney Exchange (NEPKE), to lift such constraints on exchanges. Established in 2004, NEPKE is a registry program that helps match compatible kidney donors and recipients in the New England area. In its early stages, the program sought Roth’s expertise to address issues including the logistics of medical procedures; the design of databases and algorithms for decision-making; and the alignment of incentives for doctors, patients and donors to achieve efficient outcomes.

In addition, since 2004, Roth and his colleagues have collaborated with medical doctors and computer scientists to organize exchanges that bypass the simultaneity constraint and promote Non-Simultaneous Extended Altruistic Donor Chains (the latter enabled Northwestern Memorial Hospital to perform eight kidney transplants in three days).

Mixing traditional transplant options (two-way exchanges, lists and non-directed “good Samaritan” donors) with new donor-matching software has led experts to envision even larger exchanges. The successful exchanges were accompanied by myriad smaller innovations in the exchange’s setup. “Market design is not just something that happens centrally,” Roth said. “It’s something that happens virally, too.”

Roth and his colleagues are currently analyzing exchanges between different transplant centers, where matching problems are harder to solve.

Figure 2

Figure 3

For example, take two transplant centers. Each may have two pairs of patient-donors, which would make possible two transplants (see Figure 2). Suppose, however, that in the second transplant center, there is a patient compatible with one of the donors in the first center, but that the second donor’s partner has a higher priority (for example, the patient is a child). If both transplant centers are pooled, one of the patients in the first transplant center could be left without a transplant, because the patient in the second center would take priority. Hence, the first center would have an incentive to withhold information or participate partially in the exchange, as full participation is not in the best interest of its patients. One way to eliminate this problem is to employ mechanisms that prioritize transplants based on “internally match-able pairs,” or pairs of donor-recipients who could have been matched within one transplant center (see Figure 3).

“There has been progress, but it has been awfully slow,” Roth concluded. While kidney exchanges now number in the hundreds, patients on the waiting list number in the thousands. “We are not keeping pace with the growing number of patients,” he said.

Roth closed his talk by revisiting the thorny issue of money in kidney exchanges.

Addressing the audience, he asked, “Are you willing to contemplate the investigation and perhaps eventual adoption of the carefully regulated sale of live kidneys?” Less than half of the audience members raised their hands. “How about, instead of kidneys, hearts? Suicide donors?” Almost all hands went down. “So the point is that economists, some of us, have repugnance,” Roth said.

“Think about kidney exchanges. They give us some of the benefits of money without the use of money,” he said. “And that’s why I think they are a great market design approach to try to increase the number of kidney transplants in a world where it is illegal to sell kidneys.”

The Nancy L. Schwartz Memorial Lecture series was founded in 1983 by the family members, colleagues and friends of Nancy L. Schwartz, the Morrison Professor of Decision Sciences and the first female faculty member appointed to an endowed chair at the Kellogg School. Previous speakers include Nobel Laureates Robert C. Merton, Daniel Kahneman, Roger Myerson, Joseph Stiglitz, Kenneth Arrow and Robert Aumann. In all, 11 Nobel Laureates have delivered papers at the lecture, most of whom earned the honor after speaking at Kellogg.