Moment Ambiguity and the Limits of Robust Stochastic Optimization

1.1 Our Contributions and Technical Summary

• A binary separator creates quantile and order-statistic gaps, while an N-way family creates many alternative thresholds and designated values for pricing and secretary selection.The N-way construction uses disjoint residue classes and a common nonnegative coefficient sequence with explicit bounds on its profile.Source: §1.1 · pp. 2–3
• Exact moment information can leave quantiles undetermined even approximately, with separations affecting risk, chance-constrained capacity, and fixed or randomized newsvendor decisions.The paper also rules out positive uniform approximation factors for deterministic and randomized posted prices.Source: §1.1 · p. 3
• In the cardinal-value random-order secretary problem, the robust optimal success probability equals the classical finite-horizon value and converges to 1/e.For prophet inequalities, the binary separator supports an order-statistic gap behind the fixed-r barriers.Source: §1.1 · p. 3

1.2 Related Work

• The paper distinguishes its moment-equivalence limitation from prior prophet and pricing bounds, and contrasts its secretary result with known-distribution benchmarks.It relates its discrete constructions to earlier Stieltjes classes while presenting a one-sided grid with explicit bounds.Source: §1.2 · pp. 4–5

1.3 Organization

• The paper proceeds from notation and constructions to quantile and newsvendor, pricing, secretary, and prophet applications, then technical proofs and concluding remarks.Source: §1.3 · p. 5

2.2 Background on Mechanism Design and Stochastic Optimization Problems

• The preliminaries define the CDF and its open-at-x counterpart, decreasing order statistics, Value-at-Risk as a quantile, and lower-tail average quantiles.They also specify that discrete support sets need not be closed.Source: §2 · p. 5, §2.2 · p. 5

2.1 Background on Moment Ambiguity

• Distributions agree on all moments when all finite moments exist and match; a Stieltjes-type class contains multiple distributions, and this paper focuses on subclasses with quantitatively separated supports, atoms, and threshold regions.A moment-based policy uses disclosed moments and online observations, so identical moment sequences provide identical ex ante information.Source: §2.1 · p. 5

2.2 Background on Mechanism Design and Stochastic Optimization Problems

• The newsvendor chooses an order quantity for nonnegative demand, while posted-price revenue depends on a buyer's value; randomized ordering rules are also defined.Randomization can matter under ambiguity because one moment disclosure may fit multiple distributions.Source: §2.2 · p. 6
• The secretary model has independent nonnegative values arriving in random order, with labels and values observed; its robust guarantee ranges over compatible distributions and moment profiles.For prophet inequalities, the classical benchmark is the expected maximum, with the expected r-th largest value also considered for fixed r; the finite-horizon secretary value converges to 1/e.Source: §2.2 · p. 6

3 A Residue-Class Moment-Matching Framework

• The N-way family is needed when randomized policies may spread their actions across many disjoint decision regions.The binary pair suffices for two-instance separations.Source: §3 · p. 7, §3.2 · p. 8
• Infinite-support constructions must preserve cancellation while ensuring summable weights, a positive normalization, finite moments of every order, and quantitative control of designated atoms and tails.The analytic estimates are deferred to Section 8.Source: §3 · p. 7

3.1 The Binary Construction

• On k fixed nodes, alternating-sign Vandermonde null vectors yield two distinct probability distributions on disjoint supports that match moments through degree k−2.Matching through degree k−1 would force distributions on the same k points to be identical.Source: §3.1 · pp. 7–8
• A rapidly separated infinite support gives disjoint-support probability distributions with finite moments of every order that agree on all moments.Their weights and normalization also provide quantitative bounds on atom masses and tails.Source: §3.1 · p. 8
• The binary pair places almost all of ν's mass at 1 and almost all of µ's mass at B, while ν also places 1/Θ(n) mass at nB.These controlled atoms and the small remaining tail support quantile and order-statistic separations.Source: §3.1 · p. 8

3.2 N-Way Residue-Class Construction

