Dynamic Kidney Exc hange∗M. Utku Ün v er†Boston Colle geFirst Draft: Marc h 2007Final Draft: March 2009AbstractWe study how b arter exchanges should be conducted through a centralized mechanism ina dynamically evolving agent pool with time- and compatibility-based preferences. We derivethe dynamically efficient two-way and multi-way exchange mechanisms that maximize totaldiscounted exch ange surplus. Recently several live-donor kidney exchange programs were es-tablished to sw ap incompatible donors of end-stage kidney disease patien ts. Since kidney ex-change can be modeled as a special instance of our more general model, dynamically efficientkidney exc hange mechanisms are derived as corollaries. We make policy recommendations usingsimulations.Keywords: Dynamic exchange, kidney exchange, matching, market design, dynamic opti-mization, Markov process.JEL Classification Numbers: C78, C70, D78, C61∗I would like to thank especially Tayfun Sönmez, and also David Abraham, Murat Fadılo˘glu, Fikri Karaesmen,David Kaufman, Onur Kesten, Fuhito Kojima, Alvin E. Roth, Andrew Sc h aefer,˙Insan Tunalı,andNe¸se Yıldız, par-ticipan ts at SAET Conference at Kos, Matc hing Workshops at Barcelona and Caltech, seminars at British Columbia,Boston College, Carnegie Mellon, Koç, and Bilkent for comments and suggestions. I w ould also like to thank theeditor, an associate editor, and anon ymous referees of the journal for their excellent comments. I am grateful to NSFfor financial support.†Address: Department of Economics, Boston College, 140 Commonwealth Ave., Chestnut Hill, MA 02467, USA;e-mail address: utku.unv [email protected]; url: http://www2.bc.edu/~unver.11 IntroductionThere are about 79000 patients waiting for a kidney transplan t in the United States as of March2009. In 2008, about only 16500 transplants w er e conducted , about 10500 from deceased donorsand 6000 from living donors, while about 32500 new patien ts joined the deceased donor waiting listand 4200 patien ts died while waiting for a kidney.1Although there is a substan tial organ shortage,buying and selling an organ is illegal in many coun tries in the w orld , mak ing donation the onlysource for kidney transplan ts. Especially in the last decade, the increase in the number of kidneytransplants came from the utilization of liv e donors, who are typically relativ es, friends, or spouses ofthe patients and are willing to donate one of their kidneys. Ho wever, many living donors still cannotbe utilized, since the potential donor ma y not be able to donate to her lo ved one due to blood-ty peincom p atibility or tissue rejection. The medical community has proposed innovativ e w ays to utilizethese living donors through live-donor kidney exchanges (Rapaport, 1986). In a live-d onor kidneyexchange, recipients with incompatible donors sw ap their donor s if there is cross-compatib ility. Since1991, kidney exc hanges have been done mostly in an ad-hoc manner in different countries aroundthe w orld . Live-donor kidney exch ang es accounted for at least 10% of all live donor transplants inKorea and the Netherlands in, 2004 (see Park et al., 2004 and de Klerk et al., 2005). The medicalcommunit y has endorsed the practice of live-dono r kidney exchan ges as ethical (Abecassis et al.,2000). Unlik e Korea and Netherland s, in the United States there is no national system to overseekidney exchanges as of 2009. Differ ent transplant centers around the country have recently startedkidney exchange programs. For example, New England Program for Kidney Exchange (NEPK E) isan initiative of the transplan t centers in New Englan d together with economists (see Roth, Sönmez,and Ün ver 2005b), and Alliance for Paired Donation (APD ) is an initiative of Dr. Michael Reesat Univ ersity of Toledo and the authors of the above studies. APD has already convinced a largen u mber of transplant cen ters all around the US to participate. United Network for Organ Sharing isat the stage of launching the national kidney exc hange program in the US.2In man y of these programs, a major objective has been to conduct as man y transplan ts as possible.How ever, one question has frequen tly arisen in the implem entation stage: How often and how exactlyshould the excha nge be run ? Roth, Sön mez, and Ün ver (2004, 2005a) have recen tly proposedmechanisms to organize kidney exchanges in a P a reto-efficient and dominant strategy incentive-com patible fashion under different constraints on exchan ge sizes and preferences of the recipien ts fora static recipient population .1AccordingtoSRTR/OPTNnationaldataretrievedathttp://www.optn.org on 3/17/2009.2In Europe, other than the Netherlands, paired kidney exchange programs have not yet been well organized. TheUK has only recently passed a law that makes kidney exc hanges legal. France and Germany have stricter laws, and itis illegal to have a transplant from an unrelated and emotionally distant live-donor, making paired exchanges illegal.Spain has an excellent deceased donor program. Therefore, live donation is seen as of secondary importance, althoughthere is overwhelming evidence that the long-run survival rates of live donor organs are far better than deceased-donororgans.2The above studies address the matc hing aspect of the problem. Ho wev er, they do not consider thedynamic aspects of the exchange pool evolution.3From a more general perspectiv e, in the matchingliterature in economics, although there is significan t amount of wor k on mechanism design in staticen vironmen ts, there is virtually no study on mec hanism design for dynamically c hanging popula-tions, two recent exceptions withstand ing.4A recent paper b y Bloc h and Cantala (2009) analyzeshouse allocation problems in an ov erlapping generations framework. In their model, they analyzeassignment mec hanisms that are fair, efficient, and independen t. Seniorit y-based assignmen t rulesc h aracterize these properties when agen ts are homogeneo us. How ever, when the ty pes of agentsare random, efficien t, and fair rules only exist with two agent types. Independence and efficiencyare incomp atib le in this case. Unlike our model, objects are not attac h ed to agents in their model.Hence, they study assignment rather than exc h an ge. In their model, objects remain in the problemafter agen ts leave the problem. Thus, assignment of an object is not final. Moreover, their generalpreference structure is not compatib ility-based, although they