Computing balanced solutions for large international kidney exchange schemes when cycle length is unbounded

Abstract

In kidney exchange programmes, patients with incompatible donors obtain kidneys via cycles of transplants. Countries may merge their national patient-donor pools to form international programmes. To ensure fairness, a credit-based system is used: a cooperative game-theoretic solution concept prescribes a “fair” initial allocation, which is adjusted with accumulated credits to form a target allocation. The objective is to maximize the number of transplants while staying close to the target allocation. When only 2-cycles are permitted, a solution that lexicographically minimizes deviations from the target can be found in polynomial time. However, even the problem of maximizing the number of transplants is NP-hard for larger upper bounds on cycle length. This latter problem is tractable when cycle lengths are not bounded. We formalize this setting via a new class of cooperative games called partitioned permutation games, and prove that computing an optimal solution that is lexicographically closest to the target allocation is NP-hard. We give a randomized XP-time algorithm for solve this problem exactly. We present an experimental study, simulating programmes with up to 10 countries. Allowing unbounded cycle lengths increases the number of transplants by up to 46% compared to 2-cycles. Using credits and selecting lexicographically closest solutions yields low total relative deviation (below 2% for all fairness notions). Among the seven fairness notions tested, a modified Banzhaf value performs best in balancing fairness and efficiency, achieving average deviations below 0.65%. Lexicographic minimization from the target allocation leads to significantly (36 − 56%) smaller average deviations than minimizing maximum difference only.