DB Seminar [Fall 2014]: John Dickerson

Abstract:

The preferred treatment for kidney failure is a transplant; however, demand for donor kidneys far outstrips supply.  Kidney exchange, an innovation where willing but incompatible patient-donor pairs can exchange organs—via barter cycles and altruist-initiated chains—provides a life-saving alternative.  Typically, fielded exchanges act myopically, considering only the current pool of pairs when planning the cycles and chains.  Yet kidney exchange is inherently dynamic, with participants arriving and departing.  Also, many planned exchange transplants do not go to surgery due to various failures. So, it is important to consider the future when matching.

Motivated by our experience running the computational side of a large nationwide kidney exchange, we present FutureMatch, a framework for learning to match in a general dynamic model.  FutureMatch 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.

We validate FutureMatch on real fielded exchange data.  It results in higher values of the objective.  Furthermore, even under economically inefficient objectives that enforce equity, it yields better solutions for the efficient objective (which does not incorporate equity) than traditional myopic matching that uses the efficiency objective.