How Should we Value a Prearranged Paired Kidney Exchange? A Stochastic Game Approach

Time, Date, Venue

4 March 2011, Friday 15.00-16.15

University College London

1st floor Exec-ed room, Engineering Front Building
("Malet place" in Google maps)


End-stage renal disease (ESRD) is the ninth-leading cause of death in the U.S. Transplantation is the most viable therapy for ESRD patients, but there is a severe disparity between the demand for kidneys for transplantation and the supply. This shortage is further complicated by incompatibilities in blood-type and antigen matching between patient-donor pairs. Paired kidney exchange (PKE), a cross-exchange of kidneys among incompatible patient-donor pairs, overcomes many difficulties in matching patients with incompatible donors. PKEs have grown rapidly over the last two decades.

The question of how to form PKEs among compatible patient/donor pairs has been formulated as a maximum cardinality matching, so that every potential match has the same value. We seek a more accurate method of valuing a prospective exchange by relaxing two assumptions. First, we allow patient health to progress. Second, we allow patients autonomy to choose when they are willing to undergo the exchange. The resulting model is an infinite-horizon non-zero-sum stochastic game. We explore necessary and sufficient conditions for patients' decisions to be a Nash equilibrium, and formulate a mixed-integer linear programming representation of equilibrium constraints, which provides a characterization of the socially optimal equilibria. We empirically confirm that randomized strategies do not yield a social welfare gain over pure strategies. We also quantify the social welfare loss due to patient autonomy and demonstrate that maximizing the number of transplants may be undesirable. Our results highlight the importance of the timing of an exchange and disease severity on matching patient-donor pairs.


Andrew Schaefer is an Associate Professor of Industrial Engineering and Wellington C. Carl Fellow at the University of Pittsburgh. He holds secondary appointments in the departments of medicine and bioengineering. He received his PhD in Industrial and Systems Engineering from Georgia Tech in 2000. His primary research interest is the application of stochastic optimization techniques to disease treatment problems. He has active research interests in the contexts of end-stage liver disease, sepsis, HIV, diabetes, flu shot design and kidney exchanges. His methodological interests include stochastic programming, mixed-integer programming, and Markov decision processes.