Abstract
Living donors are often incompatible with their intended recipients. Kidney paired donation matches one patient and his or her incompatible donor with another pair in the same situation for an exchange. Let patient-donor pairs be the vertices of an undirected graph G, with edges connecting reciprocally compatible vertices. A matching in G is a feasible set of paired donations. Because the lifespan of a transplant depends on the immunologic concordance of donor and recipient, we weight the edges of G and seek a maximum edge-weight matching. Unfortunately, such matchings might not have the maximum cardinality; there is a risk of an unpredictable trade-off between quality and quantity of paired donations. We prove that the number of paired donations is within a multiplicative factor of the maximum possible donations, where the factor depends on the edge weighting. We propose an edge weighting of G which guarantees that every matching with maximum weight also has maximum cardinality, and also maximizes the number of transplants for an exceptional subset of recipients, while favoring immunologic concordance. We partially generalize this result to k-way exchange and chains, and we implement our weightings using a real patient dataset from Brazil.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 100246 |
| Journal | Operations Research for Health Care |
| Volume | 25 |
| DOIs | |
| State | Published - Mar 9 2020 |
Bibliographical note
KAUST Repository Item: Exported on 2020-10-01Acknowledgements: Sommer Gentry was supported by the Naval Academy Research Council. Michal Mankowski was supported by King Abdullah University of Science and Technology (KAUST) . The authors thank Dorry Segev for clinical insights on paired donation and Juliana Bastos for sharing anonymized data from a large Brazilian transplant center. Sommer Gentry thanks Fuhito Kojima for a helpful conversation about incentives in paired donation and Charles Mylander for a thoughtful review of the manuscript. We have been pleased to work with Ken Andreoni, M.D. and the United Network for Organ Sharing's kidney–pancreas committee on formulating clinically relevant optimization models for kidney paired donation. We acknowledge the editors and reviewers for their valuable suggestions.