Opting in for an individually rational kidney exchange
May 4, 2016
Kidney transplant is sometimes the best treatment for people who suffer from chronic kidney disease. However, due to medical incompatibility issues, a direct kidney transplant is not always possible even for those patients that are fortunate enough to have a willing donor. This is where Kidney Exchange comes in: It enables two or more donor-patient pairs to swap donors, so that each patient receives a compatible kidney. In recent years, hospitals have enrolled patients into regional or even national kidney exchange programs.
However, hospitals often only enroll their hard-to-match donor-patients pairs and withhold donor and patients that can be matched internally. While this behavior increases the number of matched patients for some hospitals, it significantly reduces the social welfare -- the total number of patients that receive a kidney transplant. Therefore, it is important to design a mechanism that incentivizes the hospitals to participate fully, while achieving a near optimal social welfare.
In this work, we introduce such a mechanism. By design, our mechanism allows hospitals to opt-in and enroll all their patients, or opt-out and only match their patients internally. Our mechanism finds a matching within O(\sqrt{OPT}) of the optimal social welfare and guarantees individual rationality -- that by opting in each hospital receives as many matches as it could have achieved alone. Furthermore, our mechanism is optimal, in the sense that no individually rational mechanism achieves a better approximation factor.
Based on joint work with Avrim Blum, Ioannis Caragiannis, Ariel Procaccia, Eviatar Procaccia, and Rohit Vaish.
BIO:
Nika Haghtalab is a Ph.D. student at the Computer Science department of Carnegie Mellon University co-advised by Avrim Blum and Ariel Procaccia. Her research interests are in learning theory, computational game theory, and algorithms. Nika is a recipient of IBM and Microsoft Research Ph.D. fellowships.