• Roots of unity make the moment sums of N residue classes coincide, producing N disjointly supported probability distributions with finite moments of every order and identical moments.A common normalizing constant W lies in [1, 4).Source: §3.2 · p. 9

4 Quantile Ambiguity: VaR, Chance Constraints, and Newsvendor

• Moment-equivalent distributions can have quantiles separated by arbitrary multiplicative factors, and robust capacity may consequently exceed the distribution-specific minimum by at least B.A rule feasible across the moment class at service level β must choose capacity at least B.Source: §4 · pp. 9–10
• For every stated β range, the binary separator provides moment-equivalent laws with quantiles B and 1, enabling the capacity separation.The cited corollary applies for β ∈[1/2, 1) and B ≥3.Source: §4 · pp. 9–10

4.1 Newsvendor Problem

• The binary separator makes optimal newsvendor order quantities and profits differ by arbitrary multiplicative factors despite agreement on all moments.The construction uses a hidden critical quantile to establish the newsvendor lower bound.Source: §4 · p. 9, §4.1 · p. 11
• Randomized ordering cannot avoid the newsvendor lower bound: its expected profit is bounded by the deterministic order at its mean, while the constructed pair yields arbitrarily bad performance.Concavity of profit and Jensen’s inequality provide the mean-order bound; Figure 3 depicts the incompatible mean order quantities.Source: §4.1 · pp. 11–12, Figure 3 · p. 12
• The binary separator targets one hidden critical quantile, whereas posted pricing uses an N-way construction to hide many disjoint threshold regions.The N-way construction is presented as addressing randomized pricing rules.Source: §4.1 · p. 12

5.1 Deterministic Posted Prices

• Theorem 5.1 uses a binary separator pair so every deterministic price performs poorly on at least one of two moment-equivalent distributions.The proof divides prices into cases based on their relation to the distributions’ support and atom at B.Source: §5.1 · p. 13
• The binary construction alone does not rule out randomized pricing: mixing the two distribution-specific good prices can achieve a constant factor for that pair.The N-way construction addresses this by creating many disjoint good-price regions under identical moment disclosures.Source: §5.1 · p. 13

5.2 Randomized Posted Prices

• Theorem 5.2 uses moment-equivalent distributions to make some good-price interval receive at most 1/N of any randomized pricing strategy’s probability mass.The proof combines this small mass with an off-interval revenue bound to obtain an adversarial distribution.Source: §5.2 · pp. 14–15
• Unlike the many-scale lower bound of Babaioff et al. and the construction of Giannakopoulos, Poças, and Tsigonias-Dimitriadis, this finite family agrees on every moment.The related constructions use unrelated value distributions or a hard family whose higher moments vary.Source: §5.2 · p. 15

6 Selection Ambiguity: The Secretary Problem

• The N-way construction concentrates each residue-class distribution near its designated value while preserving a common moment sequence, enabling hard secretary instances under one disclosure.The construction’s concentration approaches one as B grows.Source: §6 · pp. 15–16
• A finite Ramsey argument finds a subgrid where a policy’s stopping behavior depends on relative value order rather than grid locations, up to an arbitrarily small success-probability loss.The proof quantizes stopping probabilities and bounds the loss by mδ before using classical secretary optimality.Source: §6 · pp. 16–17
• The optimal robust success probability at horizon m is exactly sm, the classical finite-horizon value, and it converges to 1/e.With full distributional information, the finite-horizon value converges to roughly 0.5801.Source: §6 · pp. 15, 17
• A classical skip-then-record rule guarantees at least sm even with moment-based information, because conditional on realized values it selects the lexicographic maximum with probability sm.Independent continuous tie-breakers make the selected item one of the value maximizers.Source: §6 · p. 17

7 Order-Statistic Ambiguity: Prophet Inequalities

