David F. Manlove
Skip Abstract Section
Abstract
We study the computational problem of identifying optimal sets of kidney exchanges in the UK. We show how to expand an integer programming-based formulation due to Roth et al. [2007] in order to model the criteria that constitute the UK definition of optimality. The software arising from this work has been used by the National Health Service Blood and Transplant to find optimal sets of kidney exchanges for their National Living Donor Kidney Sharing Schemes since July 2008. We report on the characteristics of the solutions that have been obtained in matching runs of the scheme since this time. We then present empirical results arising from experiments on the real datasets that stem from these matching runs, with the aim of establishing the extent to which the particular optimality criteria that are present in the UK influence the structure of the solutions that are ultimately computed. A key observation is that allowing four-way exchanges would be likely to lead to a moderate number of additional transplants.
- D. Abraham, A. Blum, and T. Sandholm. 2007. Clearing algorithms for barter exchange markets: Enabling nationwide kidney exchanges. In Proceedings of the 8th ACM Conference on Electronic Commerce (EC’07). ACM, 295--304. Google Scholar
Digital Library
- R. Anderson, I. Ashlagi, and D. Gamarnik. 2012. A dynamic model of kidney exchange programs. Extended abstract of poster presented at the 2012 Stochastic Networks Conference. Retrieved from http://stoch-nets-2012.lids.mit.edu/posters/Anderson.pdf.Google Scholar
- Alliance for Paired Donation website. http://www.paireddonation.org (accessed August 20, 2014).Google Scholar
- I. Ashlagi, F. Fischer, I. Kash, and A. D. Procaccia. 2010. Mix and match. In Proceedings of the 11th ACM Conference on Electronic Commerce. ACM, 305--314. Google ScholarDigital Library
- I. Ashlagi, D. Gamarnik, M. Rees, and A. Roth. 2012. The Need for (Long) Chains in Kidney Exchange. Working Paper 18202, National Bureau of Economic Research, Cambridge, MA. Retrieved from http://www.nber.org/papers/w18202.Google Scholar
- I. Ashlagi, D. Gilchrist, A. Roth, and M. Rees. 2011. Nonsimultaneous chains and dominos in kidney paired donation -- revisited. American Journal of Transplantation 11, 5, 984--994.Google ScholarCross Ref
- I. Ashlagi and A. Roth. 2011. Individual rationality and participation in large scale, multi-hospital kidney exchange. In Proceedings of the 12th ACM Conference on Electronic Commerce. ACM, 321--322. Google ScholarDigital Library
- I. Ashlagi and A. Roth. 2012. New challenges in multihospital kidney exchange. American Economic Review 102, 3, 354--359.Google ScholarCross Ref
- P. Awasthi and T. Sandholm. 2009. Online stochastic optimization in the large: Application to kidney exchange. In Proceedings of the 21st International Joint Conference on Artificial Intelligence. Morgan Kaufmann, 405--411. Google ScholarDigital Library
- C. Barnhart, E. Johnson, G. Nemhauser, M. Savelsbergh, and P. Vance. 1998. Branch-and-price: Column generation for solving huge integer programs. Operations Research 46, 316--329. Google ScholarDigital Library
- P. Biró, D. Manlove, and R. Rizzi. 2009. Maximum weight cycle packing in directed graphs, with application to kidney exchange. Discrete Mathematics, Algorithms and Applications 1, 4, 499--517.Google ScholarCross Ref
- I. Caragiannis, A. Filos-Ratsikas, and A. Procaccia. 2011. An improved 2-agent kidney exchange mechanism. In Proceedings of the 7th International Workshop on Internet and Network Economics. Lecture Notes in Computer Science Series, vol. 7090. Springer, 37--48. Google ScholarDigital Library
- Y. Chen, Y. Li, J. Kalbfleisch, Y. Zhou, A. Leichtman, and P. Song. 2012. Graph-based optimization algorithm and software on kidney exchanges. IEEE Transactions on Biomedical Engineering 59, 7, 1985--1991.Google ScholarCross Ref
- M. Constantino, X. Klimentova, A. Viana, and A. Rais. 2013. New insights on integer-programming models for the kidney exchange problem. European Journal of Operational Research 231, 1, 57--68.Google ScholarCross Ref
- K. Deb. 2014. Multi-objective optimization. In Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques (2nd ed.), E. Burke and G. Kendall, Eds. Springer, 403--449.Google Scholar
- J. Dickerson, A. Procaccia, and T. Sandholm. 2012a. Dynamic matching via weighted myopia with application to kidney exchange. In Proceedings of the 26th AAAI Conference on Artificial Intelligence. AAAI Press, 1340--1346.Google Scholar
- J. Dickerson, A. Procaccia, and T. Sandholm. 2012b. Optimizing kidney exchange with transplant chains: Theory and reality. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems. Vol. 2. International Foundation for Autonomous Agents and Multiagent Systems, 711--718. Google ScholarDigital Library
- J. Dickerson, A. Procaccia, and T. Sandholm. 2013. Failure-aware kidney exchange. In Proceedings of the 14th ACM Conference on Electronic Commerce. ACM, 323--340. Google ScholarDigital Library
- S. Gentry, D. Segev, M. Simmerling, and R. Montgomery. 2007. Expanding kidney paired donation through participation by compatible pairs. American Journal of Transplantation 7, 2361--2370.Google ScholarCross Ref
- K. Glorie and J. van de Klundert. 2012. Iterative branch-and-price for large multi-criteria kidney exchange. Econometric Institute Report 2012-11, Erasmus University Rotterdam.Google Scholar
- R. Johnson, J. Allen, S. Fuggle, J. Bradley, and C. Rudge. 2008. Early experience of paired living kidney donation in the United Kingdom. Transplantation 86, 1672--1677.Google ScholarCross Ref
- K. Keizer, M. de Klerk, B. Haase-Kromwijk, and W. Weimar. 2005. The Dutch algorithm for allocation in living donor kidney exchange. Transplantation Proceedings 37, 589--591.Google ScholarCross Ref
- M. de Klerk, K. Keizer, F. Claas, M. Witvliet, B. Haase-Kromwijk, and W. Weimar. 2005. The Dutch national living donor kidney exchange program. American Journal of Transplantation 5, 2302--2305.Google ScholarCross Ref
- B. S. Kim, Y. S. Kim, S. I. Kim, M. S. Kim, H. Y. Lee, Y. L. Kim, C. D. Kim, C. W. Yang, B. S. Choi, D. J. Han, Y. S. Kim, S. J. Kim, H. Y. Kim, and D. J. Kim. 2007. Outcome of multipair donor kidney exchange by a web-based algorithm. Journal of the American Society of Nephrology 18, 3, 1001--1006.Google ScholarCross Ref
- J. Kwak, O. Kwon, K. Lee, C. Kang, H. Park, and J. Kim. 1999. Exchange-donor program in kidney transplantation: A single-center experience. Transplantation Proceedings 31, 344--345.Google ScholarCross Ref
- Y. Li, P. Song, Y. Zhou, A. Leichtman, M. Rees, and J. Kalbfleisch. 2014. Optimal decisions for organ exchanges in a kidney paired donation program. Statistics in Biosciences 6, 85--104.Google ScholarCross Ref
- M. Lucan. 2007. Five years of single-center experience with paired kidney exchange transplantation. Transplantation Proceedings 39, 1371--1375.Google ScholarCross Ref
- M. Lucan, P. Rotariu, D. Neculoiu, and G. Iacob. 2003. Kidney exchange program: A viable alternative in countries with low rate of cadaver harvesting. Transplantation Proceedings 35, 933--934.Google ScholarCross Ref
- S. Micali and V. Vazirani. 1980. An O(√|V| ṡ |E|) algorithm for finding maximum matching in general graphs. In Proceedings of the 21st Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society, 17--27. Google ScholarDigital Library
- R. Montgomery, S. Gentry, W. Marks, D. Warren, J. Hiller, J. Houp, A. Zachary, J. Melancon, W. Maley, H. Rabb, C. Simpkins, and D. Segev. 2006. Domino paired kidney donation: A strategy to make best use of live non-directed donation. The Lancet 368, 9533, 419--421.Google Scholar
- National Kidney Registry. 2013. Alliance for Paired Donation. Retrieved from http://www.kidneyregistry.org.Google Scholar
- NHS Blood and Transplant. 2012. Transplant Activity Report 2011-12. Retrieved from http://www.organdonation.nhs.uk/statistics/transplant_activity_report/archive_activity_reports/pdf/ukt/activity_report_2011_12.pdf.Google Scholar
- K. Park, J. Lee, S. Kim, and Y. Kim. 2004. Exchange living-donor kidney transplantation: Diminution of donor organ shortage. Transplantation Proceedings 36, 2949--2951.Google ScholarCross Ref
- K. Park, J. Moon, S. Kim, and Y. Kim. 1999. Exchange-donor program in kidney transplantation. Transplantation Proceedings 31, 356--357.Google ScholarCross Ref
- J. P. Pedroso. 2014. Maximizing expectation on vertex-disjoint cycle packing. In Proceedings of the 14th International Conference on Computational Science and Its Applications. Lecture Notes in Computer Science Series, vol. 8580. Springer, 32--46.Google Scholar
- M. Rees, J. Kopke, R. Pelletier, D. Segev, M. Rutter, A. Fabrega, J. Rogers, O. Pankewycz, J. Hiller, A. Roth, T. Sandholm, M. Ünver, and R. Montgomery. 2009. A nonsimultaneous, extended, altruistic-donor chain. New England Journal of Medicine 360, 11, 1096--1101.Google ScholarCross Ref
- A. Roth, T. Sönmez, and M. Ünver. 2004. Kidney exchange. Quarterly Journal of Economics 119, 2, 457--488.Google ScholarCross Ref
- A. Roth, T. Sönmez, and M. Ünver. 2005. Pairwise kidney exchange. Journal of Economic Theory 125, 151--188.Google ScholarCross Ref
- A. Roth, T. Sönmez, and M. Ünver. 2007. Efficient kidney exchange: Coincidence of wants in a market with compatibility-based preferences. American Economic Review 97, 3, 828--851.Google ScholarCross Ref
- A. Roth, T. Sönmez, M. Ünver, F. Delmonico, and S. Saidman. 2006. Utilizing list exchange and nondirected donation through ‘chain’ paired kidney donations. American Journal of Transplantation 6, 11, 2694--2705.Google ScholarCross Ref
- S. Saidman, A. Roth, T. Sönmez, M. Ünver, and S. Delmonico. 2006. Increasing the opportunity of live kidney donation by matching for two and three way exchanges. Transplantation 81, 5, 773--782.Google ScholarCross Ref
- S. Segev, S. Gentry, D. Warren, B. Reeb, and R. Montgomery. 2005. Kidney paired donation and optimizing the use of live donor organs. Journal of the American Medical Association 293, 1883--1890.Google ScholarCross Ref
- P. Toulis and D. Parkes. 2011. A random graph model of kidney exchanges: efficiency, individual-rationality and incentives. In Proceedings of the 12th ACM Conference on Electronic Commerce. ACM, 323--332. Google ScholarDigital Library
- United Network for Organ Sharing. 2013. Homepage. Retrieved from http://www.unos.org.Google Scholar
- M. Ünver. 2010. Dynamic kidney exchange. Review of Economic Studies 77, 372--414.Google ScholarCross Ref
Index Terms
- Paired and Altruistic Kidney Donation in the UK: Algorithms and Experimentation
Recommendations
Position-Indexed Formulations for Kidney Exchange
EC '16: Proceedings of the 2016 ACM Conference on Economics and ComputationA kidney exchange is an organized barter market where patients in need of a kidney swap willing but incompatible donors. Determining an optimal set of exchanges is theoretically and empirically hard. Traditionally, exchanges took place in cycles, with ...
Using Deceased-Donor Kidneys to Initiate Chains of Living Donor Kidney Paired Donations: Algorithm and Experimentation
AIES '19: Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and SocietyWe design a flexible algorithm that exploits deceased donor kidneys to initiate chains of living donor kidney paired donations, combining deceased and living donor allocation mechanisms to improve the quantity and quality of kidney transplants. The ...
Kidney Exchange and the Alliance for Paired Donation: Operations Research Changes the Way Kidneys Are Transplanted
Many end-stage renal disease sufferers who require a kidney transplant to prolong their lives have a relative or friend who has volunteered to donate a kidney to them, but whose kidney is incompatible with the intended recipient. This incompatibility ...
Comments