Kidney Exchange

Kidney disease progresses toward end-stage renal failure, at which point a patient requires dialysis or transplantation to survive. A transplanted kidney nearly always outperforms dialysis in both life-expectancy and quality-of-life terms, but the supply of deceased-donor kidneys is chronically insufficient, and living donation is blocked when the willing donor and their patient are incompatible on blood type (ABO) or human leukocyte antigen (HLA) cross-match.

In 1986, Felix Rapaport proposed pairing two incompatible donor-patient dyads so each donor gives to the other dyad's patient — a two-way kidney exchange. The idea remained largely theoretical until the early 2000s, when Roth, Sönmez & Ünver (2004) formalised the problem as a market-design question and showed that kidney exchange is a cycle-selection problem on a directed compatibility graph. Their 2005 follow-up extended the machinery to longer cycles and to chains initiated by nondirected (altruistic) donors, unlocking substantially more transplants per pool.

Deployed kidney-paired-donation (KPD) programmes now include the New England Program for Kidney Exchange (NEPKE, 2003), the Alliance for Paired Donation (APD), the National Kidney Registry (NKR, 2007), and the UNOS KPD Pilot (2010). The underlying operations-research machinery — cycle enumeration, ILP selection, chain-extension heuristics — is essentially what this page explores. The work earned Alvin Roth a share of the 2012 Nobel Prize in Economic Sciences, alongside Lloyd Shapley, "for the theory of stable allocations and the practice of market design."

Multi-stakeholder framing

Let V be the set of patient-donor pairs in the pool. Build a directed graph G = (V, E) where edge (i, j) ∈ E exists iff donor i is medically compatible with patient j. A feasible exchange is a simple cycle in G: each pair in the cycle gives a kidney from its donor to the next pair's patient and receives a kidney from the previous pair's donor. The bounded-cycle ILP of Roth, Sönmez & Ünver (2005) selects a collection of vertex-disjoint cycles to maximise matched patients subject to a maximum cycle length L.

Two practical observations drive real-world deployment. First, L cannot be arbitrarily large because surgeries in a cycle must happen simultaneously (otherwise an early donor could renege after their patient received a kidney). The surgical logistics of three-way simultaneous surgery across three cities is already complex; four-way and beyond are rarely attempted for cycles. Chains relax this constraint because the altruistic donor cannot renege with anything at stake, so chain length can be much larger.

Second, weights w_c carry ethics. Setting w_c = |c| maximises transplant count. Setting priority points for hard-to-match patients (high panel-reactive antibodies, O-blood-type recipients, paediatric cases) explicitly favours those patients — which UNOS policy does. The choice of weights is not a technical detail; it is an ethics decision that OR surfaces rather than hides.

About the solver. The dashboard generates a synthetic compatibility graph with realistic blood-type-driven density (ABO self-matches plus random HLA-style cross-matches). The solver enumerates all simple directed cycles up to length L (bounded enumeration, polynomial in small L), then selects a maximum-weight packing using a greedy ILP relaxation + repair heuristic. For production KPD programmes, see Abraham, Blum & Sandholm (2007) on column-generation branch-and-price for cycle-selection, which scales to several thousand pairs.