Dynamic Matching with Abandonment: Optimal Guarantees via Static Priority Policies
Abstract
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 $0.5$ of the omniscient benchmark. This establishes that the optimal competitive ratio is exactly $0.5$, improving the previous best guarantee of 0.192 for the general model [Li et al. 2026; Collina et al. 2020] Our analysis rests on a key stochastic result, which is a new lower bound on the probability that some agent from a given set of types is available. Building on this bound, we develop two approaches: a primal approach that reads the priorities from an optimal solution of a novel linear program, and a dual approach that assigns a ``value'' to each type, and prioritizes matches with high ``surplus'' (reward minus value of involved agents). These values are the unique solution of a fixed-point equation derived from linear programming duality. We also show that the two approaches are closely connected.
Related
- Longest-Queue Policies in Dynamic Matching with Abandonments
- Tight Guarantees for Static Policies in Vehicle Sharing Networks
- Diffusion Flow Matching: Dimension-Improved KL Bounds and Wasserstein Guarantees
- Inter-Temporal Price Constraints in Dynamic Pricing: Performance Guarantees Under Price Monotonicity and Promotion Fatigue
- Climate Physics Dynamic Matching
BibTeX
@misc{arnosti2026dynamic,
title = {{Dynamic Matching with Abandonment: Optimal Guarantees via Static Priority Policies}},
author = {Nick Arnosti and Rad Niazadeh and Pranav Nuti and Felipe Simon},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.12991},
eprint = {2610.12991},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.12991},
}
RIS
TY - UNPB
TI - Dynamic Matching with Abandonment: Optimal Guarantees via Static Priority Policies
AU - Nick Arnosti
AU - Rad Niazadeh
AU - Pranav Nuti
AU - Felipe Simon
PY - 2026
DA - 2026/10/09
PB - arXiv
DO - 10.48550/arxiv.2610.12991
UR - https://arxiv.org/abs/2610.12991
AB - 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 $0.5$ of the omniscient benchmark. This establishes that the optimal competitive ratio is exactly $0.5$, improving the previous best guarantee of 0.192 for the general model [Li et al. 2026; Collina et al. 2020] Our analysis rests on a key stochastic result, which is a new lower bound on the probability that some agent from a given set of types is available. Building on this bound, we develop two approaches: a primal approach that reads the priorities from an optimal solution of a novel linear program, and a dual approach that assigns a ``value'' to each type, and prioritizes matches with high ``surplus'' (reward minus value of involved agents). These values are the unique solution of a fixed-point equation derived from linear programming duality. We also show that the two approaches are closely connected.
ER -