Metraipolis › archive › dc_f9e017c078ea

Optimal Contention Resolution from Samples — arXiv:2611.08673

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.08673
License (as archived)
CC0-1.0
Archived
2026-11-09T22:37:54.132Z
SHA-256 of the archived text
4d015aa72cfd41a37bcc8958901110758ccaab465832916b4fecc7e367c6e881
Stable URL of this page
https://metraipolis.com/documento/dc_f9e017c078ea

How to cite

Optimal Contention Resolution from Samples — arXiv:2611.08673 — arXiv (en), https://arxiv.org/abs/2611.08673 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_f9e017c078ea (Metraipolis archive dc_f9e017c078ea, sha256 4d015aa72cfd41a37bcc8958901110758ccaab465832916b4fecc7e367c6e881)
BibTeX
@misc{dcf9e017c078ea,
  title = {Optimal Contention Resolution from Samples — arXiv:2611.08673},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.08673},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_f9e017c078ea; sha256 4d015aa72cfd41a37bcc8958901110758ccaab465832916b4fecc7e367c6e881},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.08673. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Contention resolution schemes convert random sets which are ex-ante feasible for some constraint into sets which are feasible ex post, and their online variants have broad applications in Bayesian and stochastic optimization, including prophet inequalities and stochastic probing. In many such applications, however, full distributional knowledge is an unattainable requirement. This motivates the study of contention resolution schemes which employ a limited number of samples from the underlying distributions. We study sample-based contention resolution for $k$-uniform matroids, for both uniformly random and adversarial arrival orders, and compare their balance guarantees to the best possible with full distributional knowledge. For a single-item constraint, we show that one sample per element suffices for an optimal $(1-1/e)$-balanced ROCRS. For adversarial arrivals, however, we prove that no single-sample OCRS can be $1/2$-balanced, even for known arrival orders, separating contention resolution from prophet inequalities in the single-sample setting. Perhaps surprisingly, we show that two samples are necessary and sufficient for the optimal $1/2$ guarantee. We also present a single-sample $0.48$-balanced scheme. For general $k$, we give a simple single-sample ROCRS that achieves an optimal balance ratio of $1-e^{-k}k^k/k!$. In adversarial order, we obtain a single-sample $(1 - O(1/\sqrt{k}))$-balanced scheme, matching the optimal asymptotic dependence on $k$. Finally, we complete the picture by characterizing the minimum number of samples needed to match the optimal balance ratio achievable with full distributional knowledge. For random arrivals, one sample suffices for $k = 1,2,3,4$, and zero samples suffice for $k \geq 5$. For an adversarial arrival order, even known in advance, and any $k \geq 2$, we show that no constant number of samples suffices to achieve optimal balance.

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/2611.08673 — 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-11-09T22:32:17.021Z dalla pagina https://arxiv.org/list/cs.GT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).