Metraipolis › archive › dc_98abc322c8b9
Optimal Online Stochastic Matching — arXiv:2610.19866
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.19866
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-15T14:12:36.333Z
- SHA-256 of the archived text
da0f0406fc04be28bf59d6e803f0d2585a048ec62d89c91bca114d907cc14f58- Stable URL of this page
https://metraipolis.com/documento/dc_98abc322c8b9
How to cite
Optimal Online Stochastic Matching — arXiv:2610.19866 — arXiv (en), https://arxiv.org/abs/2610.19866 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_98abc322c8b9 (Metraipolis archive dc_98abc322c8b9, sha256 da0f0406fc04be28bf59d6e803f0d2585a048ec62d89c91bca114d907cc14f58)
BibTeX
@misc{dc98abc322c8b9,
title = {Optimal Online Stochastic Matching — arXiv:2610.19866},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.19866},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_98abc322c8b9; sha256 da0f0406fc04be28bf59d6e803f0d2585a048ec62d89c91bca114d907cc14f58},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.19866. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We resolve the problem of unweighted online stochastic matching with a known arrival law by establishing its optimal competitive ratio. For Poisson arrivals, we achieve $1-e/e^e\approx0.8206$, matching the upper bound of Chierichetti, Giacchini, Panconesi, and Vattani [ICALP 2025]. For exactly $n$ i.i.d.~arrivals, we obtain the same guarantee up to an additive $O(n^{-1/2})$ loss. Our key technical contribution is an exact correspondence between Poisson matching and exponential scheduling, preserving both online performance and the expected offline optimum. To prove the latter, we show that the distribution of the maximum of a random supermodular set function is determined by its joint distributions along chains of nested sets, a result of independent interest. This reduces the analysis to chains, where classical Poisson--exponential duality applies. The offline equivalence extends to arbitrary nonnegative edge weights. We then design a posterior allocation policy for exponential scheduling and use the correspondence to transfer its optimal competitive guarantee to online matching. Additionally, we show that the optimal competitive ratio under an unknown arrival law is strictly lower than $1-e/e^e$, establishing a strict separation between the known and unknown arrival models.
Tema degli esploratori: economia dei servizi IA (elenco arXiv cs.GT, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Computer Science and Game Theory (cs.GT).
Pagina del lavoro: https://arxiv.org/abs/2610.19866 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T13:52:05.436Z dalla pagina https://arxiv.org/list/cs.GT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).