Computing Balanced Solutions for International Kidney Exchange
Schemes

Abstract

In kidney exchange programmes (KEPs) patients may swap their incompatible donors leading to cycles of kidney transplants. Nowadays, countries have begun merging their national KEPs into international KEPs (IKEPs) to increase the overall number of transplants (social welfare). To ensure the longer-term stability of IKEPs, a credit-based system is introduced. In each round, every country is prescribed a ``fair'' initial allocation of kidney transplants. The initial allocation, which is obtained by using solution concepts from cooperative game theory, is adjusted by incorporating credits from the previous round, yielding a target allocation for each country. The overall goal is to find, in each round, an optimal solution, maximizing the total number of kidney transplants that approximates the target allocation vector as close as possible.

However, the maximum exchange cycle length, denoted by , is often restricted by logistical, practical and legal considerations. It is known that the complexity of computing an optimal solution is polynomial when or ; otherwise, it is NP-hard. It is polynomial to find an optimal solution that lexicographically minimizes the country deviations from the target allocation if is permitted. However, in practice, kidney transplants along longer cycles may be performed. To an extreme, namely, , we show that the lexicographical minimization is only polynomial-time solvable for under additional conditions (assuming ). Nevertheless, the fact that the optimal solutions themselves can be computed in polynomial time if still enables us to perform an experimental study for a large number of countries. Furthermore, is permitted in some European countries, such as UK and Netherlands. Even though computing optimal solutions for is NP-hard, we perform simulations by formulating integer linear programs (ILPs) and utilizing ILP solvers. As a whole, we perform large-scale and consistent simulation studies for , and and examine how the transitions from to , and from to , affect both stability and total social welfare.