Computing Balanced Solutions for Large International Kidney Exchange Schemes when Cycle Length is Unbounded

In kidney exchange programmes (KEP) patients may swap their incompatible donors leading to cycles of kidney transplants. Countries try to merge their national patient-donor pools leading to international KEPs (IKEPs). Long-term stability of an IKEP can be achieved through a credit-based system. The goal is to find, in each round, an optimal solution that closely approximates this target allocation. We provide both theoretical and experimental results for the case where the cycle length is unbounded.