Tutorial at AAAI-16

Organ Exchange

A Fielded Testbed for AI & Healthcare

A 3.5-hour tutorial to be held on Friday, February 12 at the Thirtieth AAAI Conference on Artificial Intelligence (AAAI-16).

Download Syllabus Download Slides

Description of Tutorial

This tutorial covers past and current research in organ exchange, a method by which patients in need of a organ can swap willing but incompatible donors. Throughout, it also gives a higher-level overview of the steps taken to translate a purely academic idea into a large fielded healthcare system.

We focus on the computational aspects of organ exchange, starting by introducing past research that has now been implemented in real-world kidney exchange (or deemed impractical and not yet fielded) and then by covering the current research problems available at the intersection of AI, optimization, and economics. We especially dives into the computational methods developed and used to solve extremely large discrete optimization problems that reflect kidney exchange, along with the interplay between modeling decisions, computational tractability, exchange efficiency, equity, dynamism in matching, and a variety of other real-world constraints and considerations.

While we focus on kidney exchange, research toward exchanges for other organs such as livers and lungs, as well as cross-organ exchanges, will also be covered.

This tutorial will be accessible to the general attendee of AAAI and should not require specialized knowledge in a specific subfield of AI.

About the Presenters

John P. Dickerson

John P. Dickerson

John is a final-year Ph.D. candidate in the Computer Science Department at Carnegie Mellon University. He has published extensively on kidney and general organ exchange in AI and OR venues; that work has set policy at the United Network for Organ Sharing (UNOS) nationwide kidney exchange. He is an NDSEG Fellow, Facebook Fellow, and Siebel Scholar.

Homepage »

Tuomas Sandholm

Tuomas Sandholm

Tuomas is Professor at CMU’s Computer Science Department. His algorithms run the national kidney exchange of 143 transplant centers; his kidney exchange designs have been adopted worldwide. He published 450 papers and fielded 800 largest-scale combinatorial auctions totaling $60 billion. He is Founder/CEO of Optimized Markets, for advertising campaign sales/scheduling.

Homepage »

Outline of the Tutorial ( pdf)

The following is an outline for our 3.5-hour tutorial on kidney exchange. It assumes an intermission at the 1.75-hour mark. We include a reference or two to a sample paper related to a specific point in the outline in the pdf version of this outline. These references are by no means meant to be exhaustive!

Introduction & preliminaries

Optimization models for the basic kidney exchange problem

State of, and challenges in, practical implementation

At this point in the tutorial, the audience will know about the high-level kidney exchange problem, its initial formulation as a theoretically and empirically hard optimization problem, and will have in-depth knowledge of the original techniques and AI/OR methods used to overcome that computational hardness. The presenters have worked extensively with very large kidney exchanges to implement these clearing algorithms in practice. We will cover some of the early challenges to translating AI-style research into practice, such as the following.

We will discuss how these challenges were overcome, with learnings that will hopefully help AI researchers get AI systems fielded in the large in other applications as well.

— Intermission —

Following the intermission, we will deep dive into different dimensions of fielded kidney exchange that are most pertinent to today's and the future's fielded exchanges, currently unsolved, and would benefit immensely from AI research.

Post-match failure

In all fielded kidney exchanges, many algorithmic matches fail to move to transplant. This is not explicitly taken into account in any fielded optimization algorithms, but is an active area of research.


Prioritization of otherwise-marginalized candidates is a contentious topic and ongoing discussion in healthcare and, specifically, kidney exchange. We will cover the following.

Dynamic exchange

Healthcare applications are often dynamic, with patients and other agents arriving and departing over time, and the interactions between the various agents changing over time as well. In kidney exchange, patients and donors arrive over time, and the exchange can choose when, how, and if to match these actors. We will cover general dynamic optimization techniques developed and then applied to kidney exchange, along with theoretical approaches to dynamic kidney exchange and matching. This is an open problem; we will also cover promising research directions in dynamic exchange, with an emphasis on AI approaches to the problem.

Combining human value judgments and optimization to learn to match

