More on random graph models of kidney exchange

A new paper by Panos Toulis and David Parkes explores random graph models of kidney exchange: A Random Graph Model of Kidney Exchanges: Efficiency, Individual-Rationality and Incentives

Abstract:
"In kidney exchanges, hospitals share patient lists and receive transplantations. A kidney-paired donation (KPD) mechanism needs to promote full sharing of information
about donor-patient pairs, and identify a Pareto efficient outcome that also satisfies participation constraints of hospitals. Random graph theory is applied to the kidney exchange problem to provide a two-fold benefit: early experimental results can be explained analytically, and complex models with participation of multiple hospitals can be studied in terms of incentives in a methodological way. In this paper, we introduce a random graph model of the KPD exchange and then fully characterize the structure of the efficient outcome and the expected number of transplantations that can be performed. We derive a square-root law between the welfare gains from sharing patient-donor pairs in a central pool and the individual sizes of hospitals, which also illustrates the urgent need for the nationwide expansion  of such programs. Finally, we establish through theoretical and computational analysis that enforcing simple individual rationality constraints on the outcome can mitigate the negative impact of strategic behavior by hospitals."

While they consider only two-way exchange, their results parallel those obtained in the random graph model that Itai Ashlagi and I wrote about in Ashlagi, Itai and Alvin E. Roth, "Individual rationality and participation in large scale, multi-hospital kidney exchange," working paper, January 2011.

One of the developments it has been exciting to witness is the increasingly interdisciplinary work on kidney exchange, which now involves surgeons, economists, operations researchers and computer scientists. Here at Harvard, a lot of the connection to computer science comes through David Parkes, Yileng Chen, and the EconCS group.

I enjoyed speaking at the interdisciplinary seminar run by the Center for Research on Computation and Society (CRCS, pronounced "circus"). You can see my talk on the CRCS video site, ordered by dates, Monday, September 20, 2010: Alvin Roth on Kidney Exchange. From about 27 minutes to 13 minutes from the end (if you get that far, it's an 85 minute video:), you can hear me start to talk about some of the issues explored in these two papers.