For a variety of practical reasons, including crossmatch failures, most planned kidney exchange transplants do not go to transplant in reality. This is arguably the most important challenge in kidney exchanges today.

We analyze the inclusion of probabilistic match failures in standard kidney exchange models. We address two presently unsolved problems in kidney exchange: first, how the efficacy of altruist-initiated donor chains changes as chain length increases, and second, how to match robustly in the face of post-algorithmic match transplant failures. Solutions to these problems will lower the gap between the number of algorithmically matched candidates and donors, and the number of matches that actually go through to transplant in reality.

We begin by proving results in a standard theoretical model of kidney exchange, augmented to include an explicit match failure probability. Let q be this probability—that is, the probability that an otherwise legal candidate-donor match fails exogenously after an algorithmic match has taken place. We show, for realistic values of q in this model, matching to maximize cardinality (i.e., total lives saved) is significantly worse than matching by taking these failure probabilities into account (with high probability). This has strong theoretical and practical implications for the consideration of long altruist-initiated transplant chains. While long chains may maximize cardinality at algorithmic matching time, the high probability of a chain failing makes long chains less useful in reality, once post-match failure probabilities are taken into account.

Then, we prove that under a random graph model (with blood types, uniform edge (compatibility) probability given blood compatibility, and at least reasonably high pre-transplant failure probability), in the large, 2-cycles suffice with probability one in achieving the optimal clearing. Such a clearing can be computed quickly even in the worst case, and used in our clearing algorithm, which is to our knowledge the only scalable optimization algorithm for modern kidney exchanges, and is the algorithm used by UNOS. Also, the probabilistic approach may help prune many long chains from consideration, which cause most complexity in the clearing algorithm in practice.

We present empirical feasibility results on generated data from a state-of-the-art kidney exchange generator, and empirically show the benefits of including post-match failure probabilities in currently fielded kidney exchange programs.

« Back to 2013 American Transplant Congress