Incorporating compatible pairs in kidney exchange: A dynamic weighted matching model

Zhuoshu Li, Kelsey Lieberman, William Macke, Sofia Carrillo, Chien Ju Ho, Jason Wellen, Sanmay Das

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

Kidney exchange has been studied extensively from the perspective of market design, and a significant focus has been on better algorithms for finding chains and cycles to increase the number of possible matches. A more dramatic benefit could come from incorporating compatible pairs into the mechanism, but this possibility has been relatively understudied. In order to incentivize a compatible pair to participate in exchange, they must be offered a higher quality match for the recipient that can be performed without adding extra waiting time. In this paper, we make two main contributions to the study of incorporating compatible pairs in exchanges. First, we leverage the recently proposed Living Donor Kidney Profile Index (LKDPI) to measure match quality, and develop a novel simulator (based on data from a major transplant center) for the joint distribution of compatibility and quality across pairs. This simulator allows us to study the benefits of including compatible pairs under different models and assumptions. Second, we introduce a hybrid online/batch matching model with impatient (compatible) and patient (incompatible) pairs to capture the need for immediacy. We introduce new algorithms for matching in this model, including one based on online primal-dual techniques. Overall, our results indicate great potential in terms of both increased numbers of transplants of incompatible pairs (almost doubling the number transplanted) as well as improved match quality for recipients in compatible pairs (increasing expected graft survival by between 1 and 2 years). The results are also promising for hard-to-match subpopulations, including blood group O recipients.

Original languageEnglish
Title of host publicationACM EC 2019 - Proceedings of the 2019 ACM Conference on Economics and Computation
PublisherAssociation for Computing Machinery, Inc
Pages349-367
Number of pages19
ISBN (Electronic)9781450367929
DOIs
StatePublished - Jun 17 2019
Event20th ACM Conference on Economics and Computation, EC 2019 - Phoenix, United States
Duration: Jun 24 2019Jun 28 2019

Publication series

NameACM EC 2019 - Proceedings of the 2019 ACM Conference on Economics and Computation

Conference

Conference20th ACM Conference on Economics and Computation, EC 2019
CountryUnited States
CityPhoenix
Period06/24/1906/28/19

Keywords

  • Cardinal utility
  • Kidney exchange
  • Matching
  • Online primal-dual methods

Fingerprint Dive into the research topics of 'Incorporating compatible pairs in kidney exchange: A dynamic weighted matching model'. Together they form a unique fingerprint.

  • Cite this

    Li, Z., Lieberman, K., Macke, W., Carrillo, S., Ho, C. J., Wellen, J., & Das, S. (2019). Incorporating compatible pairs in kidney exchange: A dynamic weighted matching model. In ACM EC 2019 - Proceedings of the 2019 ACM Conference on Economics and Computation (pp. 349-367). (ACM EC 2019 - Proceedings of the 2019 ACM Conference on Economics and Computation). Association for Computing Machinery, Inc. https://doi.org/10.1145/3328526.3329619