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 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 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

• Kidney disease and the state of organ transplantation in the US and abroad; medical and legal constraints in organ transplantation
• Genesis of the kidney exchange idea from a medical point of view
• Economics & matching research on large-scale kidney exchange
• Modern generalizations such as altruist-initiated chains—as opposed to traditional kidney exchange where only cycles were used. We will cover both closed and open chains. Nowadays most kidney exchange transplants are conducted using open chains (i.e., never-ending altruist-initiated chains), which Prof. Sandholm helped invent.

Optimization models for the basic kidney exchange problem

• Two basic formulations of the kidney exchange clearing problem as an integer programming search problem
• Tightness of different formulations
• Complexity and runtime tradeoffs in more expressive models (e.g., traditional matching versus more complex matching with cycles and chains, different utility functions)
• A custom branch-and-price-based integer programming solver built to clear large kidney exchange pools (of the type that existed in the nascency of kidney exchange)
• Two recent integer program-based formulations built to handle long chains in kidney exchange, an adaptation to the original branch-and-price-based solver, and runtime comparisons between the three approaches

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.

• Convincing practitioners that "hardcore" optimization is necessary, when compared to more understandable (to a layperson) heuristic methods
• Feedback loop between healthcare professionals and CS/Econ researchers
• Legality and ethics, especially with respect to moving beyond simple kidney swaps to more elaborate constructs like non-directed donor-initiated kidney chains
• Other challenges

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.

• Reasons for post-match failure in kidney exchange, and learning failure rates from data
• Approaches for incorporating failure rates into the optimization problem
• Tractability versus expressiveness in stochastic optimization formulations

Fairness

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

• How should we define fairness in general
• Two different ways to define fairness in an optimization model, and theoretical bounds on the "price of fairness" relative to an efficient matching in these models
• Open questions in balancing equity and efficiency in healthcare applications

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.

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.

• Mechanism design impossibility results in a dense model
• Better mechanisms for a reduced model of kidney exchange
• Ongoing ideas and techniques to circumvent the impossibility results

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.

• Failure-aware, fairness-aware, dynamic kidney exchange models, and the optimization techniques to solve real-world instances of the kidney exchange problem, as discussed above
• Mechanism design aspects of kidney exchange and their effect on fielded exchange performance
• Aspects of the kidney exchange model that have not been touched by the optimization literature—mainly, money and the difficulties of international exchange
• Difficulties in fielding an AI application in healthcare, and ways this could be streamlined in the future

Recommended Reading ( bib)