Metraipolis › archive › dc_621898759d01
Moment Ambiguity and the Limits of Robust Stochastic Optimization — arXiv:2609.31090
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.31090
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-08T02:07:58.746Z
- SHA-256 of the archived text
ee68326f78e3dcd6c155683c49a02e156b104d0bc6681a7dcbf343ec6298aee1- Stable URL of this page
https://metraipolis.com/documento/dc_621898759d01
How to cite
Moment Ambiguity and the Limits of Robust Stochastic Optimization — arXiv:2609.31090 — arXiv (en), https://arxiv.org/abs/2609.31090 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_621898759d01 (Metraipolis archive dc_621898759d01, sha256 ee68326f78e3dcd6c155683c49a02e156b104d0bc6681a7dcbf343ec6298aee1)
BibTeX
@misc{dc621898759d01,
title = {Moment Ambiguity and the Limits of Robust Stochastic Optimization — arXiv:2609.31090},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.31090},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_621898759d01; sha256 ee68326f78e3dcd6c155683c49a02e156b104d0bc6681a7dcbf343ec6298aee1},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.31090. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study fundamental information-theoretic limits of robust stochastic optimization when the distribution is known only through its exact moment sequence. We develop a unified framework that produces families of distinct distributions sharing all moments yet inducing radically different optimal decisions, thereby establishing strong impossibility results for a range of decision problems under moment ambiguity. Our approach gives two explicit constructions: a binary and an $N$-way construction showing that distributions with identical moment sequences can nevertheless exhibit arbitrarily different quantiles, order-statistics and threshold regions, forcing incompatible optimal actions. These families of distributions yield, in fact, strong impossibility results across several stochastic optimization problems. First, for the newsvendor problem, moment equivalence causes quantile ambiguity, inducing any fixed or randomized order quantity to fail arbitrarily badly. Second, for revenue maximization, no deterministic or randomized posted pricing scheme can secure a nontrivial approximation relative to the full-information benchmark. Third, for the secretary with cardinal observations setting, the worst-case robust value over all exact moment disclosures is exactly the classical $1/e$ finite-horizon value as opposed to the celebrated result of $0.58$ success probability with full-information by Gilbert and Mosteller (J. Am. Stat. Assoc., 1966). We also recover and expand upon the recent impossibility result of Correa et al. (STOC, 2026) for prophet inequalities with moment knowledge. Indeed, exact moment knowledge can yield at best a $\Theta(1/\log n)$ competitive ratio, even when competing against relaxed benchmarks based on expected $r$-th order statistics or when the algorithm is allowed to select $r$ items. Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-09-28 in cs.GT). Categorie arXiv: Information Theory (cs.IT) ; Data Structures and Algorithms (cs.DS); Computer Science and Game Theory (cs.GT); Optimization and Control (math.OC). Pagina del lavoro: https://arxiv.org/abs/2609.31090 — 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-08T01:41:24.863Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-09-28?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).