Computing international kidney exchange schemes

In kidney exchange, patients may swap their donors to solve incompatibility issues. In international kidney exchange, countries merge their national patient-donor pools. We consider a recently introduced credit system where in each round, countries are given an initial kidney transplant allocation which is adjusted by a credit function yielding a target allocation. The goal is to find a solution in the patient-donor compatibility graph that approaches the target allocation as closely as possible, to ensure long-term stability of the international pool. Our aim is to perform, for the first time, a computational study for a large number of countries using sophisticated methods. We therefore focus on the case where the kidney exchanges must form a maximum matching. As solutions, we use maximum matchings that lexicographically minimize the country deviations from the target allocation. The theoretical contribution of the paper is a polynomial-time algorithm for computing such matchings. For the initial allocations we use, in addition to easy-to-compute solution concepts, two classical solution concepts, namely the Shapley value and nucleolus. These solution concepts are hard to compute but we show that by using state-of-the-art software combined with our new polynomial-time matching algorithm, they are now within reach for international kidney exchange programs of up to fifteen countries. Our experiments show that using lexicographically minimal maximum matchings instead of ones that minimize the largest deviation only makes an international kidney exchange scheme up to 56% more balanced.