Optimal kidney exchange

Last updated

Optimal kidney exchange (OKE) is an optimization problem faced by programs for kidney paired donations (also called Kidney Exchange Programs). Such programs have large databases of patient-donor pairs, where the donor is willing to donate a kidney in order to help the patient, but cannot do so due to medical incompatibility. The centers try to arrange exchanges between such pairs. For example, the donor in pair A donates to the patient in pair B, the donor in pair B donates to the patient in pair C, and the donor in pair C donates to the patient in pair A.

Contents

The objective of the OKE problem is to find an optimal arrangement of such exchanges. "Optimal" usually means that the number of transplants is as large as possible, but there may be other objectives. A crucial constraint in this optimization problem is that a donor gives a kidney only if his patient receives a compatible kidney, so that no pair loses a kidney from participating. This requirement is sometimes called individual rationality.

The OKE problem has many variants, which differ in the allowed size of each exchange, the objective function, and other factors. [1]

Definitions

Input

An instance of OKE is usually described as a directed graph. Every node represents a patient-donor pair. A directed arc from pair A to pair B means that the donor in pair A is medically compatible with the patient in pair B (compatibility is determined based on the blood types of the donor and patient, as well as other factors such as particular antigens in their blood). A directed cycle in the compatibility graph represents a possible exchange. A directed cycle of size 2 (e.g. A -> B -> A) represents a possible pairwise exchange - an exchange between a pair of pairs.

A more general variant of OKE considers also nodes of a second type, that represent altruistic donors - donors who are not paired to a patient, and are willing to donate a kidney to any compatible patient. Altruistic donor nodes have only outgoing arcs. With altruistic donors, it is possible to arrange exchanges not only with cycles but also with chains, starting at an altruistic donor.

The arcs in the graph may have weights, representing e.g. the probability of success of the involved transplants. They may also have priorities, determined e.g. by medical urgency or by the time the patient have waited in the transplantation queue.

Output

The output of an OKE is a set of pairwise-disjoint directed cycles (and possibly directed chains, if altruistic donors are available). The simplest objective in OKE is to maximize the number of patients who receive a kidney. Other common objectives are:

Unrestricted cycle length

Initially, the problem was studied without any bound on the length of the exchange cycles. Roth, Sonmez and Unver [4] presented a mechanism, based on an extension of the top trading cycles mechanism, for finding exchange cycles in a Pareto-optimal and incentive-compatible way.

Abraham, Blum and Sandholm [5] show that, with unbounded cycle length, a maximum-cardinality and maximum-weight exchange can be found in polynomial time. For example, to find a maximum-cardinality exchange, given the original directed graph G, construct an undirected bipartite graph H(X+Y, E) in which:

Every maximum-cardinality exchange in G corresponds to a maximum-weight matching in H. Note that the weights guarantee that every maximum-weight matching in H is perfect, so that every patient is matched, either to a compatible donor, or to his own donor. So no donor gives a kidney unless his patient receives a kidney, which satisfies the requirement of individual rationality.

It is easy to extend this algorithm to maximum-weight exchanges, and to incorporate altruistic donors.

Pairwise kidney exchange

In the discussions towards implementing a kidney exchange program in New England in 2004, it was found out that, logistically, only pairwise exchanges are possible. This is because all operations in an exchange must be done simultaneously. This requirement aims to ensure the individual rationality constraint - to avoid the risk that a donor refuses to donate after his patient has received a kidney. An exchange cycle of size k requires 2k simultaneous operations. At that time, it was not practical to arrange more than 4 simultaneous operations, so the size of cycles was limited to 2. [6]

In this setting, it is possible to reduce the directed compatibility graph to an undirected graph, where pairs A and B are connected if and only if A->B and B->A. Finding a maximum-cardinality pairwise exchange is equivalent to finding a maximum cardinality matching in that undirected graph. Moreover, when only pairwise exchanges are allowed, a matching is Pareto-efficient if and only if it has maximum cardinality. [6] : Lem.1  Therefore, such an exchange can be found in polynomial time.

