A Random Graph Model of Kidney Exchanges: Efficiency, Individual-Rationality and

[Clark]

http://www.people.fas.harvard.edu/~ptoulis/papers/ec11-ptoulis-parkes.pdf

A Random Graph Model of Kidney Exchanges: Efficiency, Individual-Rationality and Incentives
Panos Toulis and David Parkes

ABSTRACT
In kidney exchanges, hospitals share patient lists and re-
ceive transplantations. A kidney-paired donation (KPD)
mechanism needs to promote full sharing of information
about donor-patient pairs, and identify a Pareto ecient
outcome that also satises participation constraints of hos-
pitals. Random graph theory is applied to the kidney ex-
change problem to provide a two-fold benet: early exper-
imental results can be explained analytically, and complex
models with participation of multiple hospitals can be stud-
ied 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
ecient outcome and the expected number of transplanta-
tions 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 individ-
ual rationality constraints on the outcome can mitigate the
negative impact of strategic behavior by hospitals.