Near-Optimal Dynamic Matching via Coarsening with Application to Heart Transplantation

Online matching has been a mainstay in domains such as Internet advertising and organ allocation, but practical algorithms often lack strong theoretical guarantees. We take an important step toward addressing this by developing new online matching algorithms based on a coarsening approach. Although coarsening typically implies a loss of granularity, we show that, to the contrary, aggregating offline nodes into capacitated clusters can yield near-optimal theoretical guarantees. We apply our methodology to heart transplant allocation to develop theoretically grounded policies based on structural properties of historical data. Furthermore, in simulations based on real data, our policy closely matches the performance of the omniscient benchmark, achieving competitive ratio 0.91, drastically higher than the US status quo policy's 0.51. Our work bridges the gap between data-driven heuristics and pessimistic theoretical lower bounds.

Heart transplantation is the therapy of choice for patients suffering from end-stage heart failure. However, the scarcity of donor organs has created a wide chasm between supply and demand. When matching patients to donors in real-time, algorithms often struggle to make perfect life-or-death decisions. We develop a method to allocate donor hearts by learning which patients have similar transplant outcomes, and carefully grouping similar patients together, a method we refer to as coarsening. Through coarsening, we can guarantee that the scarce donor hearts are routed to the patients that benefit from them most. When evaluated on real heart transplant data, our methods nearly double the population life years compared to the current US heart transplantation policy.