Efficient Kidney Exchange with Dichotomous Preferences

This paper considers a general and practical kidney exchange model with compatible or incompatible patient-donor pairs, single donors, and patients on the waiting list. Efficient exchange procedures are proposed with dichotomous preferences in which only one-way, two-way, three, or four-way chains or cycles of exchange are used. We derive a tight upper bound of the possible number of feasible kidney transplants in each case of exchange and provide substantial simulation results. We find that two-way cycles and chains of exchange can substantially increase the number of feasible transplants, threeway can have a visible effect, and at most four-way cycles and chains suffice to capture all potential gains of exchange. Our results are not only theoretically interesting but also have meaningful policy implications.