Complexity and Manipulation of International Kidney Exchange Programmes with Country-Specific Parameters

Abstract

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 $\hat{I}“$, 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 $\hat{I}“$) cycle packing with the maximum number of transplants, for every possible $\hat{I}“$. 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.

51 pages, 19 figures