Strategyproofness in Kidney Exchange with Cancellations

Patients requiring kidney transplant may have proxy donors: people who want to donate a kidney to the patient, but cannot due to medical incompatibility. However, patients can swap proxy donors, so that each swapping patient ends up with a compatible donor. Some patients, called overloaded, have multiple proxy donors. A matching is a collection of planned transplants resulting from swaps: we consider both balanced matchings, which restrict overloaded patients to swapping just one of their proxy donors, and unbalanced matchings which do not. In practice, many planned transplants get canceled, and so we want matchings to maximize the expected number of actually executed transplants. Maximization of executed transplants introduces perverse incentives for overloaded patients, who can increase the probability they receive a kidney by hiding some of their proxy donors. We design the SuperGreedy Algorithm, which provably incentivizes patients to fully reveal their proxy donors. When cancellation probabilities are uniformly constant, we prove that SuperGreedy $O(1)$-approximates the maximum number of executed transplans; we also implement SuperGreedy and show via simulation that it performs well on realistic data