Unpaired Kidney Exchange: Overcoming Double Coincidence of Wants without Money
For an incompatible patient-donor pair, kidney exchanges often forbid receipt-before-donation (the patient receives a kidney before the donor donates) and donation-before-receipt, causing a double-coincidence-of-wants problem. Our proposed algorithm, the Unpaired kidney exchange algorithm, uses “memory” as a medium of exchange to eliminate these timing constraints. In a dynamic matching model, we prove that Unpaired delivers a waiting time of patients close to optimal and substantially shorter than currently utilized state-of-the-art algorithms. Using a rich administrative dataset from France, we show that Unpaired achieves a match rate of 57 percent and an average waiting time of 440 days. The (infeasible) optimal algorithm is only slightly better (58 percent and 425 days); state-of-the-art algorithms deliver less than 34 percent and more than 695 days. We draw similar conclusions from the simulations of two large U.S. platforms. Lastly, we propose a range of solutions that can address the potential practical concerns of Unpaired.
We thank Nikhil Agarwal, Nick Arnosti, Itai Ashlagi, Eric Budish, Paul Milgrom, Michael Ostrovsky, Parag Pathak, Alvin Roth, Paulo Somaini, Tayfun Sonmez, Utku Unver and several seminar participants for valuable comments. Combe is grateful for the support from the ERC Grant No. 682417, Frontiers in Design - Frontiers in Mechanism Design: Methodology and Applications. Hiller is grateful for the support from ANR grant PAIRED_KIDNEY_DONATION (ANR-17-CE36-0004-01) and Labex MME-DII (ANR11-LBX-0023-01). All errors remain our own. The views expressed herein are those of the authors and do not necessarily reflect the views of the National Bureau of Economic Research.