Recourse-Bounded Repair for Kidney Exchange Under Crossmatch Failure

Kidney paired donation lets a patient with a willing but incompatible donor trade donors with other such pairs, in closed loops of two or three pairs or in open chains started by an altruistic donor. Most planned transplants never happen. Late blood tests, called crossmatches, fail; donors get sick; patients withdraw. Reported failure rates for planned transplants run from 70% to 85% (Operation Frames and Clubs in Kidney Exchange, Improving Policy-Constrained Kidney Exchange via Pre-Screening). When one planned transplant fails, the exchange must re-plan. The usual answer is to re-solve the whole optimization from scratch, which takes minutes (Multi-Organ Exchange). Computation is therefore not the bottleneck. The real cost of re-planning is disruption. Every pair whose assignment changes needs a new crossmatch, and that new test can itself fail. It also takes clinical time, and some patients die while they wait.

This note proposes treating kidney exchange re-planning as a problem of maintaining a dynamic graph under a limited number of changes. The question is how to keep a near-optimal set of cycles and chains when failures and arrivals keep coming, while changing as few existing assignments as possible. The dynamic-matching literature has a precise tool for this. It counts recourse, meaning how many times an edge's status may flip, and it shows that limiting repairs to short changes beats making large global ones (Online maximum matching with recourse). We carry that idea into directed cycle and chain packing. We add one ingredient specific to this domain: repairs should prefer edges whose crossmatch has already come back negative, because those edges are far less likely to fail again.

Core Claim

The claim is that, over a fixed horizon, a repair policy that respects a per-pair budget on reassignments produces more realized transplants and fewer patient deaths than full re-solving. The policy has two features. It limits each repair to a small neighborhood of the failure, and it routes repairs through a maintained subgraph of already-verified edges. The reason is that a full re-solve treats every edge as equally available, so it spends crossmatch time and failure risk on reassignments a local repair would avoid.

The theoretical half of the claim rests on a reduction. If only two-way swaps are allowed, the exchange is an ordinary undirected matching on the graph of mutually compatible pairs. In that case the short-repair guarantee of Online maximum matching with recourse applies directly. That paper's L-Greedy algorithm allows only repairs of length at most $2L+1$ and reaches a competitive ratio of $1+O(1/\sqrt{k})$ for per-edge budget $k$. What we must work out is how far that guarantee survives when three-way cycles and altruist-rooted chains are added. In those structures a single failure deletes several planned edges at once.

Research Program

The first component is a model and simulator. Pairs and altruistic donors arrive and depart following the Saidman generator dynamics already used in Dynamic Matching via Weighted Myopia with Application to Kidney Exchange. Departure rates are higher for medically fragile patients, as in Fair Matching in Dynamic Kidney Exchange. Each planned edge is crossmatched, which takes a delay $\tau$ and fails with probability $q$, with $q$ swept from 0.7 to 0.85 to match the reported range. Edges that pass join a verified subgraph, where a much lower residual failure rate applies. Each pair carries a reassignment budget $k$. The file reports no clinical value for $\tau$, so we sweep it, and every result will be reported as a function of $\tau$. Prior static evaluations leave out this time cost, and including it is what makes recourse matter.

The second component is the repair rule. When a planned edge fails, the rule removes its cycle, or cuts its chain at the failure point. Under the non-simultaneous logic of Kidney Exchange in Dynamic Sparse Heterogenous Pools, the donor at the cut becomes a bridge that can start a new chain. The rule then solves a small integer program over pairs within $r$ hops of the damage, using only pairs with remaining budget. It adds a bonus for verified edges and a penalty that depends on each pair's remaining budget. Keeping the bridge donor and the verified edges alive borrows directly from the lazy deletion policy in The DiskANN library. That system keeps deleted vertices as routing intermediaries so its search graph stays navigable. Here, broken plans leave behind tested, reusable structure instead of being discarded. Periodic full re-solves still run, but at a slow cadence, playing the role of DiskANN's consolidation step.

The third component is analysis. For the two-way-only case we inherit the L-Greedy bound and examine its parity behavior. Greedy recourse alternates between ratios of 3/2 and 2 depending on whether $k$ is even or odd (Online maximum matching with recourse). For cycles of length at most three and for chains, we aim for a bound in $k$ and $r$, or failing that a lower-bound instance showing that local repair loses a constant factor. A negative result is a legitimate outcome. Chains complicate the picture. Efficient Dynamic Barter Exchange shows that unbounded chains cut waiting time to $O(1/p)$, compared with $O(1/p^2)$ for two-way cycles, while Scalable Robust Kidney Exchange finds long chains fragile under failures. Chain repair by re-attaching at the bridge donor is exactly where these two results meet.

The work differs from the closest dynamic kidney exchange studies in what it changes. Dynamic Matching via Weighted Myopia learns when to match through static potentials by blood type, and Fair Matching in Dynamic Kidney Exchange sets whom to prioritize at each batch. Both re-solve every batch globally and assign no cost to changing a plan, and that cost is the variable we study. We deliberately set aside sublinear-update-time machinery such as Maintaining an EDCS in General Graphs and Beating the Folklore Algorithm for Dynamic Matching. Pools of hundreds to a few thousand pairs do not need it.