Roth, Sonmez and Unver [6] study two extensions of the simple maximum-cardinality exchange:

Cycles of length k

In later years, logistic improvements allowed the execution of larger number of simultaneous operations. Accordingly, exchange cycles involving three or more pairs were made possible. Finding a maximum-cardinality exchange is called, in graph theoretic terms, maximum cycle packing. Maximum cycle packing with cycles of length at most k, for any fixed k ≥ 3, is an NP-hard computational problem [5] (this can be proved by reduction from the problem of 3-dimensional matching in a hypergraph).

Abraham, Blum and Sandholm [5] present two techniques for maximum cycle packing: column generation and constraint generation. They report that column generation scales much better. Their algorithm have been implemented in the Alliance for Paired Kidney Donations.

Biro, Manlove and Rizzi [7] suggest two approaches for solving this problem even when the edges have weights (in which case it is called maximum-weight cycle packing):

Cycles of length k, and chains of unbounded length

Altruistic donors can be used to initiate a chain of exchanges, that is not a cycle. In such a chain, the operations need not be done simultaneously: it is possible to guarantee to each patient that he receives a kidney before his donor gives a kidney. If a donor defects, it breaks the chain, but it does not harm patients whose donor already gave a kidney, so it does not break individual rationality.

Anderson, Ashlagi, Gamarnik and Roth [8] present two algorithms for finding a maximum-cardinality packing into cycles of length at most k and chains of unbounded length:

Uncertain transplants

Early theoretic works in OKE assumed that, once a set of exchanges is determined, all of them will be executed. In practice, however, transplants might be cancelled. For example, the medical examination done just before the transplant might reveal that the donor is incompatible with the patient, even though in the database they are registered as compatible. Therefore, newer works aim to maximize the expected number of transplants. For example, Alvelos, Klimentova and Viana [9] present a branch-and-price algorithm for this problem.

Further references

Related Research Articles

<span class="mw-page-title-main">Assignment problem</span> Combinatorial optimization problem

The assignment problem is a fundamental combinatorial optimization problem. In its most general form, the problem is as follows:

<span class="mw-page-title-main">Bipartite graph</span> Graph divided into two independent sets

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets and , that is, every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.

In the mathematical discipline of graph theory, a matching or independent edge set in an undirected graph is a set of edges without common vertices. In other words, a subset of the edges is a matching if each vertex appears in at most one edge of that matching. Finding a matching in a bipartite graph can be treated as a network flow problem.

<span class="mw-page-title-main">Kidney transplantation</span> Medical procedure

Kidney transplant or renal transplant is the organ transplant of a kidney into a patient with end-stage kidney disease (ESRD). Kidney transplant is typically classified as deceased-donor or living-donor transplantation depending on the source of the donor organ. Living-donor kidney transplants are further characterized as genetically related (living-related) or non-related (living-unrelated) transplants, depending on whether a biological relationship exists between the donor and recipient. The first successful kidney transplant was performed in 1954 by a team including Joseph Murray, the recipient’s surgeon, and Hartwell Harrison, surgeon for the donor. Murray was awarded a Nobel Prize in Physiology or Medicine in 1990 for this and other work. In 2018, an estimated 95,479 kidney transplants were performed worldwide, 36% of which came from living donors.

Set packing is a classical NP-complete problem in computational complexity theory and combinatorics, and was one of Karp's 21 NP-complete problems. Suppose one has a finite set S and a list of subsets of S. Then, the set packing problem asks if some k subsets in the list are pairwise disjoint.

Maximum cardinality matching is a fundamental problem in graph theory. We are given a graph G, and the goal is to find a matching containing as many edges as possible; that is, a maximum cardinality subset of the edges such that each vertex is adjacent to at most one edge of the subset. As each edge will cover exactly two vertices, this problem is equivalent to the task of finding a matching that covers as many vertices as possible.

In computer science and graph theory, the maximum weight matching problem is the problem of finding, in a weighted graph, a matching in which the sum of weights is maximized.

<span class="mw-page-title-main">Alvin E. Roth</span> American academic (born 1951)

