Reducibility
Glossary Contents
← Ch XVI
Chapter XVII 3-Dimensional Matching
Ch XVIII →
  1. 49 — Two sides easy, three sides hard
  2. 50 — Backtracking in Swift
  3. 51 — The kidney exchange
51

The kidney exchange

Three-way kidney exchanges (donor → patient cycles) are the most morally consequential 3-DM instance running anywhere.

A patient with a willing but incompatible donor can be matched in a kidney exchange chain: donor A gives to patient B, donor B gives to patient C, donor C gives to patient A. Three-way exchanges form 3-cycles in a directed compatibility graph; finding the maximum number of three-cycles that share no vertex is a 3-D matching variant. The US National Kidney Registry runs exactly this optimization. Alvin Roth's Nobel-winning work on market design productionized the math. The same template runs in labor-market matching (worker, employer, role), in logistics (truck, dock, time slot), and in dating apps (with the third dimension being context — coffee, dinner, weekend trip).

In plain terms

If your spouse needs a kidney and you can't donate to them, you can be matched in a triangle: you donate to someone else, that person's spouse donates to a third person, that third person's spouse donates to your spouse. Finding as many such triangles as possible without anyone double-booked is 3-D matching.

Scan to come back to page 51

End of Chapter XVII
Chapter XVIII Knapsack →
← 50 Backtracking in Swift
3/3 · 51/63
52 The knapsack →