Pay it Forward

[okarol]

Pay it Forward

By: Jennifer Bails
Carnegie Mellon Today
January 2008, Vol. 5 No. 1

Barb Bunnell lies sedated in an operating room at Banner Good Samaritan Medical Center in Phoenix. The Arizona woman bears the same genetic burden as her mother and grandmother, who both died in their early 50s of an incurable disorder called polycystic kidney disease. Cysts have begun to grow and multiply on Bunnell’s kidneys, too, taking their deadly stranglehold on another generation. Eventually, the fluid-filled sacs will smother her kidneys entirely, plunging her into end-stage renal failure so that her body can no longer filter waste and toxins from her blood.

The 53-year-old grandmother already has lost more than 80 percent of her kidney function and suffers from back pain, hypertension, and anemia. Doctors are not far from recommending that she undergo regular blood-cleansing treatments known as dialysis, which involves spending several hours a day, a few times a week, hooked up to a life-sustaining machine that would perform the work of her malfunctioning kidneys until a deceased-donor organ comes along. Last year, almost 12 Americans died each day waiting for a kidney.

All too aware of the grim statistics, Bunnell had feared the worst. Until last summer, that is, when an algorithm—developed by Carnegie Mellon computer science professors Tuomas Sandholm and Avrim Blum and graduate student David Abraham—matched her with Matt Jones. Jones is a 28-year-old college student and father of four who works full-time at a rental car company to support his family. He wanted to donate one of his kidneys to a stranger, with no strings attached, simply because he could.

Many called him crazy; kidney removal is major surgery that kills three of every 10,000 donors. And what if his second kidney fails later in life? Or what if one of his children needs a kidney transplant one day, and he would have been an eligible donor? His fiancée and brother tried to talk him out of the operation. But Jones, who first learned about live kidney donation through a cable news program, was undeterred. “Around the holidays, do you ever put a couple of bucks in the red kettle for the Salvation Army?” he asks. “What I did is really no different. We only need one kidney to live. So if you’ve got something a little extra that you don’t need and someone else could use it to live a decent life, I believe you should share it.”

Doctors refer to Jones as an altruistic donor. Sandholm calls him an angel.

On a hot July morning, transplant surgeons make five keyhole incisions in the side of Jones’ belly. Next, the doctors inflate his abdomen with gas to separate the outer layers of muscle and fat from the pudding of organs within. Using a pencil-thin video camera to navigate inside the cavity, they start to dissect the tangled snarl of blood vessels attaching his healthy left kidney.

Bunnell waits for her gift in a nearby hospital bed. After living in fear for more than two decades, her transplant finally begins. And the miracle Jones touches off doesn’t stop here.

One week later, Bunnell’s husband opts to pay it forward by donating one of his own kidneys to another stranger, 32-year-old Angie Heckman of Toledo, Ohio. Ron Bunnell had intended to give a kidney to his wife, but differences in body chemistry prevented a good match. The algorithm pairs him with Heckman instead. “There were never any second thoughts on my part,” he says. “I was a little bit scared, but most people go through their whole life never receiving a gift as big as the one Barb did. So I really did want to donate a kidney in return no matter what the circumstances.”

The healthy kidney from Bunnell enables Heckman to begin her life anew, freed from the burden and risks of dialysis and effectively cured of an autoimmune disorder that caused her kidneys to break down. Now in turn, Heckman’s mother is slated to donate one of her kidneys in the coming weeks to keep another stranger healthy and alive.

And so on and so on, in theory, forever.

Experts say that organ donation chains like this one powered by Carnegie Mellon technology could help to solve America’s kidney shortage crisis and, in the process, save thousands of lives. There are nearly 75,000 patients in the United States on the waiting list for a deceased-donor kidney, according to the United Network for Organ Sharing (UNOS), which oversees the national database of clinical transplant information. Wait time often can stretch from months to years depending on age, blood type, and other variables.