• The binary-separator order-statistic gap applies for each fixed r, and Correa et al.’s hard instances can also be adapted to fixed order statistics.Each active block contains many copies of its designated value with high probability.Source: §7 · p. 18
• The upper bound arranges binary-separator instances in doubling-size blocks and varies the switch point from ν-blocks to µ-blocks while preserving the disclosed moments.A policy must allocate stopping probability across blocks without learning the switch point from the moment disclosures.Source: §7 · p. 19, Figure 5 · p. 19
• For algorithms selecting at most r values and receiving their total value, some instance has expected reward at most rbr log m times E[Z(r)].The proof reduces multi-selection to a randomized single-choice policy by choosing a uniformly random selection rank.Source: §7 · pp. 20–21

8 Proofs of Key Results

• The technical section develops the limiting construction of the binary separator.Source: §8 · p. 21
• Coefficient-decay estimates establish that all moments in the construction are finite.Source: §8 · p. 21
• The section also proves the analogous analytic estimates for the N-way residue-class separator.Source: §8 · p. 21

8.1 Proof of the Binary Separator

• The distributions μ and ν agree on all moments, all of which are finite; at B and nB, their point probabilities exhibit contrasting exact zero and lower-bound values.At B, p1 = Pν(X = B) = 0 and q1 = Pμ(Y = B) ≥ 1 − 1/(n^2B^2); at nB, p2 = Pν(X = nB) ≥ 1/(4n) and q2 = Pμ(Y = nB) = 0.Source: §8.1 · pp. 21–22

8.1.1 Constructing Distributions Agreeing on Finitely Many Moments

• For each finite K, the construction yields two distributions with disjoint supports that match moments through order K + 1.The measures are defined on the same finite set of nodes, with their probabilities assigned to alternating indices.Source: §8.1.1 · p. 23

8.1.2 Extending to Infinity

• Taking K to infinity produces limiting measures whose normalized weights converge to finite, nonzero limits.The resulting measures are defined on the countable node set and match moments of every order.Source: §8.1.2 · pp. 23–24, §8.1.3 · p. 27

8.1.3 Estimating Decay Rates for Limiting Weights

• Decay bounds on the limiting weights make the probability measures well-defined and establish finite, equal moments of every order.The proof also derives bounds on probabilities at selected support points.Source: §8.1.3 · pp. 26–28

8.1.4 Finishing the Proof

• The theorem follows by applying the limiting-measure and probability bounds to the constructed pair.The proof identifies the theorem’s stated support-probability bounds with those established in Lemma 8.6.Source: §8.1.4 · p. 29

8.2.1 Structural Properties of the Construction

• The N-way construction uses equal residue-class sums Wh(t) = GN(B^t), with a common normalizing constant W between 1 and 4.The residue-class identities establish the structural basis for measures with matching moments.Source: §8.2.1 · p. 32

8.2.2 Estimating Decay Rates of Limiting Weights

• The limiting coefficients satisfy B^-e(j) ≤ wj ≤ 2^jB^-e(j), and j − e(j) reaches N − 1 only for j from N − 1 through 2N − 2.Source: §8.2.2 · p. 34

8.2 Proof of the N-Way Separator

• The separator’s N distributions are formed on residue-class supports and have identical moment sequences.The proof combines the common residue-class normalization with the moment-equality result.Source: §8.2.3 · p. 35

8.2.3 Finishing the Proof

• The final construction gives probability measures on residue-class supports that match all moments, with weights bounded in terms of B and e(j).For each j, B^-e(j) ≤ wj ≤ 2^jB^-e(j).Source: §8.2.2 · p. 34, §8.2.3 · p. 35

• Quantiles can differ by arbitrarily large factors across distributions with the same full moment sequence, affecting Value-at-Risk, lower-tail average quantiles, capacity constraints, and newsvendor decisions.Source: §9 · p. 35
• Distributions with identical moments can have disjoint ranges of nearly optimal posted prices.Source: §9 · p. 35
• The N-way construction and a Ramsey argument remove the robust advantage of cardinal observations in the secretary problem, while the binary construction creates the order-statistic gap behind fixed-r prophet barriers.Source: §9 · p. 35