Position-Indexed Formulations for Kidney Exchange

Understand

A kidney exchange is an organized barter market where patients in need of a kidney swap willing but incompatible donors.

• Determining an optimal set of exchanges is theoretically and empirically hard.
• Traditionally, exchanges took place in cycles, with each participating patient-donor pair both giving and receiving a kidney.
• The recent introduction of chains, where a donor without a paired patient triggers a sequence of donations without requiring a kidney in return, increased the efficacy of fielded kidney exchanges---while also dramatically raising the empirical computational hardness of clearing the market in practice.