We present a holistic method to combine all of the dimensions mentioned above, along with high-level human-provided value judgments, into a unified framework for learning to match in a general dynamic model. The framework takes as input a high-level objective (e.g., "maximize graft survival of transplants over time") decided on by experts, then automatically (i) learns based on data how to make this objective concrete and (ii) learns the "means" to accomplish this goal—a task, in our experience, that humans handle poorly. It uses data from all live kidney transplants in the US since 1987 to learn the quality of each possible match; it then learns the potentials of elements of the current input graph offline (e.g., potentials of pairs based on features such as donor and patient blood types), translates these to weights, and performs a computationally feasible batch matching that incorporates dynamic, failure-aware considerations through the weights.

This method, shown in Figure 1, provides sensitivity analysis for the UNOS exchange. We will discuss challenges in implementation and the disconnect between general optimization methods and a fielded application, and how the given framework attempts to unify the two different viewpoints.

The FutureMatch framework.

Figure 1. The FutureMatch framework.

Game-theoretic analysis

Here, we view the kidney exchange problem as a multi-agent system with transplant centers as agents, and their set of patient-donor pairs (and possibly altrustic donors) as a private type. The issue is that the transplant centers can match easy-to-match pairs locally and only report hard pairs to the exchange because transplant centers gain financially from conducting surgeries locally and local transplants are logistically easier. Such hiding of the pairs from the exchange compromises the global efficiency of the system. Prof. Sandholm in collaboration with UNOS has empirically shown that the problem is rampant: today transplant centers not only hide their easy-to-match pairs but all their internally matchable pairs. We will discuss mechanism design approaches to this problem, such as the following.

Research toward exchanges of other organs and cross-organ exchanges

We will briefly overview nascent theoretical and practical pushes to field new types of organ exchanges—liver exchange, lung exchange, multi-organ exchange—with a focus on the modeling differences between those and kidney exchange.

Conclusion & recap of research directions

We will provide insight into where we think fielded kidney exchanges are—and where they should be—going, and touch on the different directions in this area where AI researchers could make an impact.

Recommended Reading ( bib)

