The presentation will take place in a hybrid format via zoom interface or in person in the room K.0.11-12 on 06.02.2025, from 13.00.
Speaker: Csáji, Gergely
Title: Finding Fair Solutions in International Kidney Exchange Problems
Abstract:
In kidney exchange programmes (KEP) patients may swap their incompatible donors leading to cycles of kidney transplants. Nowadays, countries try to merge their national patient-donor pools leading to international KEPs (IKEPs). A proposed way of achieving long-term stability in an IKEP is the use of a credit-based system. In each round, every country is prescribed a “fair” initial allocation of kidney transplants. The initial allocation, which we obtain by using solution concepts from cooperative game theory, is then adjusted by incorporating credits from the previous round, yielding the target allocation. The goal is to find, in each round, an optimal solution that closely approximates this target allocation.
Following the research of [Benedek et al.], where IKEPs were studied with only pairwise exchanges allowed, we investigate the case, where the cycle length is unbounded. For this, we introduce the Partitioned Permutation Game. We obtain several theoretical results on the complexity of finding optimal solutions that are close to a given target allocation, and about finding and verifying solutions in the core. We also perform a large-scale simulation study and obtain several interesting insights.
In the second part, we explore the non-transferable utility (NTU) variant of the Partitioned Matching game, where the utility of players is given by the number of their matched vertices. The NTU version is arguably a more natural model of the international kidney exchange program, as the utility of a participating country mostly depends on how many of its patients receive a kidney, which is non-transferable by nature. We study the core of this
game, which suitably captures the notion of stability of an IKEP, as it precludes incentives to deviate from the proposed solution for any possible coalition of the players. We prove several algorithmic and computational complexity results about the weak and strong cores under various assumptions on the players.
