Incompatible donor-recipient pairs can exchange kidneys through cycles. Roth, Sonmez, and Unver (2004) showed that 2-cycles and 3-cycles capture most efficiency gains.
| Donor \ Patient | O | A | B | AB |
|---|---|---|---|---|
| O | ✓ | ✓ | ✓ | ✓ |
| A | ✗ | ✓ | ✗ | ✓ |
| B | ✗ | ✗ | ✓ | ✓ |
| AB | ✗ | ✗ | ✗ | ✓ |
Directed edge from Pair X to Pair Y means X's donor can donate to Y's patient.
Kidney exchange uses the same cycle-finding logic as Top Trading Cycles (TTC). Each incompatible pair "points to" the pair whose patient their donor can help. Cycles in this graph represent feasible simultaneous exchanges where all surgeries happen at once (to prevent reneging).
Roth, Sonmez, and Unver (2004) showed that limiting to 2- and 3-way exchanges captures most efficiency gains. The New England Program for Kidney Exchange ran its first 3-way exchange in 2003. Today, approximately 5,000 living-donor kidney transplants happen annually in the US, with ~15% through paired exchanges.
The introduction of altruistic (non-directed) donors enables chains of exchanges that can be much longer than cycles, dramatically increasing the number of transplants.
Roth, A.E., Sonmez, T., & Unver, M.U. (2004). "Kidney Exchange." Quarterly Journal of Economics, 119(2): 457-488.