Complexity and Manipulation of International Kidney Exchange Programmes with Country-Specific Parameters
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912414266556416 |
|---|---|
| author | Colley, Rachael Manlove, David Paulusma, Daniel Zhang, Mengxiao |
| author_facet | Colley, Rachael Manlove, David Paulusma, Daniel Zhang, Mengxiao |
| contents | Kidney Exchange Programmes (KEPs) facilitate the exchange of kidneys, and larger pools of recipient-donor pairs tend to yield proportionally more transplants, leading to the proposal of international KEPs (IKEPs). However, as studied by \citet{mincu2021ip}, practical limitations must be considered in IKEPs to ensure that countries remain willing to participate. Thus, we study IKEPs with country-specific parameters, represented by a tuple $Γ$, restricting the selected transplants to be feasible for the countries to conduct, e.g., imposing an upper limit on the number of consecutive exchanges within a country's borders. We provide a complete complexity dichotomy for the problem of finding a feasible (according to the constraints given by $Γ$) cycle packing with the maximum number of transplants, for every possible $Γ$. We also study the potential for countries to misreport their parameters to increase their allocation. As manipulation can harm the total number of transplants, we propose a novel individually rational and incentive compatible mechanism $\mathcal{M}_{\text{order}}$. We first give a theoretical approximation ratio for $\mathcal{M}_{\text{order}}$ in terms of the number of transplants, and show that the approximation ratio of $\mathcal{M}_{\text{order}}$ is asymptotically optimal. We then use simulations which suggest that, in practice, the performance of $\mathcal{M}_{\text{order}}$ is significantly better than this worst-case ratio. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_04092 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Complexity and Manipulation of International Kidney Exchange Programmes with Country-Specific Parameters Colley, Rachael Manlove, David Paulusma, Daniel Zhang, Mengxiao Computer Science and Game Theory Computational Complexity Theoretical Economics Kidney Exchange Programmes (KEPs) facilitate the exchange of kidneys, and larger pools of recipient-donor pairs tend to yield proportionally more transplants, leading to the proposal of international KEPs (IKEPs). However, as studied by \citet{mincu2021ip}, practical limitations must be considered in IKEPs to ensure that countries remain willing to participate. Thus, we study IKEPs with country-specific parameters, represented by a tuple $Γ$, restricting the selected transplants to be feasible for the countries to conduct, e.g., imposing an upper limit on the number of consecutive exchanges within a country's borders. We provide a complete complexity dichotomy for the problem of finding a feasible (according to the constraints given by $Γ$) cycle packing with the maximum number of transplants, for every possible $Γ$. We also study the potential for countries to misreport their parameters to increase their allocation. As manipulation can harm the total number of transplants, we propose a novel individually rational and incentive compatible mechanism $\mathcal{M}_{\text{order}}$. We first give a theoretical approximation ratio for $\mathcal{M}_{\text{order}}$ in terms of the number of transplants, and show that the approximation ratio of $\mathcal{M}_{\text{order}}$ is asymptotically optimal. We then use simulations which suggest that, in practice, the performance of $\mathcal{M}_{\text{order}}$ is significantly better than this worst-case ratio. |
| title | Complexity and Manipulation of International Kidney Exchange Programmes with Country-Specific Parameters |
| topic | Computer Science and Game Theory Computational Complexity Theoretical Economics |
| url | https://arxiv.org/abs/2506.04092 |