Spring 2013 Seminar Series

DATE:10/3/2013
LOCATION: E51-315
TIME: 4:15pm
Reception immediately following

SPEAKER:
Ross Anderson

TITLE
A Dynamic Model of Kidney Exchange Programs

ABSTRACT
Kidney exchange programs enable patients with living but incompatible donors to exchange kidneys in 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, exchange programs perform this optimization periodically; however, the long run implications of this policy for average patient waiting time are not well understood.

 

To address this issue, we propose a dynamic random graph model of a kidney exchange program. In each time period, a single node (a donor-patient pair) arrives, and for each pre-existing node in the graph, directed edges (feasible transplants) are added to and from the new node with probability p, i.i.d. We consider two policies for deleting nodes (selecting transplants): either we remove short cycles, or we maintain and advance a single chain. In both cases, we show that the "greedy policy," where we maximize the number of transplants in every time period, results in a long run average patient waiting time that is as good as any batching policy, up to constant factors as p → 0. Additionally, we find that as p → 0, the steady state average patient waiting time using the chains policy is an order of magnitude smaller in p than under the cycles policy, which explains why modern kidney exchanges in the U.S. tend to do most transplants through chains.