1048. Complexity and Manipulation of International Kidney Exchange Programs with Country-Specific Parameters
Invited abstract in session MA-11: Kidney Exchange, stream OR in Healthcare (ORAHS).
Monday, 8:30-10:00Room: Clarendon SR 1.03
Authors (first author is the speaker)
| 1. | Rachael Colley
|
| School of Computing Science, University of Glasgow | |
| 2. | David Manlove
|
| School of Computing Science, University of Glasgow | |
| 3. | Daniel Paulusma
|
| Department of Computer Science, Durham University | |
| 4. | Mengxiao Zhang
|
| School of Computer Science, University of Auckland |
Abstract
Kidney Exchange Programs (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 Mincu et al. (2021), practical limitations must be considered in IKEPs to ensure that countries remain willing to participate. Thus, in this talk, we present 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 present 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 Γ. Following this, we explain the potential for countries to misreport their parameters to increase their allocation. As manipulation can harm the total number of transplants, we introduce a novel individually rational and incentive compatible mechanism M-order. We first give a theoretical approximation ratio for M-order in terms of the number of transplants and then show that the approximation ratio of M-order is asymptotically optimal. We then use simulations to demonstrate that, in practice, the performance of M-order is significantly better than this worst-case ratio.
Keywords
- Complexity and Approximation
- Economic Modeling
- Health Care
Status: accepted
Back to the list of papers