February 27, 2012
Volume 1, Issue 6
It’s in the news: Kidney Exchanges can save lives! How does computational thinking help? See the recent New York Times article entitled, 60 lives, 30 Kidneys, All Linked: http://www.nytimes.com/2012/02/19/health/lives-forever-linked-through-kidney-transplant-chain-124.html. This story starts with a single donor, not a patient-donor pair, so it's called a "chain" rather than a cycle, as described below.
More than 50,000 people in the U.S. are diagnosed with a potentially terminal kidney disease every year. Kidney transplants are often their best option for saving their life. Unfortunately, the demand for kidneys far outstrips the supply from deceased donors. For many patients with kidney disease, the best option is to find a living donor — a healthy person willing to donate one of their two kidneys. In a live donation, a potential donor and the intended recipient must be compatible, which can be quite rare. In order for patients to obtain a compatible donor, they can swap donors. A pool of incompatible patient-donor pairs where one tries to find swaps is called a kidney exchange. Kidney exchanges are now being used nationally and gaining recognition.
A 2-Cycle exchange.
In the simplest exchange, you have two patients each with an available donor kidney, and both patients are compatible with the other’s donor kidney (see figure to the left). However, when compatibility doesn't match, looking for a third person can make the exchange work — donor 1 donates to patient 2, donor 2 to patient 3, and donor 3 to patient 1; this is called a "3-cycle exchange" (see figure below). Longer cycles can yield more matches, but are often difficult to manage.
A 3-Cycle Exchange.
Innovative techniques from computer science and computational economics help solve the important medical challenge of finding cycles in a kidney transplant list with thousands of patients. Professor Tuomas Sandholm and his research group developed an algorithm that can compute the optimal matching for a U.S.-wide kidney exchange (~10,000 patients) in about an hour. The optimal matching is the one that results in the largest number of exchanges. Previous attempts at matching would either only work with 2-cycle exchanges, or they would exhaust the computer’s memory before reaching an optimal solution. Since their first algorithm, developed in 2006, Sandholm and his team have developed a series of new versions of the algorithm with more functionality, and new approaches of dealing with the dynamics of the problem. Currently, his algorithm is in use by the national kidney exchange run by the United Network for Organ Sharing.
Professor Tuomas Sandholm enjoying windsurfing! Photo courtesy of Tuomas Sandholm.
Matching algorithms can be applied to a variety of other problems that require similar barter exchanges. For example, the National Odd Shoe Exchange lets people with differently sized feet agree to swap shoes to avoid having to buy two pairs each (http://www.oddshoe.org); Read It Swap It lets people swap books (http://www.readitswapit.co.uk/TheLibrary.aspx); Intervac allows people to swap vacation houses (http://www.intervac-homeexchange.com); and Netcycler allows people to swap, give away, and get items for free (www.netcycler.com).
Who thinks of this stuff? Tuomas Sandholm is a Professor of Computer Science at Carnegie Mellon University and the Founder and Director of the Agent-Mediated Electronic Marketplaces Laboratory. He earned his Ph.D. from University of Massachusetts and completed his undergraduate degree at Helsinki University of Technology in Finland. Among other topics, Professor Sandholm works in mechanism design, a subfield of game theory. In 1986, he was ranked as the #1 windsurfer in Finland, and in 1987, he ranked 12th in the world.
Dickerson, J., Procaccia, A., and Sandholm, T. (June, 2012). Optimizing Kidney Exchange with Transplant Chains: Theory and Reality. Eleventh International Conference on Autonomous Agents and Multiagent Systems, Valencia, Spain. Retrieved from http://www.cs.cmu.edu/~arielpro/papers/chains.aamas12.pdf on February 13, 2012.
Rees, M., Kopke, J., Pelletier, R., Segev, D., Rutter, M., Fabrega, A., Rogers, J., Pankewycz, O., Hiller, J., Roth, A., Sandholm, T., Ünver, U., and Montgomery, R. (2009). A Nonsimultaneous, Extended, Altruistic-Donor Chain. New England Journal of Medicine 360(11), 1096-1101. Retrieved from http://www.cs.cmu.edu/~sandholm/nonsimultaneous%20donor%20chain.NEJM09.pdf on February 23, 2012.
Sandholm, T. and Heckerman, D. PROBE on Computational Thinking for Optimal Kidney Exchange. Retrieved from http://www.cs.cmu.edu/~CompThink/probes/kidney_exchange.html on February 13, 2012.
Listen to Professor Sandholm talk about his work with kidney exchanges:
To learn more about organ and tissue donation, please visit: http://organdonor.gov, and to learn more specifically about kidney exchanges, visit the United Network for Organ Donation (http://www.unos.org), Alliance for Paired Donation (http://paireddonation.org), or North American Paired Donation Network (http://www.paireddonationnetwork.org).