Unpaired Kidney Exchange: Overcoming Double Coincidence of Wants without Money

We propose a new matching algorithm -- Unpaired kidney exchange -- to tackle the problem of double coincidence of wants without using money. The fundamental idea is that "memory" can serve as a medium of exchange. In a dynamic matching model with heterogeneous agents, we prove that average waiting time under the Unpaired algorithm is close to optimal, substantially less than the standard pairwise and chain exchange algorithms. We evaluate this algorithm using a rich dataset of kidney patients in France. Counterfactual simulations show that the Unpaired algorithm can match 57% of the patients, with an average waiting time of 440 days (state-of-the-art algorithms match about 34% with an average waiting time of 695 days). The optimal algorithm, which is practically infeasible, performs only slightly better: it matches 58% of the patients and leads to an average waiting time of 426 days. The Unpaired algorithm confronts two incentive-related practical challenges. We address those challenges via a modified version of the Unpaired algorithm that employs kidneys from the deceased donors waiting list. It can match 86% of the patients, while reducing the average waiting time to about 155 days.