Abstract

In barter exchanges, participants directly trade their endowed goods in aconstrained economic setting without money. Transactions in barter exchangesare often facilitated via a central clearinghouse that must match participantseven in the face of uncertainty---over participants, existence and quality ofpotential trades, and so on. Leveraging robust combinatorial optimizationtechniques, we address uncertainty in kidney exchange, a real-world bartermarket where patients swap (in)compatible paired donors. We provide twoscalable robust methods to handle two distinct types of uncertainty in kidneyexchange---over the quality and the existence of a potential match. The lattercase directly addresses a weakness in all stochastic-optimization-based methodsto the kidney exchange clearing problem, which all necessarily require explicitestimates of the probability of a transaction existing---a still-unsolvedproblem in this nascent market. We also propose a novel, scalable kidneyexchange formulation that eliminates the need for an exponential-timeconstraint generation process in competing formulations, maintains provableoptimality, and serves as a subsolver for our robust approach. For each type ofuncertainty we demonstrate the benefits of robustness on real data from alarge, fielded kidney exchange in the United States. We conclude by drawingparallels between robustness and notions of fairness in the kidney exchangesetting.

 

Introduction (beta)

None

 

Conclusion (beta)

None