Metraipolis › archive › dc_54e6e36fb2ae
Randomized Online Fair Division: High-Probability and Expected Realized Fairness — arXiv:2609.23577
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.23577
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-09T06:58:04.937Z
- SHA-256 of the archived text
620c69358fe1ba0df9ad813dcce5c648028d6e0f5539178e8aa1620490c3e740- Stable URL of this page
https://metraipolis.com/documento/dc_54e6e36fb2ae
How to cite
Randomized Online Fair Division: High-Probability and Expected Realized Fairness — arXiv:2609.23577 — arXiv (en), https://arxiv.org/abs/2609.23577 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_54e6e36fb2ae (Metraipolis archive dc_54e6e36fb2ae, sha256 620c69358fe1ba0df9ad813dcce5c648028d6e0f5539178e8aa1620490c3e740)
BibTeX
@misc{dc54e6e36fb2ae,
title = {Randomized Online Fair Division: High-Probability and Expected Realized Fairness — arXiv:2609.23577},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.23577},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_54e6e36fb2ae; sha256 620c69358fe1ba0df9ad813dcce5c648028d6e0f5539178e8aa1620490c3e740},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.23577. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study randomized algorithms for the fully online allocation of indivisible goods among $n\ge2$ agents with nonnegative additive valuations. Goods arrive sequentially and must be allocated immediately and irrevocably, with only $n$ known in advance. Since exact ex-ante envy freeness and proportionality are readily achievable, while no positive ex-post approximation is possible for the fairness notions considered here, we study the intermediate notions of high-probability fairness and expected realized fairness. Against a non-adaptive adversary, we give a randomized algorithm for proportionality up to one good (PROP1) whose parameter depends only on $n$ and that preserves exact ex-ante envy-freeness and proportionality. At confidence $1-\delta$, its PROP1 guarantee improves on independent uniform allocation (Rand) by a factor of $\Omega(\log n)$, uniformly over $\delta\in(0,1/2]$. As $n\to\infty$, its expected realized PROP1 factor is at least $\frac{3-\sqrt5}{2}-o(1)$. We also show that the expected realized PROP1 factor of Rand is $(1+o(1))/\log n$, yielding an improvement of at least $\bigl(\frac{3-\sqrt5}{2}-o(1)\bigr)\log n$ for our algorithm. For every randomized online algorithm and every positive approximation factor, the success probability can be made arbitrarily small for envy freeness up to any good (EFX) and at most $\frac{n+1}{2n}$ for envy freeness up to one good (EF1). Consequently, every randomized fully online algorithm has an expected realized EFX guarantee of zero and an expected realized EF1 guarantee of at most $\frac{n+1}{2n}$.
Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-09-22 in cs.GT).
Categorie arXiv: Computer Science and Game Theory (cs.GT).
Pagina del lavoro: https://arxiv.org/abs/2609.23577 — 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-09T06:52:12.759Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-09-22?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).