People who wait long for a deceased-donor kidney may develop other serious medical problems, making them weaker going into surgery and more likely to suffer complications. Last year alone, approximately 4,000 kidney patients died because they did not receive a transplant in time.

Owing to the shortage of deceased donors, the best option for many people with kidney disease is to find a living donor—a healthy friend or loved one willing to donate a kidney so the patient can bypass the waitlist. On rare occasions, someone like Matt Jones is willing to give up a kidney to a stranger for nothing in return.

The medical benefits of finding a live donor kidney extend beyond the possibility of a shorter wait. The organs last nine years longer on average than from a deceased donor and usually require lower doses of potent anti-rejection drugs that make patients vulnerable to infection, high blood pressure, and other nasty side effects.

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.

In June, at the Association for Computing Machinery’s Conference on Electronic Commerce in San Diego, Calif., the University team presented a working version of the algorithm with enough computational power to analyze as many as 10,000 patient-donor pairs. The software has been in use at the Alliance for Paired Donation since February.

Every two weeks, patient data from the alliance’s 56 transplant programs in 20 states is aggregated by Jonathan Kopke from the Institute for the Study of Health at the University of Cincinnati. Kopke, who developed the alliance’s Web-based software, e-mails this data to Abraham. After just a few seconds of processing, Abraham’s computer identifies potential exchanges among two, three, and four sets of donor-patient pairs. The software also factors altruistic donors into its calculations. The good Samaritans do not have patients associated with them, so their donations could trigger domino effects—like transplant cascades that continue ad infinitum—as long as no donor in a chain backs out.

Matt Jones set in motion the first such chain this summer, after the algorithm matched him with Barb Bunnell. Then it paired Barb’s husband, Ron, with Angie Heckman. Angie’s mother is next in line waiting for her match.

Jones’ good will received national media attention, piquing the interest of another 100 potential altruistic donors who contacted the Alliance for Paired Donation to express their desire to share a kidney.

“If we could turn each of those 100 kidneys into chains of 10, as long as no one cheats, we would get 1,000 people transplanted, and if we can make chains of 100, we could eventually get 10,000 people transplanted,” Rees says. “And Tuomas’ software is definitely a key part of making this happen.”

Perhaps more importantly, the algorithm also overcomes the technological barrier to forming a unified national kidney exchange, which ideally would be managed by UNOS, Rees says. “Now it’s more of a political problem. We just need to get everyone to play in the same sandbox, and that is no easy feat because everyone thinks they have the best way to do it.”

The high stakes of the work hasn’t escaped this team of computer scientists more used to dealing with theory and abstraction than real-world matters of life and death. “At first, it made us very nervous to do the match runs,” Abraham says. “In the back of your head, you are always worried there might be a bug in the software or something you overlooked.”

They have now developed a verification technique that ensures the accuracy of the results.

The reward of helping to orchestrate lifesaving miracles far outweighs the anxiety associated with such responsibility. “Medical doctors get used to saving lives—they do it all the time,” Sandholm says. “But for a computer scientist to be saving lives, that’s really fantastic.”

Barb Bunnell is one of those lives. Minutes after transplant surgeons pull Matt Jones’ kidney through a hole near his navel, they sew the healthy organ to the inside of Bunnell’s right pelvis. Soon afterward, the kidney begins the vital work of removing waste products from her bloodstream, taking over for her failing renal system. Several months later, Bunnell is almost recovered from the operation—and hopefully spared the future ravages of her illness, with a chance to watch her three grandchildren grow to have children of their own.

As an enduring reminder of his gift, Jones bears a J-shaped scar on his abdomen. Otherwise, life continues more or less as usual. He is back to school, working long hours for his rental car company and planning his wedding. He says the profound bond he formed with the Bunnells will last a lifetime. All three hope they become links in a chain of life that lasts even longer.

------------

Jennifer Bails is a freelance writer and a former award-winning newspaper reporter.

http://www.carnegiemellontoday.com/article.asp?aid=514#