Papers › Computing Balanced Solutions for Large International Kidney Exchange Schemes When...
Computing Balanced Solutions for Large International Kidney Exchange Schemes When Cycle Length Is Unbounded
Márton Benedek, Péter Biró, Gergely Csáji, Matthew Johnson, Daniël Paulusma, Xin Ye
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
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). As shown in the literature, long-term stability of an IKEP can be achieved through 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 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. There is a known polynomial-time algorithm for finding an optimal solution that lexicographically minimizes the country deviations from the target allocation if only $2$-cycles (matchings) are permitted. In practice, kidney swaps along longer cycles may be performed. However, the problem of computing optimal solutions for maximum cycle length ℓ is NP-hard for every ℓ≥3. This situation changes back to polynomial time once we allow unbounded cycle length. However, in contrast to the case where ℓ=2, we show that for ℓ=∞, lexicographical minimization is only polynomial-time solvable under additional conditions (assuming P ≠ NP). Nevertheless, the fact that the optimal solutions themselves can be computed in polynomial time if ℓ=∞ still enables us to perform a large scale experimental study for showing how stability and total social welfare are affected when we set ℓ=∞ instead of ℓ=2.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections