# Scalable Robust Kidney Exchange

arXiv: https://arxiv.org/abs/1811.03532 · HTML: https://mlsanity.com/paper/1811.03532/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Nov 2018.

## Built on by (most cited first, 3 of 3)

- [Fair Clustering: Critique, Caveats, and Future Directions](https://mlsanity.com/paper/2406.15960/) (2024)
- [Fairness-aware kidney exchange and kidney paired donation](https://mlsanity.com/paper/2503.06431/) (2025)
- [Welfare-Centric Clustering](https://mlsanity.com/paper/2508.10345/) (2025)

## Abstract (arXiv)

In barter exchanges, participants directly trade their endowed goods in a constrained economic setting without money. Transactions in barter exchanges are often facilitated via a central clearinghouse that must match participants even in the face of uncertainty---over participants, existence and quality of potential trades, and so on. Leveraging robust combinatorial optimization techniques, we address uncertainty in kidney exchange, a real-world barter market where patients swap (in)compatible paired donors. We provide two scalable robust methods to handle two distinct types of uncertainty in kidney exchange---over the quality and the existence of a potential match. The latter case directly addresses a weakness in all stochastic-optimization-based methods to the kidney exchange clearing problem, which all necessarily require explicit estimates of the probability of a transaction existing---a still-unsolved problem in this nascent market. We also propose a novel, scalable kidney exchange formulation that eliminates the need for an exponential-time constraint generation process in competing formulations, maintains provable optimality, and serves as a subsolver for our robust approach. For each type of uncertainty we demonstrate the benefits of robustness on real data from a large, fielded kidney exchange in the United States. We conclude by drawing parallels between robustness and notions of fairness in the kidney exchange setting.