CS Bits & Bytes is a bi-weekly newsletter highlighting innovative computer science research. It is our hope that you will use CS Bits & Bytes to engage in the multi-faceted world of computer science to become not just a user, but a creator of technology. Please visit our website at: http://www.nsf.gov/cise/csbytes.

February 27, 2012
Volume 1, Issue 6

Kidney Exchange

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.

2-cycle exchange

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.

3-Cycle Exchange

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.

TUomas Sandholm

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.

 

Sources:

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.

Links:

Listen to Professor Sandholm talk about his work with kidney exchanges:
http://research.microsoft.com/apps/video/default.aspx?id=103471.

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).

Activity:

These problems, developed with guidance from Vincent Conitzer, Professor of Computer Science and Economics at Duke University, will help students to think through the algorithmic steps required for a cycle exchange.

  1. Consider the exchange below. A patient is connected to a donor if they are biologically compatible. A donor will only donate a kidney if his or her friend also receives a kidney. What is the optimal  matching for this exchange? Why?


    2. 4-cycle exchange

  2. What technique did you use to solve this problem? How would your technique scale if there were 10 donors and patients? 100? Thousands?
  3. Problem 1 may be more easily viewed if expressed in a different structure that preserves the important relations among patients and donors. In the figure below, there is an edge from i to j if and only if, patient i can receive donor j’s kidney.  A legal kidney exchange is one where there is a path following the edges that visits each vertex exactly once and returns to the starting vertex. What is the largest such path in the graph below?

    4. Hamiltonian Cycle
  4. A Hamiltonian cycle is a path where you visit every node in the graph and return to the initial node. A Hamiltonian cycle in a kidney exchange graph would include all patients and donors. A kidney exchange that includes a collection of smaller cycles rather than a single big cycle would be preferable. However, Hamiltonian cycles have broad applications in computer science and mathematics.  For more activities that involve Hamiltonian cycles, see: Finding Hamiltonian Cycles (http://nrich.maths.org/897) and Calculating the Number of Hamiltonian Cycles: (http://nrich.maths.org/2320).