Alvin Eliot Roth is an American academic. He is the Craig and Susan McCaw professor of economics at Stanford University and the Gund professor of economics and business administration emeritus at Harvard University. He was President of the American Economic Association in 2017.

<span class="mw-page-title-main">Market design</span>

Market design is a practical methodology for creation of markets of certain properties, which is partially based on mechanism design. In some markets, prices may be used to induce the desired outcomes — these markets are the study of auction theory. In other markets, prices may not be used — these markets are the study of matching theory.

<span class="mw-page-title-main">3-dimensional matching</span>

In the mathematical discipline of graph theory, a 3-dimensional matching is a generalization of bipartite matching to 3-partite hypergraphs, which consist of hyperedges each of which contains 3 vertices.

In combinatorial optimization, the matroid intersection problem is to find a largest common independent set in two matroids over the same ground set. If the elements of the matroid are assigned real weights, the weighted matroid intersection problem is to find a common independent set with the maximum possible weight. These problems generalize many problems in combinatorial optimization including finding maximum matchings and maximum weight matchings in bipartite graphs and finding arborescences in directed graphs.

"Harvest" is the 14th episode of the second season of the American television show Numbers. Inspired by a Christian Science Monitor article about organ tourists, people who travel to a different country to give their organs for money, and an algorithm developed in the United States, the episode features Federal Bureau of Investigation (FBI) agents and mathematicians attempting to locate a missing organ tourist before she is killed.

Tayfun Sönmez is a Turkish-American professor of economics at Boston College. He is a Fellow of the Econometric Society and the 2008 winner of the Social Choice and Welfare Prize, which honors scholars under the age of 40 for excellent accomplishment in the area of social choice theory and welfare economics. Sönmez has made significant contributions in the areas of microeconomic theory, mechanism/market design, and game theory. His work has been featured by the U.S. National Science Foundation for its practical relevance.

The National Kidney Registry (NKR) is a national registry in the United States listing kidney donors and recipients in need of a kidney transplant. NKR facilitates over 450 "Kidney Paired Donation" (KPD) or "Paired Exchange" transplants annually.

Kidney paired donation (KPD), or paired exchange, is an approach to living donor kidney transplantation where patients with incompatible donors swap kidneys to receive a compatible kidney. KPD is used in situations where a potential donor is incompatible. Because better donor HLA and age matching are correlated with lower lifetime mortality and longer lasting kidney transplants, many compatible pairs are also participating in swaps to find better matched kidneys. In the United States, the National Kidney Registry organizes the majority of U.S. KPD transplants, including the largest swaps. The first large swap was a 60 participant chain in 2012 that appeared on the front page of the New York Times and the second, even larger swap, included 70 participants and was completed in 2014. Other KPD programs in the U.S. include the UNOS program, which was launched in 2010 and completed its 100th KPD transplant in 2014, and the Alliance for Paired Donation.

Top trading cycle (TTC) is an algorithm for trading indivisible items without using money. It was developed by David Gale and published by Herbert Scarf and Lloyd Shapley.

<span class="mw-page-title-main">Dorry Segev</span> American surgeon

Dorry L. Segev is the Marjory K. and Thomas Pozefsky Professor of Surgery at Johns Hopkins School of Medicine, professor of epidemiology at Johns Hopkins Bloomberg School of Public Health, and associate vice chair of the Department of Surgery at Johns Hopkins Hospital. He has made significant contributions to the field of transplantation, including developing a mathematical model to facilitate a nationwide kidney paired donation program, both in the US and Canada. He is also known for his role in getting the HIV Organ Policy Equity Act signed into law.

In graph theory, a maximally matchable edge in a graph is an edge that is included in at least one maximum-cardinality matching in the graph. An alternative term is allowed edge.

In graph theory, a priority matching (also called: maximum priority matching) is a matching that maximizes the number of high-priority vertices that participate in the matching. Formally, we are given a graph G = (V, E), and a partition of the vertex-set V into some k subsets, V1, …, Vk, called priority classes. A priority matching is a matching that, among all possible matchings, saturates the largest number of vertices from V1; subject to this, it saturates the largest number of vertices from V2; subject to this, it saturates the largest number of vertices from V3; and so on.

