A Dynamic Model and Optimization of Kidney Exchange Programs


David Gamarnik
Massachusetts Institute of Technology

Wednesday, April 29th, 2015
4:00 - 5:00 PM
GSB P107


Abstract:

Kidney exchange programs enable patients with living but incompatible donors to exchange kidneys by constructing chains initiated by altruistic donors and short cycles. The problem of maximizing the number of transplants in a fixed pool of patients has been well studied. In practice, however, exchange programs solve this optimization periodically, and the long run implications of the matching choices for patient waiting time are not well understood. To address this question, we propose a dynamic random graph model of a kidney exchange program. For this model we show that the "greedy policy" which maximizes the number of transplants in every time period results in a long run average patient waiting time that is asymptotically as good as any other policy. Furthermore, we establish asymptotically that the average patient waiting time is order of magnitude smaller when the exchanges are conducted by advancing chains as opposed to when they are conducted using cycles only. This explains why at the present time kidney exchanges programs tend to rely mostly on chain type transplants. Finally, we will discuss algorithms for finding the largest number of exchanges in kidney exchange programs, which are implemented in several places and countries. This is joint work with Ross Anderson, Itai Ashlagi, Yashodan Kanoria, and Alvin Roth.




Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html