Not every kidney patient who finds a person who is willing and able to be a live donor will be able to get a kidney from that donor. Even if the donor is healthy, the pair may have incompatible blood types or be HLA-incompatible. Historically, this meant the patient would not be able to get a live donor transplant and had to wait for a cadaver kidney.

However, this isn’t necessary. It is possible to create a kidney exchange. Two (or sometimes more) unmatched donor-recipient pairs could swap partners. In economic parlance, the recipients (the kidney patients) are considered traders in the exchange and the donors (or actually their kidneys) are considered the goods. All traders wants kidneys that will match them based on blood type and HLA compatibility. There may be other constraints like travel that can also be accommodated by trading.

The first kidney exchanges were local, usually involving a single transplant center. Patients had a hard time finding the exchanges and the pool of traders in any one exchange was quite small. This made it very hard to find a match. In order to improve the chances of a match two national organizations arose. The National Kidney Registry was started by the father of a kidney patient. The Alliance for Paired Donation was created by a transplant surgeon at the University of Toledo. I have signed up with both organizations (see Nov 2007 blog post) in an attempt to participate in a kidney exchange.

Let’s take a look at how a typical paired transaction works. In the example shown below, two donor/recipient pairs (labeled 0 and 1) get together and discover that they can trade kidneys among themselves and provide a transplant for each recipient. The chain can grow with round robin exchanges between 3-pairs, 4-pairs, etc.


A simple 2-pair exchange. Image by George Taniwaki

Now let’s take a look at a slightly more complex case where the trading pool consists of 20 recipient/donor pairs. Each circle represents an unmatched donor/recipient pair. The lines indicate all the possible 2-pair transactions that can occur like the one shown above.


An exchange with 20 pairs. Image from Optimized Match

There are lots of potential trades available. How should we decide which trades should be made? Do we leave it up to the individuals? Or maybe assign trades starting with pair 0 and move sequentially (called the first-match algorithm)? Both methods are used today. It turns out that using either of these methods will leave a lot of participants without a match. If our goal is to maximize the total number of matches, we should let a computer create a tree of all the potential matches and then examine all the combinations to find the one with the most matches.

It turns out this matching problem is NP-complete (or NP-hard, depending on the number of pairs we allow in a single exchange). Solving problems that are NP-complete is computationally expensive because the time it takes to solve them grows faster than a polynomial of the number of elements. Eventually, the number of elements gets too large and the problem become unsolvable. That is, it will take up more computing resources (CPU time, memory, etc.) than is available.

NP-complete problems are not rare. There are lots of real-world NP-complete problems that are encountered daily. How should United Airlines schedule its planes and crew, what paths should UPS delivery trucks take, where should Wal-mart open its next store, etc. To make these problems solvable in a finite amount of time with a finite amount of resources, we rely on various approximation algorithms that produce good solutions, but that may not be optimum solutions.

The first researchers to consider the kidney exchange problem in detail are Dorry Segev and Sommer Gentry, a husband and wife team that run Optimized Match. He is a transplant surgeon at Johns Hopkins and she is a mathematics professor at the U.S. Naval Academy. They and other colleagues published a paper in the J. Amer. Med. Assoc. 2005 showing that the Edmond algorithm produced much better results than the first-match algorithm. If applied nationwide to a pool of 4,000 potential recipients, it could result in 750 more transplants in the first year (before the pool is depleted), with a possible savings of nearly $750 million compared to the cost of dialysis.

Using simulated data, they also found that it would result in more patients getting transplants (47.7 percent vs. 42.0 percent), better matches, and more grafts surviving at 5 years when compared with an extension of the currently used first-match algorithm. Highly sensitized patients, who are extremely difficult to match and typically wait almost 7 years for a deceased donor kidney, would benefit 6-fold by using the Edmond algorithm (14.1 percent vs. 2.3 percent). Even more surprising, switching from local pools to a national program would dramatically reduce the number of pairs required to travel (2.9 percent vs. 18.4 percent).

As noted above, the Edmond algorithm is an approximation that conserves computing resources. However, for kidney exchanges, the small percentage of error in matching represents real people who could die if they don’t get a transplant. So it would be better if we can find a way to get the optimum solution to the exchange problem even if it takes more computing effort.

An early exact matching algorithm was developed by Al Roth, an economist at Harvard, and his collaborators. They modified an existing linear programing algorithm that uses the simplex method to match students to dorm rooms. Their research was presented in the Quar. J. Econ. May 2004 and J. Econ. Theory Dec 2005. The algorithm was quickly adopted by many transplant organizations such as New England Program for Kidney Exchange (NEPKE), University of Michigan Health System, and the Alliance for Paired Donations (APD). An article featuring an early paired exchange appeared in Miller-McCune Mar 2009. The National Kidney Registry developed its own similar algorithm called BestMatch which resulted in the first 6-HLA matches among strangers, press release Feb 2008.

Unfortunately, the simplex algorithm is very inefficient at solving this exchange problem and cannot scale to meet the needs of a national kidney database. One clever solution has been found by Tuomas Sandholm and his colleagues at Carnegie Mellon University. Their integer programming algorithm can provide the exact solution (not an approximation) of the NP-hard exchange problem in nearly polynomial time. They published their results in ACM Conf. Electr. Comm. 2007. The algorithm scales to tens of thousands of patients. The chart below shows that with 500 patients their new algorithm takes a few seconds to find the best matches, while the current CPLEX algorithm takes several minutes. When the pool increases to 1,000 patients, the new algorithm takes a few minutes while CPLEX no longer works. By the time the pool gets to 10,000 patients, the new algorithm still only take an hour or two to find the best combination of trades.

The new method has been adopted by both the Alliance for Paired Donation and the NEPKE. It is also the basis of the algorithm being used by the UNOS in its national trial of a kidney exchange. Mr. Sandholm is one of several academics on the design committee for the trial. An article on the APD’s pursuit of kidney exchanges appears in the Toledo Blade Mar 2009.


Image from ACM

In upcoming posts I’ll discuss extensions to the kidney exchange model for multiple rounds, the matching problem facing patients with O blood type that cannot be easily solved by improvements to kidney exchange software alone, and additional software for managing kidney transplant casework.

[Update: Corrected list of exchanges using integer programming.]