×

IP solutions for international kidney exchange programmes. (English) Zbl 07381768

Summary: In kidney exchange programmes patients with end-stage renal failure may exchange their willing, but incompatible living donors among each other. National kidney exchange programmes are in operation in ten European countries, and some of them have already conducted international exchanges through regulated collaborations. The exchanges are selected by conducting regular matching runs (typically every three months) according to well-defined constraints and optimisation criteria, which may differ across countries. In this work we give integer programming formulations for solving international kidney exchange problems, where the optimisation goals and constraints may be different in the participating countries and various feasibility criteria may apply for the international cycles and chains. We also conduct simulations showing the long-run effects of international collaborations for different pools and under various national restrictions and objectives. We compute the expected gains of the cooperation between two countries with different pool sizes and different restrictions on the cycle-length. For instance, if country A allows 3-way cycles and country B allows 2-way cycles only, whilst the pool size of country A is four times larger than the pool size of country B (which is a realistic case for the relation of Spain and France, respectively), then the increase in the number of transplants will be about 2% for country A and about 37% for country B.

MSC:

90Bxx Operations research and management science
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Abraham DJ, Blum A, Sandholm T (2007) Clearing algorithms for barter exchange markets: enabling nationwide kidney exchanges. In: Proceedings on EC ’07: the 8th ACM conference on electronic commerce. ACM, pp 295-304
[2] Agarwal N, Ashlagi I, Azevedo E, Featherstone CR, Karaduman Ö (2018) Market failure in kidney exchange. Technical report, National Bureau of Economic Research
[3] Andersson T, Kratz J (2016) Pairwise kidney exchange over the blood group barrier. Lund University Department of Economics Working Paper, 2016, p 11 · Zbl 1460.91167
[4] Ashlagi, I.; Fischer, F.; Kash, IA; Procaccia, AD, Mix and match: a strategyproof mechanism for multi-hospital kidney exchange, Games Econ Behav, 91, Supplement C, 284-296 (2015) · Zbl 1318.91143 · doi:10.1016/j.geb.2013.05.008
[5] Ashlagi, I.; Roth, A., New challenges in multihospital kidney exchange, Am Econ Rev, 102, 3, 354-359 (2012) · doi:10.1257/aer.102.3.354
[6] Ashlagi, I.; Roth, AE, Free riding and participation in large scale, multi-hospital kidney exchange, Theor Econ, 9, 3, 817-863 (2014) · Zbl 1395.91337 · doi:10.3982/TE1357
[7] Biró P, Haase B et al (2018) Building kidney exchange programmes in Europe—an overview of exchange practice and activities. Transplantation (to appear)
[8] Böhmig, GA; Fronek, J.; Slavcev, A.; Fischer, GF; Berlakovich, G.; Viklicky, O., Czech-Austrian kidney paired donation: first European cross-border living donor kidney exchange, Transpl Int, 30, 6, 638-639 (2017) · doi:10.1111/tri.12945
[9] Carvalho, M.; Lodi, A.; Pedroso, JP; Viana, A., Nash equilibria in the two-player kidney exchange game, Math Program, 161, 1-2, 389-417 (2017) · Zbl 1414.91289 · doi:10.1007/s10107-016-1013-7
[10] Constantino, M.; Klimentova, X.; Viana, A.; Rais, A., New insights on integer-programming models for the kidney exchange problem, Eur J Oper Res, 231, 1, 57-68 (2013) · Zbl 1317.90174 · doi:10.1016/j.ejor.2013.05.025
[11] De Klerk, M.; Keizer, KM; Claas, FHJ; Witvliet, M.; Haase-Kromwijk, B.; Weimar, W., The Dutch national living donor kidney exchange program, Am J Transplant, 5, 9, 2302-2305 (2005) · doi:10.1111/j.1600-6143.2005.01024.x
[12] Hajaj C, Dickerson J, Hassidim A, Sandholm T, Sarne D (2015) Strategy-proof and efficient kidney exchange using a credit mechanism. In: Proceedings of the twenty-ninth AAAI conference on artificial intelligence, pp 921-928
[13] Klimentova X, Santos N, Pedroso JP, Viana A (2019) Fairness models for multi-agent kidney exchange programs. Working paper
[14] Manlove DF, O’Malley G (2014) Paired and altruistic kidney donation in the UK: algorithms and experimentation. ACM J Exp Algorithmics 19(2), article 2.6, 21pp
[15] Rees, MA; Kopke, JE; Pelletier, RP; Segev, DL; Rutter, ME; Fabrega, AJ; Rogers, J.; Pankewycz, OG; Hiller, J.; Roth, AE; Sandholm, T.; Ünver, MU; Montgomery, RA, A nonsimultaneous, extended, altruistic-donor chain, N Engl J Med, 360, 11, 1096-1101 (2009) · doi:10.1056/NEJMoa0803645
[16] Santos, N.; Tubertini, P.; Viana, A.; Pedroso, JP, Kidney exchange simulation and optimization, J Oper Res Soc, 12, 1-12 (2017)
[17] Toulis, P.; Parkes, DC, Design and analysis of multi-hospital kidney exchange mechanisms using random graphs., Games Econ Behav, 91, Supplement C, 360-382 (2015) · Zbl 1318.91148 · doi:10.1016/j.geb.2015.01.001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.