Paired and Altruistic Kidney Donation in the UK: Algorithms and Experimentation

The first 4-way liver paired exchange from an interdisciplinary collaboration between health care professionals and design economists

We report initial results of a liver paired exchange (LPE) program established at the Liver Transplant Institute at Inonu University through collaboration with design economists. Since June 2022, the program has been using a matching procedure that maximizes the number of living donor liver transplants (LDLTs) to the patients in the pool subject to the ethical framework and the logistical constraints of the program. In 1 4-way and 4 2-way exchanges, 12 LDLTs have been performed via LPE in 2022. The 4-way exchange, generated in the same match run with a 2-way exchange, is a first worldwide. This match run generated LDLTs for 6 patients, revealing the value of the capacity to carry out larger than 2-way exchanges. With only 2-way exchanges, only 4 of these patients would receive a LDLT. The number of LDLTs from LPE can be increased by developing the capacity to perform larger than 2-way exchanges in either high-volume centers or multicenter programs.

Finding long chains in kidney exchange using the traveling salesman problem

As of May 2014 there were more than 100,000 patients on the waiting list for a kidney transplant from a deceased donor. Although the preferred treatment is a kidney transplant, every year there are fewer donors than new patients, so the wait for a transplant continues to grow. To address this shortage, kidney paired donation (KPD) programs allow patients with living but biologically incompatible donors to exchange donors through cycles or chains initiated by altruistic (nondirected) donors, thereby increasing the supply of kidneys in the system. In many KPD programs a centralized algorithm determines which exchanges will take place to maximize the total number of transplants performed. This optimization problem has proven challenging both in theory, because it is NP-hard, and in practice, because the algorithms previously used were unable to optimally search over all long chains. We give two new algorithms that use integer programming to optimally solve this problem, one of which is inspired by the techniques used to solve the traveling salesman problem. These algorithms provide the tools needed to find optimal solutions in practice.

Allocation and matching in kidney exchange programs

Living donor kidney transplantation is the preferred treatment for patients suffering from end-stage renal disease. To alleviate the shortage of kidney donors, many advances have been made to improve the utilization of living donors deemed incompatible with their intended recipient. The most prominent of these advances is kidney paired donation (KPD), which matches incompatible patient-donor pairs to facilitate a kidney exchange. This review discusses the various approaches to matching and allocation in KPD. In particular, it focuses on the underlying principles of matching and allocation approaches, the combination of KPD with other strategies such as ABO incompatible transplantation, the organization of KPD, and important future challenges. As the transplant community strives to balance quantity and equity of transplants to achieve the best possible outcomes, determining the right long-term allocation strategy becomes increasingly important. In this light, challenges include making full use of the various modalities that are now available through integrated and optimized matching software, encouragement of transplant centers to fully participate, improving transplant rates by focusing on the expected long-run number of transplants, and selecting uniform allocation criteria to facilitate international pools.