Altruistically Unbalanced Kidney Exchange

Abstract

Although a pilot national live-donor kidney exchange program was recently launched in the US, the kidney shortage is increasing faster than ever. A new solution paradigm is able to incorporate compatible pairs in exchange. In this paper, we consider an exchange framework that has both compatible and in- compatible pairs, and patients are indifferent over compatible pairs. Only two-way exchanges are permitted due to institutional constraints. We explore the structure of Pareto-efficient matchings in this framework. The mathematical structure of this model turns out to be quite novel. We show that under Pareto-efficient matchings, the same number of patients receive transplants, and it is possible to construct Pareto-efficient matchings that match the same incompatible pairs while matching the least number of compatible pairs. We extend the celebrated Gallai-Edmonds Decomposition in the combinatorial optimization literature to our new framework. We also conduct comparative static exercises on how this decomposition changes as new compatible pairs join the pool.