Joint Theory Lunch Seminar / Computer Science Speaking Skills Talk

Wednesday, May 4, 2016 - 12:00pm to 1:00pm


ASA Conference Room 6115 Gates & Hillman Centers



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(√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. — 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. Presented in Partial Fulfillment of the CSD Speaking Skills Requirement.

Event Website:

For More Information, Contact:


Speaking Skills