Abstract
A kidney-paired donation (KPD) pool consists of transplant candidates and their incompatible donors, along with nondirected donors (NDDs). In a match run, exchanges are arranged among pairs in the pool via cycles, as well as chains created from NDDs. A problem of importance is how to arrange cycles and chains to optimize the number of transplants. We outline and examine, through example and by simulation, four schemes for selecting potential matches in a realistic model of a KPD system; proposed schemes take account of probabilities that chosen transplants may not be completed as well as allowing for contingency plans when the optimal solution fails. Using data on candidate/donor pairs and NDDs from the Alliance for Paired Donation, the simulations extend over 8 match runs, with 30 pairs and 1 NDD added between each run. Schemes that incorporate uncertainties and fallbacks into the selection process yield substantially more transplants on average, increasing the number of transplants by as much as 40% compared to a standard selection scheme. The gain depends on the degree of uncertainty in the system. The proposed approaches can be easily implemented and provide substantial advantages over current KPD matching algorithms.