« Back to Page 1

In 2006, almost 38 percent of kidney transplants in the United States involved living donors, according to UNOS data. In all likelihood, that percentage could be much higher, but all too often potential donors and their intended recipients are incompatible with each other because their blood or tissue types do not match. Time and again, willing donors such as Ron Bunnell prove to be mismatched with their intended recipients, leaving patients to wait helplessly for a deceased donor.

Three years ago, Carnegie Mellon’s Sandholm became aware of the problem when he helped organize a game theory conference in Marseilles, France. There, he heard a lecture delivered by Harvard Business School economist Alvin Roth about a new approach to kidney donation called paired exchange, in which two patients swap their incompatible live donors with each other to obtain suitable organs.

Roth’s interests lie in creating efficient mechanisms for the exchange of goods in moneyless markets—in this case, the bartering of kidney donors. He worked with fellow economists Tayfun Sonmez of Boston College and M. Utku Unver of the University of Pittsburgh to develop the first mechanism for organizing such an exchange. Using algorithms, it can be implemented on a computer to find the best possible patient-donor swaps.

With the help of the mechanism, a few paired kidney exchanges have occurred in the United States since 1999. The ultimate goal is to create a centralized, nationwide registry of more than 10,000 patient-donor pairs and do 2,000–3,000 such transplants a year, says University of Toledo Medical Center surgeon Michael Rees, who directs a kidney exchange network called Alliance for Paired Donation.

The more pairs in the database, the better the odds will be of finding good matches, Rees says. Moreover, when a person gets a kidney through paired donation, it shortens the wait period for others on the transplant list without subtracting from the organ pool.

But the available algorithms used by Roth, Sonmez, and Unver were inadequate to operate a national kidney exchange network. They couldn’t perform calculations on 600–900 pairs of donors and patients without the computers running out of memory.

Sandholm realized there was a need for a sophisticated computer program to find the best donor-patient matches in a database of thousands of people. He was prepared for the challenge to develop a matching algorithm for kidney exchange. After teaching at Washington University in St. Louis for four years, he left academia to form an electronic auction firm, CombineNet. With more than 130 employees and operations on four continents, CombineNet has saved companies who use its electronic marketplace software more than $4.4 billion through efficiency improvements. Sandholm also developed, with his graduate student Andrew Gilpin, one of the world’s best Texas Hold ’Em poker programs.

Solving the nationwide kidney exchange problem was a bit trickier. With thousands of pairs in a national registry, there could be billions of potential exchanges between kidney patients and would-be donors. Sandholm would have to develop an algorithm, or computerized method, to find the optimal set of cycles (of donors and patients) from among the virtually limitless possibilities without running out of memory first. “I’ve been doing market clearing problems since 1990, and in terms of memory requirements, this was the most complex I’ve ever faced,” says Sandholm, who was born in Finland and joined the Carnegie Mellon faculty in 2001.

He worked with Avrim Blum, an algorithm expert who came to Carnegie Mellon in 1991 after earning his doctorate at MIT, and David Abraham, Sandholm’s computer science graduate student with experience in matching markets. Their work was paid for by one of Sandholm’s grants from the National Science Foundation.

To bypass the computer memory limitations, the Carnegie Mellon trio created an algorithm that attacks the matching problem incrementally through a technique called column generation. That means that at no given time are all of the potential cycles in the computer’s memory together. In addition, rather than examining every possible solution, the algorithm can decide when it is headed in the wrong direction and stop itself from exploring paths unlikely to produce the optimal cycle of matches—a method known as “branch-and-price.” The three men spent hour after hour scribbling equations and graphs on the dry-erase board. After each brainstorming session on the algorithm, Abraham would retreat to his computer armed with new theories to test. “It was one idea flying after another,” says Abraham, originally from Sydney, Australia. “One idea would mean that instead of 800 patients in the market, we could do 1,500. Then another idea would take it from 1,500 to 4,000 patients. We were constantly refining the basic theme and coming up with new ideas to improve the program.”

Another breakthrough came last year when Roth, Sonmez, and Unver determined that allowing for exchanges among more than four donor-patient pairs doesn’t substantially increase the number of transplants that can be arranged. Their observation gave the Carnegie Mellon algorithm even greater ability to know early on when it arrives at the best answer, while considering still fewer possibilities. That saves additional time and memory.

“Our software doesn’t even have to look at all the cycles, but it is still able to know it has the best solution,” Blum says.

(Continued …)

1 2 3