What would happen if surgeons and medical clinicians used computational thinking in order to make organ transplantation decisions?  Is it possible to optimize the allocation of organs so that many more people can be saved?  In this PROBE, Tuomas Sandholm, in collaboration with Microsoft Research, will make it possible for the United Network for Organ Sharing to use advanced computing concepts to make the best use of donor organs, potentially savings many thousands of lives each year.  Along the way, new advances in fundamental algorithms will be developed.

PROBE on Computational Thinking for Optimal Kidney Exchange

Organized by Tuomas Sandholm
In collaboration with David Heckerman, Microsoft Research

In the US alone, over 30,000 fall sick with lethal kidney disease each year. The demand for kidneys far exceeds the supply of cadaver kidneys. It is possible for a living person to donate a kidney, e.g., to a spouse, relative, or friend, and both can live well. Unfortunately, it is unlikely that a given donor can donate to a given patient due to blood type and tissue type incompatibilities. This opens the door for kidney exchange. Consider two donor-patient pairs, A and B. Say that each of the pairs is incompatible. Yet Donor A may be able to donate to Patient B, and Donor B to Patient A. This constitutes a cycle of length two. Somewhat longer cycles are also practical. In addition to cycles, chains are possible when there is an altruistic donor (who does not expect anything in return for his kidney donation) to initiate the chain. There are already a few disparate kidney exchanges in the US, and the United Network for Organ Sharing (UNOS) is planning a nationwide one.

We proved that the exchange clearing problem is NP-complete, and developed the only optimal algorithm for this that scales to the nationwide level. PAPER THAT DESCRIBES THAT WORK: Clearing Algorithms for Barter Exchange Markets: Enabling Nationwide Kidney Exchanges.  In Proceedings of the ACM Conference on Electronic Commerce (EC), 2007.  By Abraham, D., Blum, A., and Sandholm, T.

Our algorithm has already been used by the Alliance for Paired Donation (APD), a kidney exchange of 65 transplant centers across 15 states-the largest current kidney exchange in the US.  Several other kidney exchanges have also expressed their desire to use it.

This research epitomizes computational thinking. It is computer science playing the key role in a new area of medical science and healthcare practice. When surgeons manually make kidney transplantation decisions, they make those decisions based on visibility to only a restricted part of the problem because they see the current patient and want to help that patient. They do not necessarily take into account the fact that allocating a certain kidney to that patient will make it impossible to use that kidney for someone else at a different transplant center or at the same transplant center later on. Those other allocation decisions could be significantly better in enabling many more lives to be saved and/or better quality matches. In computer science terms the manual approach is a greedy algorithm. In contrast, we take a holistic view: we make all the centers' data available at one point and run our optimizer that finds the best transplantation decisions for the network overall.

We will tackle the following research topics on this over the next twelve months: 1. The algorithm takes an hour, and potentially longer if there are degrees of (rather than binary) compatibility. We will strive to develop faster algorithms. This will also enable sensitivity analysis of the solution to different objectives and constraints. We will also generalize the functionality of the algorithm in important ways. 2. We will study the online problem of deciding who to match now in light of the fact that new people will arrive to (and depart from) the system over time. We will not do this in the traditional adversarial model of competitive ratios, because we have already shown that such prior-free approaches cannot lead to meaningful guarantees in this setting. Rather, we will use knowledge of the blood and tissue type distribution in the population as a prior, and will extend modern sample-based online optimization approaches to this setting.

There is a clear technology transfer path for the fruits of our research. Three of the current US kidney exchanges (including both of the large ones) have already formally requested to use our technology and others (also from abroad) have made exploratory requests. UNOS has also decided to go with our technology - and future versions thereof based on our ongoing research - for the nationwide kidney exchange that they will set up.  We will continue to actively further the real-world fielding of our kidney exchange technology. The predicted size of the nationwide kidney exchange is 10,000 donor-patient pairs per batch, and our technology has the potential to save thousands of lives per year in the US alone. The approach also leads to dramatic improvements in the quality of life by moving patients off dialysis and back into the productive work force. Societal benefits come also from transplants being a significantly less expensive treatment than dialysis. (This effect has been very conservatively estimated to be $750 million in the US over five years.) Research in this area will have the most impact right now as the procedures and technologies are being established.

The techniques apply to other barter exchanges as well. Such exchanges could be set up, for example, for live-donor transplants of liver lobes and potentially also partial lungs.

The scientific impact goes even further. Many of the tree search / integer programming techniques developed for the batch problem will have broad applicability across a wide range of combinatorial optimization problems. Similarly, the techniques developed for robust planning and online planning will have applicability across a broad range of planning problems where the action space is large and/or the space of possible futures is large. Successful completion of the effort will make significant contributions to both theory and practice in multiagent systems, search, integer programming, planning under uncertainty, exchange design, electronic commerce, and transplantation. The center and MSR will benefit in all the ways listed above.  They will be able to use computational thinking to save a large number of lives. They will also capture the associated PR benefits.