Skip to main content

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

Andrew J. Schaefer, Noah Harding Chair and Professor of Computational & Applied Math, Rice University

End-stage renal disease (ESRD) is the ninth-leading cause of death in the U.S. Transplantation is the preferred therapy for ESRD patients, but there is a severe shortage of kidneys for transplantation. This shortage is exacerbated by incompatibilities in blood type and antigen matching among 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 previously 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 with an arbitrary number of patients. First, we propose that the value of an exchange be the total quality-adjusted survival of the patients. Second, we consider the stochastic evolution of end-stage renal disease. Finally, we introduce patient autonomy by allowing patients to choose when they are willing to undergo the exchange. As all transplantations occur simultaneously, the resulting model is an infinite-horizon non-zero-sum stochastic game. We show that a pure stationary equilibrium always exists for this game. We provide necessary and sufficient conditions for patients' decisions to be a stationary Nash equilibrium via a set of mixed-integer inequalities. This characterization permits equilibrium selection through a mixed-integer program. We then refine our model to consider only pure equilibria. Our numerical study, based on 2500 hypothetical PKEs, confirms that randomized strategies do not yield a social welfare gain over pure strategies. It quantifies the social welfare loss due to patient autonomy and demonstrates that maximizing the number of transplants may be undesirable. Our results highlight the importance of disease severity and the timing of an exchange and in evaluating potential PKEs.

This is joint work with Murat Kurt of the University of Buffalo, Utku Ünver of Boston College, and Mark Roberts of the University of Pittsburgh.