Metraipolis › archive › dc_ccb544249cea
Prophet Inequalities Beyond Utilitarian Social Welfare — arXiv:2609.25424
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.25424
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-08T14:40:51.248Z
- SHA-256 of the archived text
435c41c00a4d29c788bd94ee783ff1a154b9b3a47f4d29e9a675249a168af316- Stable URL of this page
https://metraipolis.com/documento/dc_ccb544249cea
How to cite
Prophet Inequalities Beyond Utilitarian Social Welfare — arXiv:2609.25424 — arXiv (en), https://arxiv.org/abs/2609.25424 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ccb544249cea (Metraipolis archive dc_ccb544249cea, sha256 435c41c00a4d29c788bd94ee783ff1a154b9b3a47f4d29e9a675249a168af316)
BibTeX
@misc{dcccb544249cea,
title = {Prophet Inequalities Beyond Utilitarian Social Welfare — arXiv:2609.25424},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.25424},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ccb544249cea; sha256 435c41c00a4d29c788bd94ee783ff1a154b9b3a47f4d29e9a675249a168af316},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.25424. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
In the classical i.i.d. prophet-inequality problem, a single item is allocated to one of $n$ agents who arrive sequentially, with values drawn independently from a known distribution. When an agent arrives, their value is revealed, and the algorithm must immediately allocate the item or continue. The usual objective is utilitarian welfare: the expected value of the recipient. Guarantees for this objective extend to allocating $m$ indivisible items to sequentially arriving agents with i.i.d.\ additive values. Utilitarian welfare, however, ignores how expected utility is distributed across agents. Motivated by a rich literature in fair division, we instead evaluate an online rule by its generalized $p$-mean welfare, which includes utilitarian welfare at $p=1$, Nash welfare (the geometric mean of utilities) at $p=0$, and egalitarian welfare (the minimum utility) as $p\to-\infty$. When the number of items is large, we show that this many-item fair-division problem is captured exactly by a single-item prophet problem evaluated by the $p$-mean of agents' expected utilities. We characterize this single-item problem: every online rule is weakly Pareto dominated by a quantile-threshold rule, and an optimal egalitarian rule equalizes agents' expected utilities. We prove that for every $n$, the online optimum is at least $\Gamma\approx0.7059$ times the prophet's egalitarian welfare; by monotonicity of generalized means, the same guarantee holds for every $p\le1$. Further, for egalitarian welfare, the optimal ratio converges to $\Gamma$ as $n\to\infty$. Thus, asymptotically, optimizing egalitarian rather than utilitarian welfare costs only about four percentage points relative to the classical utilitarian ratio of $0.7451$. Finally, when $m=n$, the worst-case competitive ratio converges to zero as $n\to\infty$ for every $p\le0$, showing that the large-item assumption is necessary. Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-09-23 in cs.GT). Categorie arXiv: Computer Science and Game Theory (cs.GT). Pagina del lavoro: https://arxiv.org/abs/2609.25424 — 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-08T13:54:10.267Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-09-23?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).