Moment ambiguity prevents reliable decisions in stochastic optimization
Moment Ambiguity and the Limits of Robust Stochastic Optimization
Information TheoryData Structures and AlgorithmsComputer Science and Game Theory
Summary
When you only know certain average values (moments) about a situation but not the full details, it can be impossible to make good decisions. The authors show that many very different scenarios can share these average values but lead to wildly different best choices. This means common decision problems, like stocking items to sell or setting prices, can fail badly if they rely only on this limited information. Their work also explains why some classic decision strategies don’t work well without full knowledge of the situation.
What this means in practice
- •For inventory managers: Avoid depending solely on moment-based estimates when deciding order quantities, as identical summary statistics can cause costly errors.
- •For pricing strategists: Recognize that pricing rules based only on moment information cannot guarantee good revenue, highlighting the need for richer data.
A theory result. No direct application yet.
Authors
Andrés Cristi, Matteo Russo, Jiechen Zhang
Abstract
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 $Θ(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.