Actions

Download Analytics Citations

Export to: EndNote  |  Zotero  |  Mendeley

Collections

This file is not currently in any collections.

Computing Balanced Solutions for Large International Kidney Exchange Schemes When Cycle Length Is Unbounded [dataset] Open Access

In kidney exchange programmes (KEP) patients may swap their incompatible donors leading to cycles of kidney transplants. Recently, 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~$\ell$ is \NP-hard for every $\ell\geq 3$. By contrast, the problem is polynomial time solvable once we allow unbounded cycle length. However, in contrast to the case where $\ell=2$, we show that for $\ell=\infty$, lexicographical minimization is only polynomial-time solvable under additional conditions (assuming $\sP\neq \NP$). Nevertheless, the fact that the optimal solutions themselves can be computed in polynomial time if $\ell=\infty$ still enables us to perform a large scale experimental study for showing how stability and total social welfare are affected when we set $\ell=\infty$ instead of $\ell=2$.

Descriptions

Resource type

Dataset

Contributors

Benedek, Marton ¹
Biro, Peter ¹
Csaji, Gergely ¹
Johnson, Matthew ²
Paulusma, Daniel ²
Creator: Ye, Xin ²

¹ KRTK, Institute of Economics, Budapest, Hungary
² Durham University, UK

Funder

Országos Tudományos Kutatási Alapprogramok
Corvinus University, Budapest, Hungary
Magyar Tudományos Akadémia
Leverhulme Trust

Research methods

Other description

Keyword

International kidney exchange program

Subject

Kidneys--Transplantation

Location

Language

Cited in

doi:10.1007/s10458-024-09645-w
https://www.ifaamas.org/Proceedings/aamas2024/pdfs/p2153.pdf

Identifier

ark:/32150/r28336h194z
doi:10.15128/r28336h194z

Rights

Creative Commons Attribution 4.0 International (CC BY)

Publisher

Durham University

Date Created

File Details

Depositor

X. Ye

Date Uploaded

17 February 2025, 13:02:19

Date Modified

21 February 2025, 10:02:19

Audit Status

Audits have not yet been run on this file.

Characterization

File format: zip (ZIP Format)

Mime type: application/zip

File size: 206507896

Last modified: 2025:02:21 09:38:34+00:00

Filename: ResearchData.zip

Original checksum: 86825a6c23c760a575d2268b5202eb96