Near-Optimal Dynamic Matching via Coarsening with Application to Heart Transplantation
This work addresses the gap between data-driven heuristics and theoretical bounds in online matching, specifically for organ allocation, though it is incremental as it builds on prior clustering approaches.
The paper tackled the problem of online matching in domains like organ allocation by developing a coarsening-based algorithm that aggregates nodes into clusters, achieving near-optimal theoretical guarantees. In simulations for heart transplant allocation, the policy closely matched the performance of an omniscient benchmark.
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. In realistic simulations, our policy closely matches the performance of the omniscient benchmark. Our work bridges the gap between data-driven heuristics and pessimistic theoretical lower bounds, and provides rigorous justification for prior clustering-based approaches in organ allocation.