Baselines

The naive reference point is full re-solving after every failure and arrival, using the standard maximum-weight cycle-and-chain integer program with cycles of length at most 3 and a chain cap. It ignores both recourse and verification status. All methods share the same simulated event stream, the same random seeds, the same solver, and the same time limit per call. To beat this baseline, our rule must deliver more realized transplants and fewer deaths over the horizon at every $\tau$ above a crossover point we report.

The strongest competitor is a stability-penalized global re-solve. This is the same full program with a tuned penalty on each changed assignment and a tuned bonus for verified edges. It is the obvious engineering fix, and it could plausibly match our rule, because it can choose local repairs whenever they are best. It receives the same hyperparameter search budget as our method, with tuning on training seeds and evaluation on held-out seeds. To beat it, our rule must show a statistically significant gain in realized transplants, measured by a Wilcoxon signed-rank test over paired seeds as in Dynamic Matching via Weighted Myopia. The gain must come at comparable or lower per-pair recourse and be concentrated among highly sensitized patients, the group that pays most for repeated crossmatches. If we find no such gain, we will report that the penalty alone is enough. That outcome would still establish that modeling recourse is the useful contribution.

We also compare against published methods with reported numbers. Weighted Myopia reports roughly an 18% closure of the gap between myopic matching and perfect foresight in 510-pair pools (Dynamic Matching via Weighted Myopia). Operation frames report a 34%–51% increase in successful matches over batch clearing under a 70% failure rate (Operation Frames and Clubs in Kidney Exchange). Pre-screening 10 edges reports a more-than-100% increase in expected transplants under an 85% failure rate (Improving Policy-Constrained Kidney Exchange via Pre-Screening). None of these numbers was measured under a recourse-time cost, and no reported result was found on Lacuna for realized transplants under a reassignment budget. We therefore re-run each method inside our simulator rather than comparing against the published figures directly.

Three ablations isolate the ingredients. The first removes the verified-edge bonus. The second removes locality by setting $r$ to infinity under a budget penalty. The third replaces budget-aware penalties with a flat one.

Why not just…?

Why not just re-solve from scratch, since it only takes minutes? Solving fast does not make a solution cheap to carry out. Each new assignment costs a crossmatch delay $\tau$ and a fresh failure draw. Timing matters a great deal in heterogeneous pools: Continuous Time Analysis of Dynamic Matching in Heterogeneous Networks finds unmatched loss falling only as $\Theta(1/d)$ in network density $d$ under greedy matching, but as $e^{-cd}$ under patient matching. The $\tau$ sweep will show the delay at which full re-solving stops winning. If that crossover sits above any plausible clinical delay, the proposal fails, and we will say so.

Why not just add a stability penalty to the existing integer program? This alternative is the real threat. That is why it is the headline baseline with an equal tuning budget, and why the ablations separate what locality, verification, and budget-awareness each contribute. The case for expecting a gap is the parity and wasted-recourse effect in Online maximum matching with recourse. A flat penalty spends budget equally on long and short repairs, while bounding repair length avoids wasting it. The experiment either confirms that this effect carries over to cycles and chains or refutes it.

Why not just pre-screen risky edges before matching? Pre-screening (Improving Policy-Constrained Kidney Exchange via Pre-Screening) acts before a match run and relies on static probability estimates. It does not decide what to do after a failure. The two approaches fit together, since pre-screened negatives feed the verified subgraph. We will test pre-screening alone, our repair rule alone, and the two combined.

Why not just use Weighted Myopia's learned potentials? Those potentials are fixed per blood-type category and do not react to plans breaking (Dynamic Matching via Weighted Myopia). They decide when to spend flexible donors, not how to repair a broken plan. We stack them on top of both the baseline and our rule to check that the gains are additive.

Proposed Experiments

The main experiments use Saidman-generated dynamic pools at the scales in Dynamic Matching via Weighted Myopia, up to roughly 700 pairs, with 5% altruists. We sweep $q$ over {0.7, 0.85}, $\tau$ across a wide range, and $k$ from 1 to 6. Where access permits, we replay the UNOS match-run graphs used in Balancing Lexicographic Fairness and a Utilitarian Objective as starting pools.

We measure five things: realized transplants per simulated year, patient deaths while waiting, the mean and maximum number of reassignments per pair, crossmatches ordered per realized transplant, and the transplant share going to highly sensitized patients.

The decisive check is the head-to-head against the tuned stability-penalized re-solve, read across the $\tau$ sweep. A secondary check tests the two-way-only theory. In that setting the empirical ratio against offline-optimal packings should track the inherited $1+O(1/\sqrt{k})$ bound, and its degradation once three-way cycles and chains are allowed tells us how much of the theory carries over.