[1] David Abraham, Avrim Blum, and Tuomas Sandholm. Clearing algorithms for barter exchange markets: Enabling nationwide kidney exchanges. In Proceedings of the ACM Conference on Electronic Commerce (EC), pages 295--304, 2007.
[2] Mohammad Akbarpour, Shengwu Li, and Shayan Oveis Gharan. Dynamic matching market design. In Proceedings of the ACM Conference on Economics and Computation (EC), page 355, 2014.
[3] Ross Anderson, Itai Ashlagi, David Gamarnik, and Yash Kanoria. A dynamic model of barter exchange. In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2015.
[4] Ross Anderson, Itai Ashlagi, David Gamarnik, and Alvin E Roth. Finding long chains in kidney exchange using the traveling salesman problem. Proceedings of the National Academy of Sciences, 112(3):663--668, 2015.
[5] Elliot Anshelevich, Meenal Chhabra, Sanmay Das, and Matthew Gerrior. On the social welfare of mechanisms for repeated batch matching. In AAAI Conference on Artificial Intelligence (AAAI), pages 60--66, 2013.
[6] Itai Ashlagi, Felix Fischer, Ian A Kash, and Ariel D Procaccia. Mix and match: A strategyproof mechanism for multi-hospital kidney exchange. Games and Economic Behavior, 91:284--296, 2015.
[7] Itai Ashlagi, Duncan S. Gilchrist, Alvin E. Roth, and Michael Rees. Nonsimultaneous chains and dominos in kidney-paired donation---revisited. American Journal of Transplantation, 11(5):984--994, 2011.
[8] Itai Ashlagi, Patrick Jaillet, and Vahideh H. Manshadi. Kidney exchange in dynamic sparse heterogenous pools. In Proceedings of the ACM Conference on Electronic Commerce (EC), pages 25--26, 2013.
[9] Itai Ashlagi and Alvin E. Roth. New challenges in multihospital kidney exchange. American Economic Review, 102(3):354--59, 2012.
[10] Itai Ashlagi and Alvin E Roth. Free riding and participation in large scale, multi-hospital kidney exchange. Theoretical Economics, 9(3):817--863, 2014.
[11] Pranjal Awasthi and Tuomas Sandholm. Online stochastic optimization in the large: Application to kidney exchange. In Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI), pages 405--411, 2009.
[12] Avrim Blum, John P. Dickerson, Nika Haghtalab, Ariel D. Procaccia, Tuomas Sandholm, and Ankit Sharma. Ignorance is almost bliss: Near-optimal stochastic matching with few queries. In Proceedings of the ACM Conference on Economics and Computation (EC), 2015.
[13] Avrim Blum, Anupam Gupta, Ariel D. Procaccia, and Ankit Sharma. Harnessing the power of two crossmatches. In Proceedings of the ACM Conference on Electronic Commerce (EC), pages 123--140, 2013.
[14] Ioannis Caragiannis, Aris Filos-Ratsikas, and Ariel D. Procaccia. An improved 2-agent kidney exchange mechanism. Theoretical Computer Science, 589:53--60, 2015.
[15] Miguel Constantino, Xenia Klimentova, Ana Viana, and Abdur Rais. New insights on integer-programming models for the kidney exchange problem. European Journal of Operational Research, 231(1):57--68, 2013.
[16] Sanmay Das, John P. Dickerson, Zhuoshu Li, and Tuomas Sandholm. Competing dynamic matching markets. In Proceedings of the Conference on Auctions, Market Mechanisms and Their Applications (AMMA), 2015.
[17] John P. Dickerson, Ariel D. Procaccia, and Tuomas Sandholm. Dynamic matching via weighted myopia with application to kidney exchange. In AAAI Conference on Artificial Intelligence (AAAI), pages 1340--1346, 2012.
[18] John P. Dickerson, Ariel D. Procaccia, and Tuomas Sandholm. Optimizing kidney exchange with transplant chains: Theory and reality. In International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), pages 711--718, 2012.
[19] John P. Dickerson, Ariel D. Procaccia, and Tuomas Sandholm. Failure-aware kidney exchange. In Proceedings of the ACM Conference on Electronic Commerce (EC), pages 323--340, 2013.
[20] John P. Dickerson, Ariel D. Procaccia, and Tuomas Sandholm. Price of fairness in kidney exchange. In International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), pages 1013--1020, 2014.
[21] John P. Dickerson and Tuomas Sandholm. Multi-organ exchange: The whole is greater than the sum of its parts. In AAAI Conference on Artificial Intelligence (AAAI), pages 1412--1418, 2014.
[22] John P. Dickerson and Tuomas Sandholm. FutureMatch: Combining human value judgments and machine learning to match in dynamic environments. In AAAI Conference on Artificial Intelligence (AAAI), 2015.
[23] Yichuan Ding, Dongdong Ge, Simai He, and Christopher Ryan. A non-asymptotic approach to analyzing kidney exchange graphs. In Proceedings of the ACM Conference on Economics and Computation (EC), 2015.
[24] Haluk Ergin, Tayfun Sönmez, and M Utku Ünver. Lung exchange, 2014. Working paper.
[25] Haluk Ergin, Tayfun Sönmez, and M Utku Ünver. Liver exchange, 2015. Working paper.
[26] Kristiaan M. Glorie. Estimating the probability of positive crossmatch after negative virtual crossmatch. Technical report, Erasmus School of Economics, 2012.
[27] Kristiaan M. Glorie, J. Joris van de Klundert, and Albert P. M. Wagelmans. Kidney exchange with long chains: An efficient pricing algorithm for clearing barter exchanges with branch-and-price. Manufacturing & Service Operations Management (MSOM), 16(4):498--512, 2014.
[28] Chen Hajaj, John P. Dickerson, Avinatan Hassidim, Tuomas Sandholm, and David Sarne. Strategy-proof and efficient kidney exchange using a credit mechanism. In AAAI Conference on Artificial Intelligence (AAAI), 2015.
[29] Jian Li, Yicheng Liu, Lingxiao Huang, and Pingzhong Tang. Egalitarian pairwise kidney exchange: Fast algorithms via linear programming and parametric flow. In International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), pages 445--452, 2014.
[30] Yijiang Li, Jack Kalbfleisch, Peter Xuekun Song, Yan Zhou, Alan Leichtman, and Michael Rees. Optimization and simulation of an evolving kidney paired donation (KPD) program. Department of biostatistics working paper 90, University of Michigan, May 2011.
[31] Yicheng Liu, Pingzhong Tang, and Wenyi Fang. Internally stable matchings and exchanges. In AAAI Conference on Artificial Intelligence (AAAI), pages 1433--1439, 2014.
[32] Suiqian Luo and Pingzhong Tang. Mechanism design and implementation for lung exchange. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 2015.
[33] David Manlove and Gregg O'Malley. Paired and altruistic kidney donation in the UK: Algorithms and experimentation. ACM Journal of Experimental Algorithmics, 19(1), 2014.
[34] Robert Montgomery, Sommer Gentry, William H Marks, Daniel S Warren, Janet Hiller, Julie Houp, Andrea A Zachary, J Keith Melancon, Warren R Maley, Hamid Rabb, Christopher Simpkins, and Dorry L Segev. Domino paired kidney donation: a strategy to make best use of live non-directed donation. The Lancet, 368(9533):419--421, 2006.
[35] Benjamin Plaut, John P. Dickerson, and Tuomas Sandholm. A fast and optimal clearing engine for barter exchanges with capped chains, 2015. Working paper.
[36] F. T. Rapaport. The case for a living emotionally related international kidney donor exchange registry. Transplantation Proceedings, 18:5--9, 1986.
[37] Michael Rees, Jonathan Kopke, Ronald Pelletier, Dorry Segev, Matthew Rutter, Alfredo Fabrega, Jeffrey Rogers, Oleh Pankewycz, Janet Hiller, Alvin Roth, Tuomas Sandholm, Utku Ünver, and Robert Montgomery. A nonsimultaneous, extended, altruistic-donor chain. New England Journal of Medicine, 360(11):1096--1101, 2009.
[38] Alvin Roth, Tayfun Sönmez, and Utku Ünver. Kidney exchange. Quarterly Journal of Economics, 119(2):457--488, 2004.
[39] Alvin Roth, Tayfun Sönmez, and Utku Ünver. A kidney exchange clearinghouse in New England. American Economic Review, 95(2):376--380, 2005.
[40] Alvin Roth, Tayfun Sönmez, and Utku Ünver. Pairwise kidney exchange. Journal of Economic Theory, 125(2):151--188, 2005.
[41] Alvin Roth, Tayfun Sönmez, and Utku Ünver. Efficient kidney exchange: Coincidence of wants in a market with compatibility-based preferences. American Economic Review, 97:828--851, 2007.
[42] Alvin Roth, Tayfun Sönmez, Utku Ünver, Frank Delmonico, and Susan L. Saidman. Utilizing list exchange and nondirected donation through `chain' paired kidney donations. American Journal of Transplantation, 6:2694--2705, 2006.
[43] Tayfun Sönmez and Utku Ünver. Altruistically unbalanced kidney exchange. Journal of Economic Theory, 152(1):105--129, 2014.
[44] Darren Stewart, Ruthanne Leishman, Elizabeth Sleeman, Catherine Monstello, Guy Lunsford, Jude Maghirang, Tuomas Sandholm, Sommer Gentry, Richard Formica, John Friedewald, and Kenneth Andreoni. Tuning the OPTN's KPD optimization algorithm to incentivize centers to enter their easy-to-match pairs. In American Transplant Congress (ATC), 2013. Talk abstract.
[45] Panos Toulis and David C. Parkes. Design and analysis of multi-hospital kidney exchange mechanisms using random graphs. Games and Economic Behavior, 91(0):360--382, 2015.
[46] Utku Ünver. Dynamic kidney exchange. Review of Economic Studies, 77(1):372--414, 2010.
[47] Özgür Yilmaz. Kidney exchange: An egalitarian mechanism. Journal of Economic Theory, 146(2):592--618, 2011.
[48] S. A. Zenios. Optimal control of a paired-kidney exchange program. Management Science, 48(3):328--342, 2002.