Computing Balanced Solutions for Large International Kidney Exchange Schemes

Benedek, Márton; Biró, Péter; Kern, Walter; Paulusma, Daniel

Abstract

To overcome incompatibility issues, kidney patients may swap their donors. In international kidney exchange programmes (IKEPs), countries merge their national patient–donor pools. We consider a recently introduced credit system. In each round, countries are given an initial “fair” allocation of the total number of kidney transplants. This allocation is adjusted by a credit function yielding a target allocation. The goal is to find a solution that approaches the target allocation as closely as possible, to ensure long-term stability of the international pool. As solutions, we use maximum matchings that lexicographically minimize the country deviations from the target allocation. We perform, for the first time, a computational study for a large number of countries. For the initial allocations we use two easy-to-compute solution concepts, the benefit value and the contribution value, and four classical but hard-to-compute concepts, the Shapley value, nucleolus, Banzhaf value and tau value. By using state-of-the-art software we show that the latter four concepts are now within reach for IKEPs of up to fifteen countries. Our experiments show that using lexicographically minimal maximum matchings instead of ones that only minimize the largest deviation from the target allocation (as previously done) may make an IKEP up to 54% more balanced.

Citation

Benedek, M., Biró, P., Kern, W., & Paulusma, D. (2022, May). Computing Balanced Solutions for Large International Kidney Exchange Schemes. Presented at AAMAS ' 22: International Conference on Autonomous Agents and Multi-Agent Systems, Virtual Event / New Zealand

• Presentation Conference Type: Conference Paper (published)
• Conference Name: AAMAS ' 22: International Conference on Autonomous Agents and Multi-Agent Systems
• Start Date: May 9, 2022
• End Date: May 13, 2022
• Acceptance Date: Mar 31, 2022
• Online Publication Date: May 9, 2022
• Publication Date: 2022-05
• Deposit Date: Dec 31, 2021
• Publicly Available Date: Oct 17, 2022
• Publisher: Association for Computing Machinery (ACM)
• Peer Reviewed: Peer Reviewed
• Pages: 82-90
• Book Title: AAMAS '22: Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems
• ISBN: 9781450392136
• DOI: https://doi.org/10.5555/3535850.3535861
• Keywords: Kidney exchange, Simulation, Matching game, Credit system, Solution concept
• Public URL: https://durham-repository.worktribe.com/output/1137759
• Publisher URL: https://dl.acm.org/doi/10.5555/3535850.3535861