Modern Organ Exchanges:Generalized Matching under Dynamics, Edge Failures, and Fairness

In kidney exchanges, patients with kidney disease can obtain compatible donors by swapping their own willing but incompatible donors. The vanilla clearing problem involves finding an optimal set of non-overlapping short cycles. We proved this is NP-hard. We developed an algorithm capable of clearing optimally on a nationwide scale. The key was incremental problem formulation because the formulation that gives tight LP bounds is too large to even store. On top of the branch-and-price paradigm we developed techniques that dramatically improve runtime and memory usage. 

 Our algorithms autonomously make the transplant plan twice a week for the United Network for Organ Sharing national kidney exchange that has 143 transplant centers. Our algorithms have also been used by two private exchanges. We introduced several design enhancements to kidney exchange. For one, we used our algorithms to launch the first never-ending altruist-donor-initiated barter chains. I will discuss the role of long chains. 

 Furthermore, clearing is actually a dynamic problem where patient-donor pairs and altruistic donors appear and expire over time. We first developed trajectory-based online stochastic optimization algorithms for this. Recently we developed a general approach for giving batch algorithms guidance about the future without a run-time hit. It learns potentials of elements of the problem, and then uses them in each batch clearing. Then, I will present an algorithm that finds the highest expected value plan in the face of pre-transplant failures such as last-minute incompatibilities. I will present new computational approaches for dynamic compatibility testing. I will also discuss the fairness-efficiency tradeoff. Finally, I will describe the FUTUREMATCH framework that combines all these elements and uses data to learn a concrete objective from high-level human value judgments.

 We show that similar approaches could be used to set up an exchange for liver lobes, or cross-organ exchanges. (Different parts of this work are joint with dozens of different collaborators, as detailed in the presentation.)