We explore the theoretical and empirical efficacy of long altruist-initiated chains in kidney exchange programs. Kidney exchange, where needy patients swap incompatible donors with each other, offers a life-saving alternative to waiting for an organ from the deceased-donor waiting list. Recently, chains—sequences of transplants initiated by an altruistic kidney donor—have shown marked success in practice, yet remain poorly understood.

We first provide a theoretical analysis of the efficacy of chains in the most widely used kidney exchange model (which has a constant incompatibility probability on edges conditional on blood-type compatibility), proving that long chains do not help beyond chains of length 3 when the exchange pool grows large. This contradicts our experimental results from running the matches for the UNOS US-wide kidney exchange pilot; there, solution quality improves by increasing the chain length cap to 13 or beyond.

We study reasons for this gulf between theory and practice. For one, experiments on non-sensitized pools simulated using the Saidman et al. data generator support the theory and help determine how large the exchange pool needs to be for the theory to begin to apply.

We then conduct simulation experiments in a dynamic setting that includes a variety of real-world features such as individual cross-match sensitivity, entry and departure dynamics, chains breaking down, and chains triggered by O-donors not being carried out unless they exceed a certain length (except if the chain-triggering altruist so chooses). Experiments in the dynamic setting cannot be conducted in the large due to computational limitations, but with up to 460 candidates, a chain length cap of 4 was best (in fact, better than 5).

« Back to 2013 American Transplant Congress