October 22, 2012
New Software Matches More Kidney Donations, Faster
Game theory and market dynamics inspire new software that streamlines complicated matches
Jack Burns and his wife, Adele, welcomed Doug Robertson with open arms. It was a very special reunion!
"I didn't know whether I was ever going to meet my recipient and I was just thrilled that we could get together," said Doug, who had traveled from his home in Portsmouth, N.H., to meet Jack and his wife. Doug came into Jack and Adele's lives in 2010 when Jack, who has diabetes and high blood pressure, needed a new kidney. Adele wanted to give him one of her own. "I wanted to have my husband around and I knew that we didn't have a lot of options," says Adele.
Jack gets choked up thinking about what his wife sacrificed. "I was grateful to have someone who loved me that much." But, Adele was not a good medical match to her husband. So, they joined a live-donor kidney exchange program. She donated one of her kidneys to a suitable recipient and Jack got a kidney from Doug. It can be much quicker than getting an organ from a deceased donor.
"The deceased donor wait list can be very long for people," explains Ruthanne Hanto, director of the Organ Procurement and Transplantation Network (OPTN) Kidney Paired Donation pilot program, which is operated under the United Network for Organ Sharing (UNOS). "If somebody brings a living donor with them, then they have a great chance of getting transplanted sooner."
With support from the National Science Foundation (NSF), Harvard University economist Alvin Roth helped develop a suite of computer programs that match living kidney donors with recipients. Roth and UCLA professor emeritus Lloyd S. Shapley shared the 2012 Nobel Memorial Prize in Economic Science for the theory of stable allocations and the practice of market design.
Roth's team includes market designer Itai Ashlagi and operations researcher David Gamarnik at MIT and economists Utku Unver and Tayfun Sonmez at Boston College. Together, they developed an optimization program which looks at all the donors and recipients in the program. "You look for ways to arrange those exchanges so as to get as many of them as possible," says Roth.
"A combination of tools from the optimization theory, theory of graphs and probabilistic methods enable building models which provide a unique insight into the fascinating challenge of finding the right matches," explains Gamarnik. "Without these techniques, the practitioners face the proverbial 'finding-a-needle-in-a-haystack problem' of searching through the astronomic number of potential matches."
"This research is making it possible for one altruistic person to spark a chain of donations, whereas before one kidney donor helped one person," says Nancy Lutz, program director for the Social and Economic Sciences (SES) Division of NSF's Directorate for Social, Behavioral and Economic Sciences (SBE). "Now, someone associated with the first kidney recipient then donates to someone else, and so on, kicking off a domino effect of donations and matches. In addition, it's especially rewarding to see such a clear and immediate benefit to the public. This research moved from abstract, academic theory to real world, direct impact very quickly."
Transplant surgeon Michael Rees at the University of Toledo Medical center is CEO of the Alliance for Paired Donation (see www.paireddonation.org). "When I first got involved with kidney paired donation in 2000, I was sitting at my kitchen table with the medical charts of 10 incompatible transplant patients and it took me four hours to find just one 2-way exchange. I knew then that I needed a computer to help find the matches," recalls Rees.
"But, then Al and his team showed me that with just 600 incompatible patient pairs, the maximum number of possible 2-way exchanges is about 180,000! And, if you include multi-way exchanges and chains of transplants, the best supercomputers in the world cannot find the best solution," continues Rees. "So, game theory and market design have come together to find practical solutions for kidney disease patients. Their matching software is the engine that has allowed us to help transplant centers in 30 states work together to create over 125 paired exchange kidney transplants since 2007."
So what are economists doing organizing kidney transplants? It turns out that an understanding of game theory and market dynamics is key to optimizing pairings. "If you're trying to organize an exchange, you need a marketplace and a clearinghouse, and that's what we tried to help our surgical colleagues put together," explains Roth. "Game theory turns out to be a giant thing for thinking about big systems in which there are lots of different incentives. The care of patients with kidney disease is a $100 billion a year industry so there are lots of interests in it."
"When we started working on market design for kidney exchange, ad hoc exchanges were being conducted sparsely in the country," says Unver. "Our experience in studying other allocation and exchange problems such as dormitory room allocation in colleges helped us tremendously in the design of centralized clearinghouses for kidney exchange. With the help of health professionals, the ideas we developed were adopted, tested and got refined in the field in various programs over the years. We eventually hope to help thousands of patients per year."
Think of it as a medical version of match-dot-com, linking donors and recipients, making chains of transplants possible across the country. It's all about streamlining complicated matches using the science of the marketplace.
"Kidney exchange is a powerful example of how research transforms into services which have profound impact on our lives," says Sonmez.
The software is comprehensive, matching participants with compatible blood types and antibodies. "It can put together an amazing string of different potential transplants that you just could not do manually. It is an amazing computer system," explains OPTN's Hanto.
"It is the combination of research and practice that led us to understand that using chains, exchanges that begin with an altruistic donor, vastly increase the number of transplants for highly sensitized patients who are difficult to match," notes Ashlagi.
Jack, Adele and Doug talk about how the live kidney exchange program changed their lives. "I'm just grateful and lucky that this person was out there," says Jack, as he smiles at Doug. The two joke with each other. "How are you doing with my old spare part," asks Doug. "Your kidney is probably the healthiest thing in my body!" chuckles Jack. "I was just hoping someone could use an old kidney like mine," laughs Doug.
This story was originally published April 30, 2012
Any opinions, findings, conclusions or recommendations presented in this material are only those of the presenter grantee/researcher, author, or agency employee; and do not necessarily reflect the views of the National Science Foundation.