The Need for (Long) Chains in Kidney Exchange

by Itai Ashlagi, David Gamarnik, Michael A. Rees & Alvin E. Roth

Overview — It is illegal in the U.S. and in most of the world to buy or sell organs for transplantation. Kidney exchange arises because a healthy person has two kidneys and can donate one to a person in need of a transplant. But a donor and his or her intended recipient may be incompatible. An incompatible patient-donor pair can exchange with another pair, or with more than one other pair, in a cycle of exchanges among patient-donor pairs that allows each patient to receive a kidney from a compatible donor. In addition, sometimes exchange can be initiated by an altruistic donor who does not designate a particular intended patient, and in that case a chain of exchanges need not form a closed cycle. This paper seeks to understand why such longer chains have become increasingly important in practical kidney exchange. The answer has to do with the growing percentage of patients for whom finding a compatible donor is difficult. These "highly sensitized" patients are those for whom finding a transplantable kidney is difficult, even from a donor with the same blood type, because of tissue-type incompatibilities. This paper shows that highly sensitized patients are the ones to benefit from longer cycles and chains, and that this does not harm low-sensitized patients. Key concepts include:

As long as there is such a high percentage of highly sensitized patients, long chains will help by increasing the number of these patients who can receive transplants, and each altruistic donor can have a big effect.

Author Abstract

It has been previously shown that for sufficiently large pools of patient-donor pairs, (almost) efficient kidney exchange can be achieved by using at most 3-way cycles, i.e., by using cycles among no more than 3 patient-donor pairs. However, as kidney exchange has grown in practice, cycles among n>3 pairs have proved useful, and long chains initiated by non-directed, altruistic donors have proven to be very effective. We explore why this is the case, both empirically and theoretically. We provide an analytical model of exchange when there are many highly sensitized patients and show that large cycles of exchange or long chains can significantly increase efficiency when the opportunities for exchange are sparse. As very large cycles of exchange cannot be used in practice, long non-simultaneous chains initiated by non-directed donors significantly increase efficiency in patient pools of the size and composition that presently exist. Most importantly, long chains benefit highly sensitized patients without harming low-sensitized patients.