Matchmaking for Kidneys
December 21, 2008
In this 40-node graph, the black lines represent possible kidney paired donation matches. The magenta lines show one possible set of matches, but only 10 pairs get transplants. The green lines show the best possible set of matches, with 14 pairs receiving transplants. From Sommer Gentry�s prize-winning essay (published in Compose, the DOE CSGF annual essay contest journal).
In a 2004 article about mathematicians' spare-time pursuits, Dana Mackenzie led off with MIT graduate student Sommer Gentry, an accomplished swing dancer who had incorporated "the wordless communication used by dance partners" into her research on robotics. This fall, SIAM News became aware of another of Gentry's talents: writing. Having been supported at MIT by a DOE Computational Science Graduate Fellowship, she was eligible to participate in the annual essay-writing contest sponsored by DOE for program alumni. Her essay---on matching donors and recipients for kidney transplants---took the top prize for 2007 (awarded by a trio of judges that included SIAM vice-president-at-large David Keyes). In the article that follows, Mackenzie brings readers up to date on Gentry, now a member of the faculty at the U.S. Naval Academy, her husband (her long-time dance partner and now a transplant surgeon), and results of their recent collaboration on kidney exchanges.
Dana Mackenzie
In April 2007, a 45-year-old African�American woman in Maryland made transplant history by becoming the first recipient of a kidney taken from a living donor and then flown all the way across the country. Anna (not her real name) had been waiting for a donated kidney for two years. Like many patients with kidney failure, Anna had a willing donor---her husband---but their blood types were a mismatch. She had blood type O and could receive an organ only from another person with blood type O. Her husband had blood type A.
When patients cannot find a compatible living donor, they often wait for what is called a "cadaver kidney"--a transplant from someone who has just died. But the odds against Anna were long. As a result of five pregnancies and numerous blood transfusions, her immune system was hypersensitive. Blood tests indicated that her body would reject organs from 96% of prospective donors, even those who matched her blood type.
Today, however, Anna is alive and has a normally functioning kidney, donated by a 50-year-old white man she had never met, who lived across the country in California. He had wanted to donate a kidney to his Asian�American wife, but also was denied because of a blood-type mismatch. Not only that, a third couple was involved, a Korean�American couple (both 48 years old) who likewise had incompatible blood types. By a series of three simultaneous exchanges---the 50-year-old in California donating to Anna, Anna's husband donating to the Korean woman, and the Korean man donating to the white man's wife---all three patients received the organs they needed, and nobody had to die.
For patients with renal failure, such games of "musical kidneys" are becoming more and more common, and the ending is almost always a happy one. Johns Hopkins University (where Anna received her kidney) and the California Pacific Medical Center in San Francisco (where the other two transplants were performed) have been leaders in organizing simultaneous ex-changes of pairs or triples of kidneys.
Although they have been highly publicized (a six-way exchange even appeared recently in the popular TV drama Grey's Anatomy), these multiple exchanges are no publicity stunt. They represent a very real way to make more kidneys available to more patients who need them. Sommer Gentry, an applied mathematician at the U.S. Naval Academy, has calculated that with a national database of incompatible donor�recipient pairs and a computerized matchmaking system, approximately 1000 to 2000 more kidney transplants could be performed every year---a major increase over the 15,000 transplants currently performed in a year. And the biggest beneficiaries would be people who, like Anna, are difficult to match. A nationwide pool would give them a better shot at finding a rare compatible donor.
Multi-patient Exchanges: Too Ambitious
The idea of kidney exchanges was first proposed by Felix Rapaport, a former president of the Transplantation Society, in 1986. He pointed out that a donor who was ready to give a kidney to a relative, but was stymied by a blood-type mismatch, might have enough of an emotional investment to agree to a quid pro quo arrangement. But according to Alvin Roth, an economist at Harvard University, kidney exchanges were extremely rare until the early years of this decade, and were performed on a completely ad hoc basis.
"There had been four in New England before we started," Roth says. "In one of them, the patients met in a waiting room at a dialysis center." Presumably, the idea of trading donor kidneys came up as the two patients were comparing notes about their incompatible donors.
In early 2002, Roth and two colleagues, Tayfun Sonmez and Utku Unver, started to wonder if there wasn't a more rational way to approach kidney exchanges. "This is where economists come in," Roth says. "We shouldn't just rely on people bumping into each other." They proposed a kidney-matching algorithm, called TTCC, or Top Trading Cycles and Chains (see SIAM News, June 2004, http://www.siam.org/news/news.php?id=230), based on a similar method designed by the late mathematical economist David Gale to facilitate exchanges in a housing market.
"We sent [the paper] to every surgeon we could find," Roth says. "Only Frank Delmonico [a surgeon at Harvard University] came to lunch with us and said, let's start a program." Six years later, the New England Program for Kidney Exchange now links 17 transplant centers in a regional network.
The TTCC algorithm has one drawback, however: It produces large multi-patient exchanges. "Don't kid yourself, we'll never be that ambitious," Roth recalls Delmonico saying. Large exchanges are logistically more difficult. Every transplant requires two separate operating rooms (one for the donor, one for the recipient) and two teams of surgeons. And lots of things can go wrong between the identification of a likely match and the actual operation.
Even among people who have matching blood types and pass the antibody tests, there is roughly a 10% chance of an immune reaction, which can be detected only when the patient's blood is directly exposed to the donor's in a lab. Once a likely match has been identified, in other words, there is still a 10% chance that the operation will have to be called off. With three pairs, the probability climbs to 27%; with six pairs, it escalates to 47%. A larger number of patients also means a greater risk that one of the donors will back out---as dramatized in the Grey's Anatomy episode---or that a bumbling surgeon will drop one of the kidneys on the floor. (Oops, maybe that happens only on TV.)
For all these reasons, Roth says, Delmonico advised him to concentrate on pairwise exchanges at first. Ironically, that was the same idea that Gentry had. Her husband, Dorry Segev, is a transplant surgeon at Johns Hopkins. One Friday afternoon, as she picked him up from work, he told her about the problem of maximizing the total number of transplants. At the time, surgeons were using index cards or a magnetic board to match patients with donors by hand. "Does the kind of math you do say anything about this?" Segev asked.
Pairwise Only: Not Ambitious Enough
By the next Monday, Gentry had an answer. She adapted an algorithm that had been discovered in 1965 by Jack Edmonds, a pioneer in the field of computational complexity. Edmonds's algorithm was designed to find the maximum number of matchings on a graph---in other words, the largest possible set of edges such that no two edges have a common vertex. In the kidney exchange problem, each edge would connect a mismatched donorrecipient pair to another pair who could exchange kidneys with them. The algorithm could be tweaked to include real-world constraints (for example, giving priority to hard-to-match patients, avoiding long-distance matches for patients who couldn't travel). Best of all, Edmonds's algorithm was fast---it was, in fact, one of the first nontrivial examples of a polynomial-time algorithm.
In 2005, Gentry and Segev performed a computer simulation of the effects of implementing Edmonds's algorithm on a national database of incompatible donor�recipient pairs. (Only a simulation was possible, because no such database existed.) The simulation showed that 1000 to 2000 additional kidney transplants could be performed every year. Their article presenting the result appeared in the Journal of the American Medical Association. "The JAMA editors told me that it was the first article they had ever published that was a computer simulation, and they published it because it was so important," says Robert Montgomery, the chief of transplantation at Johns Hopkins, who was a co-author of the paper.
Unfortunately, Gentry's approach had a weakness that was just the opposite of the one holding back Roth's TTCC algorithm: Because it considered only pairwise exchanges, it wasn't ambitious enough. "If you limit the problem to two-way exchanges, the problem is simple, polynomial time," Roth says. "Or if you place no limit on the sizes, it's also simple. But the hard problem, which is NP-complete, is to compute the solution with a limitation on size." That turns out to be the most relevant problem for kidney exchanges. Three-way exchanges, such as the one involving Anna's kidney, significantly increase the number of transplant opportunities, but with more than three donor�recipient pairs, the practical problems start to outweigh the benefits.
Both Roth and Gentry have developed integer-programming algorithms to solve the problem for three-way exchanges, and their algorithms have been successful on a regional scale. Gentry's software identified the three-way match that Anna participated in, because one of the California donors had actually gone to Johns Hopkins and been entered into its computer system.
Toward a Truly National Registry
For a truly national registry with as many as 10,000 patients, however, better matchmaking algorithms would be needed. Both Gentry and Roth relied on the integer-programming package CPLEX, which just couldn't scale up to such a large network. Last year, a team led by computer scientist Tuomas Sandholm of Carnegie Mellon University developed special-purpose software that chops the problem into smaller parts that can be fed into CPLEX.
Now that a national matchmaking program seems technically feasible, will it actually happen? Last year, the major legal hurdle was removed. In 1984, Congress had banned the sale or transfer of human organs "for valuable consideration." Did another person's kidney constitute "valuable consideration"? This legal ambiguity prevented the United Network for Organ Sharing (UNOS), the U.S. government's watchdog agency for organ transplantation, from moving ahead with proposals to implement a national kidney-sharing network.
In 2007, Congress passed the Charlie Norwood Living Donation Act, which made it clear that organ exchanges are legal. "This proposal came up before three different Congresses, but then Charlie Norwood [a congressman from Georgia] died of transplant complications, and his colleagues passed it in honor of him," Roth says. With UNOS now legally able to support the plan, and fully committed to it, Montgomery says that the national registry of incompatible donor�recipient pairs will probably "go live" in 2010.
It probably would not have happened without the mathematicians. "At first, surgeons had not seen the problem as being interconnected to the degree that I was talking about," Gentry says. According to Montgomery, it was Gentry and Segev's unique combination of talents that made surgeons pay attention. Says Montgomery, "It's been a wonderful marriage of someone who was capable of solving the problem with someone who had the clinical ability to identify the problem and evaluate how well the solution fits."
Dana Mackenzie writes from Santa Cruz, California.
