{"id":"arxiv/2610.12991","url":"https://arxiv.org/abs/2610.12991","tags":["cs.DS","cs.CC","cs.GT","econ.TH","math.OC"],"score":0,"title":"Dynamic Matching with Abandonment: Optimal Guarantees via Static Priority Policies","domain":"cs.DS","source":"arxiv","authors":["Nick Arnosti","Rad Niazadeh","Pranav Nuti","Felipe Simon"],"reviews":0,"subject":"cs.DS","summary":"We study stochastic dynamic matching with abandonment, a fundamental model in which agents of different types arrive over time, may abandon the market while waiting, and can be matched in pairs for rewards that depend on their types. No online policy can guarantee more than $0.5$ of the omniscient benchmark, which knows all arrival and departure times. Whether this guarantee is achievable has been a central open problem, even in special cases. We resolve this problem by showing that, on every instance, a simple static priority policy, which is computable in polynomial time, earns at least…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-09","reactions":{}}