코어닝을 이용한 근사 최적 동적 매칭: 심장 이식 적용

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

온라인 매칭은 인터넷 광고 및 장기 배분과 같은 분야에서 중요한 역할을 해왔지만, 실제 알고리즘은 종종 강력한 이론적 보장을 제공하지 못합니다. 우리는 코어닝 접근 방식을 기반으로 새로운 온라인 매칭 알고리즘을 개발하여 이러한 문제를 해결하기 위한 중요한 진전을 이루었습니다. 일반적으로 코어닝은 세분화의 손실을 의미하지만, 우리는 오히려 오프라인 노드를 용량 제한된 클러스터로 집계하면 근사 최적의 이론적 보장을 얻을 수 있음을 보여줍니다. 우리는 개발한 방법론을 심장 이식 배분에 적용하여, 과거 데이터의 구조적 특성을 기반으로 이론적으로 검증된 정책을 개발했습니다. 또한, 실제 데이터를 기반으로 한 시뮬레이션에서, 개발된 정책은 전지적 기준(omniscient benchmark)의 성능과 거의 일치하며, 경쟁률(competitive ratio)이 0.91로, 이는 현재 미국의 정책인 0.51보다 훨씬 높은 수치입니다. 본 연구는 데이터 기반 휴리스틱과 비관적인 이론적 하한 사이의 간극을 좁히는 데 기여합니다.

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.