In economics and computer science, the house allocation problem is the problem of assigning objects to people with different preferences, such that each person receives exactly one object. The name "house allocation" comes from the main motivating application, which is assigning dormitory houses to students. Other commonly used terms are assignment problem and one-sided matching. When agents already own houses, the problem is often called a housing market. In house allocation problems, it is assumed that monetary transfers are not allowed; the variant in which monetary transfers are allowed is known as rental harmony.

References

  1. ↑ Ashlagi, Itai; Roth, Alvin E. (2021-09-01). "Kidney Exchange: An Operations Perspective". Management Science. 67 (9): 5455–5478. doi:10.1287/mnsc.2020.3954. ISSN   0025-1909.
  2. ↑ Manlove, David F.; O’malley, Gregg (2015-01-07). "Paired and Altruistic Kidney Donation in the UK: Algorithms and Experimentation". ACM Journal of Experimental Algorithmics. 19: 2.6:1–2.6:21. doi:10.1145/2670129. ISSN   1084-6654. S2CID   8744186.
  3. ↑ Zenios, Stefanos A.; Chertow, Glenn M.; Wein, Lawrence M. (2000-08-01). "Dynamic Allocation of Kidneys to Candidates on the Transplant Waiting List". Operations Research. 48 (4): 549–569. doi:10.1287/opre.48.4.549.12418. ISSN   0030-364X.
  4. ↑ Roth, A. E.; Sonmez, T.; Unver, M. U. (2004-05-01). "Kidney Exchange". The Quarterly Journal of Economics. 119 (2): 457–488. doi:10.1162/0033553041382157. ISSN   0033-5533.
  5. 1 2 3 Abraham, David J.; Blum, Avrim; Sandholm, Tuomas (2007-06-11). "Clearing algorithms for barter exchange markets". Proceedings of the 8th ACM conference on Electronic commerce. EC '07. New York, NY, USA: Association for Computing Machinery. pp. 295–304. doi:10.1145/1250910.1250954. ISBN   978-1-59593-653-0. S2CID   8909161.
  6. 1 2 3 Roth, Alvin E.; Sönmez, Tayfun; Utku Ünver, M. (2005-12-01). "Pairwise kidney exchange" (PDF). Journal of Economic Theory. 125 (2): 151–188. doi:10.1016/j.jet.2005.04.004. ISSN   0022-0531. S2CID   583399.
  7. ↑ Biró, Péter; Manlove, David F.; Rizzi, Romeo (2009-12-01). "Maximum weight cycle packing in directed graphs, with application to kidney exchange programs". Discrete Mathematics, Algorithms and Applications. 01 (4): 499–517. doi:10.1142/S1793830909000373. ISSN   1793-8309. S2CID   11337530.
  8. ↑ Anderson, Ross; Ashlagi, Itai; Gamarnik, David; Roth, Alvin E. (2015-01-20). "Finding long chains in kidney exchange using the traveling salesman problem". Proceedings of the National Academy of Sciences. 112 (3): 663–668. Bibcode:2015PNAS..112..663A. doi: 10.1073/pnas.1421853112 . ISSN   0027-8424. PMC   4311855 . PMID   25561535.
  9. ↑ Alvelos, Filipe; Klimentova, Xenia; Viana, Ana (2019-01-01). "Maximizing the expected number of transplants in kidney exchange programs with branch-and-price". Annals of Operations Research. 272 (1): 429–444. doi:10.1007/s10479-017-2647-4. ISSN   1572-9338. S2CID   254235768.
  10. ↑ Constantino, Miguel; Klimentova, Xenia; Viana, Ana; Rais, Abdur (2013-11-16). "New insights on integer-programming models for the kidney exchange problem". European Journal of Operational Research. 231 (1): 57–68. doi:10.1016/j.ejor.2013.05.025. hdl: 10400.22/3315 . ISSN   0377-2217.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.