Operations Research

Motivation

Nisan and Ronen's Algorithmic Mechanism Design (Games and Economic Behavior 35, 2001) asks how well a computational task can be carried out when its inputs are held by self-interested agents who may lie about them. Their test case is scheduling on unrelated machines: tasks must be assigned to agents (machines), each agent privately knows how long it needs for each task, and the planner wants to minimize the time at which the last agent finishes. The paper shows that the mechanism MinWork, which gives each task to the fastest agent and pays it the second-fastest time, is truthful and loses a factor of at most $n$ against the optimum, and that no truthful mechanism can do better than a factor $2$. It then conjectures (Conjecture 4.9) that the factor $n$ cannot be improved by any truthful mechanism.

That conjecture became the Nisan–Ronen conjecture, one of the central questions of algorithmic mechanism design. A sequence of papers raised the general lower bound from $2$ to $1 + \sqrt 2$ (Christodoulou, Koutsoupias and Vidali), to $1 + \varphi \approx 2.618$ (Koutsoupias and Vidali) and to larger constants, and Christodoulou, Koutsoupias and Kovács (STOC 2023) finally proved the conjecture for all deterministic truthful mechanisms. In the original paper, Nisan and Ronen confirm the conjecture for two restricted classes of mechanisms, with short direct arguments. This mission concerns the second class, local mechanisms (Theorem 4.12).

Setting

There are $k$ tasks $j \in \{1, \dots, k\}$ and $n$ agents $i \in \{1, \dots, n\}$. A type vector $t$ records, for every agent $i$ and task $j$, the positive time $t^i_j$ agent $i$ needs for task $j$. An allocation $x$ assigns every task to one agent; $x^i$ is the set of tasks of agent $i$. For a set $X$ of tasks write $t^i(X) = \sum_{j \in X} t^i_j$. The make-span of $x$ is $g(x, t) = \max_i t^i(x^i)$.

A direct mechanism $(x, p)$ asks every agent for its type, computes an allocation $x(t)$ from the declarations, and hands agent $i$ the payment $p^i(t)$. Agent $i$'s utility is $p^i(t) - t^i(x^i(t))$ measured with its true times. The mechanism is truthful if declaring the true type maximizes each agent's utility whatever the other agents declare. The allocation rule is a $c$-approximation if $g(x(t), t) \le c \cdot g(y, t)$ for every type vector $t$ and every allocation $y$.

For a truthful mechanism the payment to agent $i$ depends only on the set it receives and on the declarations $t^{-i}$ of the others (Proposition 4.4). This gives the price offered to agent $i$ for a set $X$ (Definition 12):

A mechanism is local (Definition 14) if $p^i(X, t^{-i})$ depends only on the other agents' times $\{t^l_j : l \ne i, j \in X\}$ on the tasks of $X$. MinWork is local: its price for $X$ is $\sum_{j \in X} \min_{l \ne i} t^l_j$.

Formalization targets

Goal: Theorem 4.12

For every $n \ge 1$, every $k \ge n^2$ and every real $c < n$, no truthful local mechanism is a $c$-approximation:

The bound holds for every $c < n$, so together with MinWork it shows that $n$ is the exact best ratio for local truthful mechanisms.

Milestones

1. Proposition 4.4 (Independence). Payments depend only on the allocated set and on $t^{-i}$.
2. Proposition 4.5 (Maximization). $x^i(t)$ maximizes $p^i(X, t^{-i}) - t^i(X)$ over the sets $X$ that agent $i$ can obtain.
3. Lemma 4.13. Every type vector has type vectors arbitrarily close to it at which each agent's maximizing set is unique.
4. Claim 4.14, first step. If $x^i(t)$ is the unique maximizer, lowering agent $i$'s times on $x^i(t)$ keeps $x^i(t)$.
5. Ratio step. An allocation that gives one agent $n$ tasks of time about $1$, while every other agent's own tasks are nearly free, has make-span about $n$, while splitting those $n$ tasks gives make-span about $1$.

Significance

The result. Theorem 4.12 settles the Nisan–Ronen conjecture for a natural class of mechanisms. Locality captures the mechanisms in which the price for a bundle of tasks is set only by the competition for those tasks. It includes MinWork and, more generally, every mechanism that prices tasks separately using the other agents' bids on them. The theorem says that for this class the trivial per-task auction is already optimal, so any improvement over the ratio $n$ must use prices that depend on the other agents' times on tasks outside the bundle.

Formalizing it. The statement is not open: it follows from the 2023 proof of the Nisan–Ronen conjecture, and Nisan and Ronen's own argument is much shorter. That argument is a sketch, though. Lemma 4.13 rests on an informal measure-theoretic appeal, and the core claim relies on a maximization property stated over all sets of tasks. A machine-checked proof pins down exactly which properties of truthful mechanisms the short argument needs. None of these results is known to have been formalized. The definitions (type vectors, truthful mechanisms, prices, locality) are shared with the other missions of this series.

Difficulty

An argument that looks at one agent at a time does not go through. Changing one agent's declaration changes the prices offered to every other agent, so an allocation that is stable for one agent can shift for another. The argument needs a type vector at which every agent's choice is strict, and only then can it lower times agent by agent and follow the allocation. Producing such a type vector is Lemma 4.13. The printed argument for it applies a "for almost every type vector" statement to sets defined by the price functions of an arbitrary mechanism, which need not be measurable. A proof must therefore work without any regularity of the mechanism. A second difficulty is Definition 12's convention that a set the agent cannot obtain has price $0$. Locality constrains these zero prices too, and the argument has to account for sets that are obtainable at one type vector and not at a nearby one.

Formalization scope

Agents are Fin n, tasks Fin k. An allocation is a function Fin k → Fin n, a type vector is Fin n → Fin k → ℝ, and a mechanism is a pair of functions alloc (declarations to allocation) and pay (declarations to the payment handed to each agent). Utilities are quasi-linear. All types, declarations and misreports are positive, and every truthfulness, locality and approximation quantifier ranges over positive type vectors. The make-span is a Finset.sup' over the nonempty set of agents ([NeZero n]).

Conventions and explicit thresholds:

• $k \ge n^2$. The theorem is printed without a bound on the number of tasks, and its proof begins "Let $k \ge n^2$". The goal carries $k \ge n^2$ as a hypothesis.
• Truthfulness is assumed. §4.3 assumes throughout that the mechanism is truthful (by the revelation principle this is no loss). The goal quantifies over all truthful local mechanisms.
• Prices use Definition 12 literally, including the value $0$ for sets the agent cannot obtain, and locality is Definition 14 applied to that price function over all sets $X$, not only single tasks. When several declarations give the same set, the price uses one chosen witness; by Proposition 4.4 the choice does not matter for truthful mechanisms.
• Proposition 4.5 is stated over the sets the agent can obtain. As printed, over all subsets, it is false for a truthful mechanism that never leaves an agent idle and pays it negative amounts. Uniqueness of maximizers (Lemma 4.13, Claim 4.14) refers to the same family.
• Lemma 4.13 uses Mathlib's norm on Fin n → Fin k → ℝ, the sup norm. No measurability of the mechanism is assumed.
• Claim 4.14 is printed at $t^i_j = 1$ with $0 < \varepsilon < 1$. The first step is stated at any type vector, with $0 < \varepsilon \le t^i_j$ on the lowered tasks.
• Running time and computability are out of scope.

Ruled-out trivializations: locality is not restricted to single tasks; the goal does not assume that maximizers are unique at every type vector (that is Lemma 4.13's conclusion at one point, not a hypothesis); and the bound holds for every $c < n$, not for some.

Needed infrastructure: finite sums over allocation fibres, sup norms on function spaces, and a genericity argument for finitely many affine functions (Lemma 4.13). The model file and the price and locality definitions are reusable in the other missions of the series. Proofs of individual milestones are welcome independently.

Selected references

• N. Nisan, A. Ronen, Algorithmic Mechanism Design, Games and Economic Behavior 35 (2001) 166–196. https://doi.org/10.1006/game.1999.0790
• A. Mas-Colell, M. D. Whinston, J. R. Green, Microeconomic Theory, Oxford University Press, 1995 (pp. 876–880, basic properties of truthful mechanisms).
• G. Christodoulou, E. Koutsoupias, A. Vidali, A lower bound for scheduling mechanisms, Algorithmica 55 (2009).
• E. Koutsoupias, A. Vidali, A lower bound of 1+φ for truthful scheduling mechanisms, Algorithmica 66 (2013).
• G. Christodoulou, E. Koutsoupias, A. Kovács, A proof of the Nisan–Ronen conjecture, STOC 2023.

Motivation

Algorithms deployed on the Internet often take their inputs from parties who own them and who may lie when lying pays. Nisan and Ronen's Algorithmic Mechanism Design (Games and Economic Behavior 35, 2001) proposed studying optimization problems in this setting: the algorithm designer may hand out payments, and must guarantee that the intended output is produced when every participant acts in its own interest. The paper's central test case is scheduling on unrelated machines, a standard problem of combinatorial optimization, in which the machines are the selfish participants and only they know how long each job takes them.

For this problem the paper shows that incentives cost a factor of two at least: with two or more machines, no mechanism can guarantee a make-span below twice the optimum. This was the first lower bound separating what incentive-compatible mechanisms can achieve from what ordinary approximation algorithms can achieve, and it started a line of work on the "Nisan–Ronen conjecture" (that the right factor for $n$ machines is $n$), with improved lower bounds by Christodoulou, Koutsoupias and Vidali (Algorithmica, 2009) and by Koutsoupias and Vidali (Algorithmica, 2013), and a resolution announced by Christodoulou, Koutsoupias and Kovács (STOC 2023).

Setting

There are $n$ agents (machines) $i = 1,\dots,n$ and $k$ tasks $j = 1,\dots,k$. Agent $i$'s private type is the vector $t^i = (t^i_1,\dots,t^i_k)$ of positive real numbers, $t^i_j$ being the time agent $i$ needs for task $j$; a type vector is $t = (t^1,\dots,t^n)$. An allocation $x$ assigns every task to one agent; $x^i$ is the set of tasks given to agent $i$. For a set $X$ of tasks write $t^i(X) = \sum_{j\in X} t^i_j$. The objective is the make-span

and an allocation rule is a $c$-approximation if its make-span is at most $c$ times that of every allocation, on every type vector.

A mechanism $m = (o,p)$ gives each agent $i$ a set $A^i$ of strategies. On a strategy profile $a = (a^1,\dots,a^n)$ it outputs an allocation $o(a)$ and hands agent $i$ a payment $p^i(a)$. An agent of type $t^i$ has utility $p^i(a) - t^i(o^i(a))$. A strategy is dominant if it maximizes the agent's utility whatever the others play. The mechanism implements a $c$-approximation if every agent of every type has a dominant strategy and every profile of dominant strategies yields a $c$-approximate allocation.

A direct mechanism $(x,p)$ has $A^i$ equal to the set of types, and is truthful if reporting the true type is dominant. For a truthful mechanism, the price $p^i(X,t^{-i})$ is the payment agent $i$ receives when, against the others' reports $t^{-i}$, some report of its own makes it receive exactly $X$ (and $0$ if none does); the price difference is $\Delta^i(A,B) = p^i(A\cup B,t^{-i}) - p^i(A,t^{-i})$.

Formalization targets

Goal: Theorem 4.6

For every $n\ge 2$, $k\ge3$ and $c<2$, no mechanism with any strategy sets implements a $c$-approximation:

Milestones

1. Proposition 2.1 (revelation principle): a mechanism implementing a $c$-approximation yields a truthful direct mechanism whose allocation rule is a $c$-approximation.
2. Theorem 4.6 for truthful mechanisms (§4.3): no truthful direct mechanism has a $c$-approximate allocation rule for $c<2$. With milestone 1 it gives the goal.
3. Proposition 4.4 (independence): for a truthful mechanism, $t_1^{-i}=t_2^{-i}$ and $x^i(t_1)=x^i(t_2)$ imply $p^i(t_1)=p^i(t_2)$.
4. Proposition 4.5 (maximization): $x^i(t)$ maximizes $p^i(X,t^{-i}) - t^i(X)$ over attainable $X$.
5. Lemma 4.7: the price-difference inequalities satisfied by $x^i(t)$, and the uniqueness statement for sets satisfying them strictly.
6. Claim 4.8: for two agents, all-ones types and $0<\varepsilon<1$, moving agent 1's times to $\varepsilon$ on its own bundle and $1+\varepsilon$ elsewhere leaves the allocation unchanged.
7. The even case of the ratio: at that perturbed instance the mechanism's make-span is $|x^2(t)|$ while some allocation achieves $\tfrac12|x^2(t)| + k\varepsilon$.

Significance

The result. Theorem 4.6 shows that the requirement of dominant-strategy incentive compatibility, by itself, rules out approximation ratios below $2$ for scheduling on unrelated machines, a problem for which polynomial-time $2$-approximation algorithms that ignore incentives exist (Lenstra, Shmoys, Tardos 1990) and for which the exact optimum is computable in exponential time. Combined with the MinWork mechanism of the same paper (an $n$-approximation), it determines the optimal ratio for two machines. It is the base case of the Nisan–Ronen conjecture and the prototype of the "characterize truthful mechanisms by prices" technique used throughout later work on the conjecture.

Formalizing it. The theorem has been proved since 1999, but no machine-checked version is known to exist. The mission produces a formal account of general mechanisms with arbitrary strategy sets, dominant-strategy implementation, the revelation principle in that generality, and the price characterization of truthful mechanisms (independence and maximization). These are reusable for every other lower bound in this paper and for the later literature on the conjecture.

Difficulty

The statement quantifies over all mechanisms, with arbitrary strategy sets and arbitrary payment functions, so no finite search settles it. The revelation principle reduces to truthful direct mechanisms, but even these are an infinite-dimensional family: the allocation rule may break ties in any way, and prices may be any functions of the other agents' reports.

The printed argument also has two places that need care. Proposition 4.5 and Lemma 4.7, as printed, range over all sets of tasks, while Definition 12 gives unattainable sets price $0$; the statements hold only over attainable sets, and are formalized that way. And the case where agent 2's bundle has odd size is dispatched in one sentence ("which still yields the same allocation"), which the preceding lemma does not justify when agent 2's best bundle at the perturbed prices is not unique. A complete formal proof of the goal must supply an argument for that case.

Formalization scope

• Agents are Fin n, tasks Fin k; an allocation is a function Fin k → Fin n; bundles may be empty. The make-span is a finite maximum and assumes $n\ge1$ (NeZero n).
• Types, declarations and misreports are strictly positive reals throughout (Definition 10). Utility is quasi-linear; payments are handed to the agent and may have either sign.
• A general mechanism has strategy sets A : Fin n → Type u (any universe), output $o$ and payments $p$ on dependent strategy profiles. Implements requires both that every agent of every positive type has a dominant strategy and that every profile of dominant strategies yields a $c$-approximate allocation. Dominance is against every profile of the others, not only dominant ones. Without the existence clause, a mechanism with no dominant strategies would implement vacuously; the definition excludes that.
• Thresholds made explicit: $n\ge2$ and $k\ge3$, both taken from the proof ("We prove the theorem for the case of two agents"; "Let $k\ge3$"). The goal holds for each fixed $n$ and $k$ and every $c<2$, for every mechanism, with no restriction on tie-breaking and no requirement of strong truthfulness. At $n=1$ the claim is false.
• Proposition 2.1 is stated for task scheduling with the $c$-approximation specification; "truthful implementation" is read as truth-telling dominant and the truthful output $c$-approximate.
• Printed slips: Proposition 4.5 and Lemma 4.7 are stated over attainable sets; the "Moreover" of Lemma 4.7 requires $Y$ attainable. The odd case of the ratio step is not a milestone.
• The reduction from $n>2$ to two agents ("having the other agents be much slower") is not a separate milestone; the goal covers every $n\ge2$.
• Running time ("polynomial-time computable") is out of scope and not modelled.

Contributions of any of the milestones are welcome, as are alternative proofs of the goal that avoid the terse odd case.

Selected references

• N. Nisan, A. Ronen, Algorithmic Mechanism Design, Games and Economic Behavior 35 (2001) 166–196. https://doi.org/10.1006/game.1999.0790
• A. Mas-Colell, M. D. Whinston, J. R. Green, Microeconomic Theory, Oxford University Press, 1995 (revelation principle, p. 871).
• J. K. Lenstra, D. B. Shmoys, É. Tardos, Approximation algorithms for scheduling unrelated parallel machines, Mathematical Programming 46 (1990) 259–271. https://doi.org/10.1007/BF01585745
• G. Christodoulou, E. Koutsoupias, A. Vidali, A lower bound for scheduling mechanisms, Algorithmica 55 (2009).
• E. Koutsoupias, A. Vidali, A lower bound of 1+φ for truthful scheduling mechanisms, Algorithmica 66 (2013).
• G. Christodoulou, E. Koutsoupias, A. Kovács, A proof of the Nisan–Ronen conjecture, STOC 2023.

Motivation

This mission continues chapter 10's algorithmic account across its remaining two sections: finishing the Iwata-Fleischer-Fujishige fixing algorithm for submodular minimization (§10.2.3's tail), the steepest descent algorithm for L-convex function minimization (§10.3), and — the capstone of chapter 10's account of the M-convex submodular flow problem (§10.4) — conjugate scaling, the operation that finally makes the primal-dual algorithm run in polynomial time. As in mission 34-ch10b-algorithms, most of this block's numbered results are asymptotic complexity bounds; this mission places the results that are ordinary mathematical propositions.

Setting

The IFF fixing algorithm (mission 34-ch10b-algorithms) builds an acyclic graph D=(U,F) and partition Z,H,Γ certifying the maximal minimizer of a submodular ρ once η≤0 (Eq. (10.26)); this mission places the case-independent inequality its own legitimacy rests on, and restates its correctness conclusion. The steepest descent algorithm for an L-convex function g repeatedly minimizes the submodular set function ρ_p(X)=g(p+χ_X)-g(p) and moves to p+χ_X for its minimal minimizer X (the tie-breaking rule (10.33)); this mission places the resulting monotonicity fact and a domain-size bound for the L$^\natural$-convex adaptation. Conjugate scaling replaces a dual-integral M-convex function's conjugate g with g_α(p)=g(αp)/α, defining f⟨α⟩ via the resulting sup-formula (Eq. (10.77)) — a scaling operation compatible with M-convexity where the naive ⌈f(·)/α⌉ is not.

Formalization targets

Goal: Conjugate scaling preserves M-convexity (Proposition 10.41)

For a dual-integral polyhedral M-convex function f (represented as the mixed real-primal/ integer-dual conjugate of an L$^\natural$-convex g), the conjugate scaling f⟨α⟩ is again dual-integral M-convex, witnessed by g_α itself being L$^\natural$-convex, provided f⟨α⟩>-∞. Chosen as goal: this is the fact the whole conjugate scaling algorithm — chapter 10's final and most refined algorithm for the M-convex submodular flow problem — depends on, and the book's own text singles it out as the "compatible scaling operation" that makes M-convex cost scaling work where a naive approach provably does not.

Supporting structural targets

Proposition 10.26 (the case-independent inequality underlying the IFF fixing algorithm's own legitimacy) and Proposition 10.28 (that algorithm's correctness conclusion) close out mission 34-ch10b-algorithms's coverage of §10.2.3. Proposition 10.30 gives the steepest descent algorithm's monotonicity property under its tie-breaking rule; Proposition 10.32 (found by direct reading) bounds the L$^\natural$-convex adaptation's domain-size parameter in terms of the original function's.

Significance

Conjugate scaling is chapter 10's demonstration that M-convexity, while a combinatorial rather than a numeric-magnitude notion, still admits a genuine scaling technique compatible with its own structure — completing the book's account of the M-convex submodular flow problem with an algorithm whose polynomial running time depends on exactly this compatibility. Propositions 10.26/10.28 complete the correctness/legitimacy argument for the strongly polynomial submodular- minimization algorithm mission 34-ch10b-algorithms began placing, and Propositions 10.30/10.32 are the analogous structural facts for L-convex function minimization, chapter 10's third major algorithmic thread.

None of these results are open — they are Murota's own account of submodular-function- minimization (§10.2 continued), L-convex minimization (§10.3), and conjugate scaling (§10.4.5). What this mission contributes is a faithful, machine-checked formal statement of each, including one result (Proposition 10.32) the platform's own automated extractor missed; no comparable formalization exists on the platform (see Formalization scope).

Difficulty

As in mission 34-ch10b-algorithms, several numbered results in this block are excluded as hard for being pure algorithmic-complexity bounds (Propositions 10.25, 10.27, 10.31); see HARD.md. A further three (Propositions 10.37-10.39, on the primal-dual algorithm's maximum submodular flow subproblem) are excluded for a distinct reason: the source text's own OCR extraction demonstrably cannot distinguish the two visually different capacity-bound symbols (c* overlined vs. underlined) central to their shared defining formula, confirmed directly against the raw extracted bytes, making faithful reconstruction of that formula impossible from the available text; see HARD.md.

Formalization scope

Ground-set elements are a Fintype V with DecidableEq. All apparatus needed for Propositions 10.26/10.28 (Submodular, GammaSet, RhoTilde, ReachSet, Eta, IsMaximalMinimizer) is redeclared fresh from mission 34-ch10b-algorithms, genericized over an arbitrary ground type where the original was V-specific, since this draft cannot import that sibling. Proposition 10.26 is placed as the case-independent core inequality its own proof establishes, rather than by replicating the three-case verification against Proposition 10.24's own internal proof objects (Cases (i)-(iii)); see HARD.md. Proposition 10.30 omits its own trailing iteration-count corollary (a pure complexity bound); see HARD.md. Six numbered results (Propositions 10.25, 10.27, 10.31, 10.37, 10.38, 10.39) are hard. Contributions completing any of the five sorrys are welcome; the goal carries the most independent proof content (via the conjugacy theorem and Theorem 7.10(2), both established elsewhere in this series).

Selected references

• K. Murota, Discrete Convex Analysis, SIAM, 2003. DOI: 10.1137/1.9780898718508.
• S. Iwata, "A faster scaling algorithm for minimizing submodular functions," SIAM Journal on Computing, 32 (2003), pp. 833-840 [99] (conjugate scaling's origin).
• A. Frank, "A weighted matroid intersection algorithm," Journal of Algorithms, 2 (1981), pp. 328-336 [55] (the primal-dual framework this mission's Proposition 10.28 continues, via mission 34-ch10b-algorithms's own Proposition 10.24).

Motivation

In the capacitated vehicle routing problem (CVRP) a fleet of $m$ vehicles of capacity $Q$ leaves a depot and serves $n$ customers; every customer is visited once, and the load of each route must not exceed $Q$. In practice customer demands are uncertain at planning time. The chance-constrained CVRP asks that each route respect the capacity with probability at least $1-\epsilon$, but this presupposes a known demand distribution, which is rarely available. Ghosal and Wiesemann (Oper. Res. 68(3), 2020) require the chance constraints to hold for every distribution in an ambiguity set $\mathcal P$ built from the information that can actually be estimated: support, means and dispersion bounds.

Their branch-and-cut method separates rounded capacity inequalities whose right-hand side is the worst-case value-at-risk of the total demand of a customer set $S$. This quantity is evaluated thousands of times during the search, so it matters whether it has a closed form or a small convex reformulation. This mission concerns the paper's covariance ambiguity sets (§5.2), which bound the whole covariance matrix of the demands and can therefore express that demands of nearby customers are correlated, as happens with geographically clustered demand. The covariance bound can be derived from data, for example analytically through McDiarmid's inequality (Delage and Ye, 2010) or by bootstrapping.

Setting

Customers are indexed by $i\in\{1,\dots,n\}$ and their random demand vector is $\tilde{\boldsymbol q}\in\mathbb R^n$. Fix a box $\mathcal Q=[\underline{\boldsymbol q},\overline{\boldsymbol q}]$ with $\underline{\boldsymbol q}\ge\mathbf 0$, a mean vector $\boldsymbol\mu$ in the interior of $\mathcal Q$, and a symmetric positive definite matrix $\Sigma\succ0$. The covariance ambiguity set is

where $\mathcal P_0(\mathbb R^n)$ is the set of all probability distributions on $\mathbb R^n$ and $A\preceq\Sigma$ means that $\Sigma-A$ is positive semidefinite.

For a distribution $\mathbb P$ and a real random variable $\tilde X$, the value-at-risk at level $1-\epsilon$, $\epsilon\in(0,1)$, is $\mathbb P\text{-VaR}_{1-\epsilon}[\tilde X]=\inf\{x\in\mathbb R:\mathbb P[\tilde X\le x]\ge1-\epsilon\}$. For a customer set $S$, the worst-case value-at-risk is $\sup_{\mathbb P\in\mathcal P}\mathbb P\text{-VaR}_{1-\epsilon}[\sum_{i\in S}\tilde q_i]$. A route serving $S$ satisfies the chance constraint for every $\mathbb P\in\mathcal P$ exactly when this number is at most $Q$.

Two componentwise bounds appear in the answer:

A route set is an ordered partition of the customers into $m$ nonempty ordered routes. It is feasible in the distributionally robust problem RVRP($\mathcal P$) if every route satisfies the chance constraint for every $\mathbb P\in\mathcal P$, and feasible in a deterministic instance with capacity $Q'$ and demands $\boldsymbol q$ if every route's total demand is at most $Q'$.

Formalization targets

Goal: Theorem 7

For every customer set $S$,

The right-hand side maximizes an affine function over the intersection of an ellipsoid and a box.

Milestone: Corollary 4 (corrected)

For a diagonal bound $\Sigma=\operatorname{diag}(\sigma_1^2,\dots,\sigma_n^2)$, program (17) collapses to a search over one parameter $\theta\ge0$ with $S(\theta)=\{i\in S:\sigma_i^2>\theta q^u_i\}$:

over the $\theta$ for which the first bracket is nonnegative and the point of (17) that $\theta$ induces respects $\boldsymbol q^u$ (see Formalization scope).

Milestone: Theorem 6

For some instance with the ambiguity set (16), no deterministic CVRP instance on the same customers and fleet has the same set of feasible route sets.

Significance

Theorem 7 makes the worst-case value-at-risk over (16) computable in polynomial time as a convex quadratically constrained program. With it, the rounded capacity inequalities of the two-index vehicle flow formulation can be separated for covariance information. Theorem 2 of the same paper shows that the resulting demand estimator is subadditive, so this formulation is exact. Corollary 4 gives a closed form for the diagonal case, which the paper uses to evaluate the estimator in time linear in $|S|$ after sorting. Theorem 6 explains why the paper needs this machinery: the robust feasible region cannot be reproduced by any deterministic demand vector and capacity.

The results are proved in the paper's online supplement. No part of them is formalized anywhere to our knowledge; the platform has no worst-case value-at-risk and no moment-based ambiguity set. A complete development would give machine-checked worst-case VaR bounds over moment sets with second-order information. These are used well beyond routing, in distributionally robust portfolio and inventory models.

Difficulty

The supremum ranges over an infinite-dimensional set of distributions, while (17) ranges over vectors. The inequality "$\ge$" requires, for every feasible $\boldsymbol q$ of (17), a sequence of distributions in (16) whose value-at-risk approaches $\mathbf 1_S^\top(\boldsymbol\mu+\boldsymbol q)$. The value-at-risk is a lower quantile, so a distribution placing mass exactly $\epsilon$ on a high point does not attain the value: the construction has to be a limit. The inequality "$\le$" is harder. It must rule out every distribution, not only two-point ones, and a bound through the one-dimensional Chebyshev–Cantelli inequality for $\sum_{i\in S}\tilde q_i$ alone ignores the box: it yields $\sqrt{\frac{1-\epsilon}{\epsilon}\mathbf 1_S^\top\Sigma\mathbf 1_S}$, which is too large whenever the support bounds bind. The interaction between the Loewner constraint and the componentwise support bounds, which produces the unusual bound $\boldsymbol q^\ell$, is where the work lies. For Theorem 6 the difficulty is to exhibit the instance and to evaluate enough chance constraints exactly.

Formalization scope

Customers are Fin n (0-based) and demand vectors are Fin n → ℝ. Distributions are measures on Fin n → ℝ. The set (16) is covarianceSet qlo qhi μ Sig: a probability measure with P (Set.Icc qlo qhi) = 1, coordinate means μ, and Sig - M positive semidefinite, where M is the matrix of integrals $\int(q_i-\mu_i)(q_j-\mu_j)\,d\mathbb P$. The covariance bound is called Sig because Σ is Lean syntax. The side conditions $\underline{\boldsymbol q}\ge\mathbf 0$, $\boldsymbol\mu\in\operatorname{int}\mathcal Q$, $\Sigma\succ0$ (Sig.PosDef) and $0<\epsilon<1$ are hypotheses of every theorem. The value-at-risk is the published MultistageStochastic.valueAtRisk P Y (1 - ε). The worst-case value-at-risk is a real sSup over the image of the set. That image is nonempty (the Dirac measure at $\boldsymbol\mu$ lies in (16)) and bounded (the box), so the supremum is genuine. "The optimal objective value" of a maximization is stated as a supremum; attainment is not part of any claim. $\Sigma^{-1}$ is Mathlib's matrix inverse.

The paper states Theorem 7 and Corollary 4 with "$\mathbb P$-VaR" without a level; the level $1-\epsilon$, used in the sentence introducing Theorem 7 and everywhere else, is read in. Corollary 4 as printed is false. It maximizes over every $\theta\ge0$ with a nonnegative bracket. For $n=1$, every large $\theta$ then gives the value $\mu_1+\sigma_1\sqrt{(1-\epsilon)/\epsilon}$, which can exceed $\overline q_1$ and hence every value-at-risk. The formal statement adds the condition that makes each $\theta$ a feasible point of (17): $\sigma_i^2\sqrt{s(\theta)}\le q^u_i\sqrt{\sum_{k\in S\setminus S(\theta)}\sigma_k^2}$ for $i\in S\setminus S(\theta)$, where $s(\theta)$ is the first bracket. With this condition the statement is the diagonal case of Theorem 7.

A theorem about the Lean set is trivial if the set is empty or the supremum is a junk value. Neither happens here, and replacing the Loewner constraint by a scalar variance bound on $\sum_{i\in S}\tilde q_i$ would state a different theorem. The dual second-order cone program printed after Theorem 7 is not a target: as printed it has the all-ones vector where Lagrangian duality gives $\mathbf 1_S$, and it has no multiplier for $\boldsymbol q\ge\boldsymbol q^\ell$.

Needed infrastructure: quantiles of pushforward measures, the Loewner order on moment matrices, and finite-support (two-point) distributions. The value-at-risk lemmas and the moment-matrix lemmas are reusable beyond this mission, and contributions of either kind are welcome. Theorem 6 needs only the route-set layer defined here and one explicit instance.

Selected references

• S. Ghosal and W. Wiesemann, The Distributionally Robust Chance-Constrained Vehicle Routing Problem, Operations Research 68(3):716–732, 2020. https://doi.org/10.1287/opre.2019.1924
• E. Delage and Y. Ye, Distributionally Robust Optimization Under Moment Uncertainty with Application to Data-Driven Problems, Operations Research 58(3):595–612, 2010. https://doi.org/10.1287/opre.1090.0741
• S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004. https://doi.org/10.1017/CBO9780511804441
• G. Laporte, Y. Nobert and M. Desrochers, Optimal Routing under Capacity and Distance Restrictions, Operations Research 33(5):1050–1073, 1985. https://doi.org/10.1287/opre.33.5.1050

Motivation

In the capacitated vehicle routing problem (CVRP) a depot serves customers $V_C=\{1,\dots,n\}$ with $m$ vehicles of capacity $Q$, and every route must respect the capacity. When customer demands are uncertain, the distributionally robust chance-constrained CVRP of Ghosal and Wiesemann (Oper. Res. 68(3), 2020) requires every route to meet its capacity with probability at least $1-\epsilon$ under every distribution in an ambiguity set $\mathcal P$, a family of distributions consistent with what is known about the demands. Such constraints are handled in a branch-and-cut scheme through rounded capacity inequalities, whose right-hand sides require one quantity for each customer subset $S$: the worst-case value-at-risk of the cumulative demand of $S$.

For ambiguity sets that describe each customer separately (marginal moment sets), this quantity is additive over customers and the problem reduces to a deterministic CVRP. Such sets cannot express that the demands of customers in the same municipality, county or state vary jointly within limits. The first-order generic moment ambiguity set does express this: it bounds the mean absolute deviation of the cumulative demand of prescribed customer groups. The mean absolute deviation is a standard robust dispersion measure, less sensitive to outliers than the standard deviation (see Casella and Berger, Statistical Inference, 2002). This mission formalizes the paper's description of the worst-case value-at-risk over such sets.

Setting

Demands form a random vector $\tilde{\boldsymbol q}$ on $\mathbb R^n$. The data are a support box $\mathcal Q=[\underline{\boldsymbol q},\overline{\boldsymbol q}]$ with $\underline{\boldsymbol q}\ge\mathbf 0$, a mean vector $\boldsymbol\mu$ in the interior of $\mathcal Q$, customer subsets $S_1,\dots,S_p\subseteq V_C$ and bounds $\boldsymbol\nu>\mathbf 0$. For $A\subseteq V_C$, $\mathbf 1_A\in\{0,1\}^n$ is its indicator vector. The first-order generic moment ambiguity set, Eq. (12) of the paper, is

where $\mathcal P_0(\mathbb R^n)$ is the set of probability distributions on $\mathbb R^n$ and $|\cdot|$ acts componentwise. The subsets are arbitrary: they may overlap and need not cover $V_C$.

For a risk level $\epsilon\in(0,1)$ and a random variable $\tilde X$, the value-at-risk is $\mathbb P\text{-VaR}_{1-\epsilon}[\tilde X]=\inf\{x\in\mathbb R:\mathbb P[\tilde X\le x]\ge1-\epsilon\}$. For a customer subset $S$ the quantity of interest is

Write $\hat{\boldsymbol q}=\min\{\overline{\boldsymbol q}-\boldsymbol\mu,\ \frac{1-\epsilon}{\epsilon}(\boldsymbol\mu-\underline{\boldsymbol q})\}$ (componentwise) and $[\cdot]_+$ for the componentwise positive part. A route set $\mathbf R=(\mathbf R_1,\dots,\mathbf R_m)$ partitions $V_C$ into $m$ nonempty ordered routes. It is feasible in the deterministic CVRP with demands $\boldsymbol q$ if $\sum_{i\in\mathbf R_k}q_i\le Q$ for all $k$, and feasible in the distributionally robust CVRP if $\mathbb P[\sum_{i\in\mathbf R_k}\tilde q_i\le Q]\ge1-\epsilon$ for all $\mathbb P\in\mathcal P$ and all $k$.

Formalization targets

Goal: Theorem 5 (p. 726)

For every customer subset $S$,

The right-hand side is the optimal value of the paper's problem (13). The statement holds for every family of subsets and all data satisfying the standing assumptions, so it is the general form of which the milestones are special cases.

Corollary 2 (p. 726, Eq. (14))

If $S_1,\dots,S_{p-1}$ are pairwise disjoint and cover $V_C$ and $S_p=V_C$, then

Corollary 3 (pp. 726–727, Eq. (15))

If $p=n+1$, $S_i=\{i\}$ for $i\le n$ and $S_{n+1}=V_C$, then

Theorem 4 (p. 726)

For some instance with an ambiguity set of the form (12), no deterministic CVRP instance on the same customers and vehicles (capacity $Q'\ge0$, demands $\boldsymbol q'\ge\mathbf 0$) has the same set of feasible route sets.

Significance

Theorem 5 makes the worst-case value-at-risk over (12) computable in polynomial time as the value of a nonsmooth convex problem over the nonnegative orthant, which the paper notes can be written as a linear program. This gives the right-hand sides of the rounded capacity inequalities in a branch-and-cut scheme for the distributionally robust CVRP. Corollaries 2 and 3 give closed forms for two structured families of groups, evaluable in time linear in $|S|$. Theorem 4 shows the gain in modelling power has a cost: unlike the marginal case, the problem cannot in general be replaced by a deterministic CVRP with altered demands. With a single customer and $S_1=\{1\}$, Theorem 5 reduces to the closed form $\mu+\min\{\hat q,\nu/(2\epsilon)\}$ for marginalized first-order sets, so it extends that single-customer formula to joint dispersion constraints.

All four results are proved in the paper's online supplement. As far as a platform search shows, none has been machine-checked. The mission produces checked proofs of the equality in Theorem 5, the two closed forms, and an explicit instance for Theorem 4.

Difficulty

The supremum ranges over an infinite-dimensional set of joint distributions, and the value-at-risk is neither convex nor concave in the distribution. Bounding the value-at-risk of each group separately and adding the bounds does not work when groups overlap, and it ignores the total-dispersion constraint. It gives only an upper bound, and in the setting of Corollary 2 that bound is strict whenever the total bound $\nu_p/(2\epsilon)$ is the binding term. Showing that the infimum in (13) is attained in the limit needs distributions that saturate several overlapping dispersion constraints at once while keeping the mean fixed and the support inside the box. For Theorem 4, the witness must separate the feasible-route-set family of the robust instance from every family defined by a single linear capacity inequality with nonnegative weights.

Formalization scope

Customers are Fin n (0-based), subsets are Sfam : Fin p → Finset (Fin n), and a distribution is a Measure (Fin n → ℝ) that is required to be a probability measure. Support is P (Set.Icc qlo qhi) = 1, the mean condition is ∫ q, q j ∂P = μ j, and the dispersion condition is ∫ q, ∑ j ∈ Sfam l, |q j - μ j| ∂P ≤ ν l. The integrability clauses stated alongside are automatic for measures carried by the box. The value-at-risk is the published MultistageStochastic.valueAtRisk P Y (1 - ε). The worst-case value-at-risk is the real sSup of its image over the set; under the standing assumptions this image is nonempty (the Dirac at $\boldsymbol\mu$ lies in the set) and bounded (bounded support), so the real supremum is the paper's. The optimal value of (13) is the real sInf of the objective over $\{\boldsymbol\gamma\ge\mathbf 0\}$, a nonempty set on which the objective is bounded below by $\mathbf 1_S^\top\boldsymbol\mu$. Attainment is not claimed. All statements carry the standing assumptions $\underline{\boldsymbol q}\ge\mathbf 0$, $\underline{\boldsymbol q}<\boldsymbol\mu<\overline{\boldsymbol q}$, $\boldsymbol\nu>\mathbf 0$ and $0<\epsilon<1$. Corollary 2 writes $p=r+1$ with the last subset Sfam (Fin.last r). Corollary 3 indexes the singleton of customer $i$ by Fin.castSucc i. In Theorem 4 route sets are Fin m → List (Fin n) and only feasibility is modelled; costs play no role.

The theorems are not trivialized by an empty ambiguity set or a junk supremum: membership of the Dirac distribution at $\boldsymbol\mu$ is checked locally with a sorry-free proof. Theorem 4 needs a genuinely separating instance: an instance in which no route set is robustly feasible, for example, is matched by a deterministic instance in which none is feasible either.

Needed infrastructure: two-point and finitely supported distributions on $\mathbb R^n$ and their value-at-risk; weak duality for moment problems over the box; the positive-part calculus of (13). The value-at-risk lemmas for finitely supported measures are reusable in the sibling missions on this paper. Contributions of any of the milestones, of lemmas for these building blocks, or of either inequality of Theorem 5 on its own are welcome.

Selected references

• S. Ghosal and W. Wiesemann, The Distributionally Robust Chance-Constrained Vehicle Routing Problem, Operations Research 68(3):716–732, 2020. https://doi.org/10.1287/opre.2019.1924
• G. Casella and R. L. Berger, Statistical Inference, 2nd ed., Duxbury, 2002.
• S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004. https://doi.org/10.1017/CBO9780511804441
• G. Laporte, Y. Nobert and M. Desrochers, Optimal routing under capacity and distance restrictions, Operations Research 33(5):1050–1073, 1985. https://doi.org/10.1287/opre.33.5.1050

Motivation

The capacitated vehicle routing problem (CVRP) assigns customers to a fleet of $m$ identical vehicles of capacity $Q$ and orders each vehicle's visits so as to minimize transportation cost, subject to each vehicle's total load not exceeding $Q$. In practice the customers' demands are not known when the routes are planned. Two classical responses are the robust CVRP, which requires feasibility for every demand vector in an uncertainty set, and the chance-constrained CVRP, which requires each capacity constraint to hold with probability at least $1-\epsilon$ under a known demand distribution. The first ignores all distributional information; the second assumes a distribution that is rarely known and usually requires independent demands.

Ghosal and Wiesemann (Oper. Res. 68(3), 2020) study the distributionally robust chance-constrained CVRP, RVRP($\mathcal P$), in which each capacity constraint must hold with probability at least $1-\epsilon$ under every distribution of an ambiguity set $\mathcal P$. Whether this problem can be solved with existing CVRP technology depends on how the worst-case value-at-risk of a customer set's total demand behaves as a set function. This mission formalizes §4 of the paper, which treats ambiguity sets that only constrain each customer's demand separately.

Setting

There are $n$ customers $V_C=\{1,\dots,n\}$ with random demand vector $\tilde{\boldsymbol q}\in\mathbb R^n$ and a risk level $\epsilon\in(0,1)$. For a probability distribution $\mathbb P$ and a real random variable $\tilde X$, the value-at-risk is

For an ambiguity set $\mathcal P$ and a customer subset $S$, the worst-case value-at-risk of $S$ is $\sup_{\mathbb P\in\mathcal P}\mathbb P\text{-VaR}_{1-\epsilon}[\sum_{i\in S}\tilde q_i]$.

Fix a support box $\mathcal Q=[\underline{\boldsymbol q},\overline{\boldsymbol q}]$ with $\underline{\boldsymbol q}\ge\mathbf 0$, a mean vector $\boldsymbol\mu$ in the interior of $\mathcal Q$, and for each customer $i$ a componentwise convex dispersion measure $\boldsymbol\varphi_i:\mathbb R\to\mathbb R^{p_i}$ with bound $\boldsymbol\sigma_i>\boldsymbol\varphi_i(\mu_i)$. The marginalized moment ambiguity set (5) is

It constrains marginal moments only, and so contains joint distributions of every dependence structure, from independent to perfectly correlated demands. Three special cases have their own closed forms: the first-order set (6), where $\sigma_i>0$ bounds the mean absolute deviation $\mathbb E|\tilde q_i-\mu_i|$; the variance set (8), where $\sigma_i>0$ bounds $\mathbb E(\tilde q_i-\mu_i)^2$; and the semivariance set (10), where $\sigma_i^+,\sigma_i^->0$ bound $\mathbb E[\tilde q_i-\mu_i]_+^2$ and $\mathbb E[\mu_i-\tilde q_i]_+^2$.

A route set $\mathbf R=(R_1,\dots,R_m)\in\mathfrak P(V_C,m)$ partitions the customers into $m$ nonempty ordered routes. It is feasible in RVRP($\mathcal P$) if $\mathbb P[\sum_{i\in R_k}\tilde q_i\le Q]\ge1-\epsilon$ for all $\mathbb P\in\mathcal P$ and all $k$, and feasible in the deterministic CVRP with demands $\boldsymbol q$ if $\sum_{i\in R_k}q_i\le Q$ for all $k$.

Formalization targets

Goal: Theorem 3 (p. 723)

For every marginalized moment ambiguity set (5) and every nonempty $S\subseteq V_C$,

The dispersion measures are left arbitrary (convex, componentwise, any number of components), so the goal covers every set of the form (5).

Milestones

• Proposition 2 (p. 724, Eq. (7)), first-order sets: $\sup_{\mathbb P}\mathbb P\text{-VaR}_{1-\epsilon}[\tilde q_i]=\mu_i+\min\{\overline q_i-\mu_i,\frac{1-\epsilon}{\epsilon}(\mu_i-\underline q_i),\frac1{2\epsilon}\sigma_i\}$.
• Proposition 3 (p. 725, Eq. (9)), variance sets: the same with last term $\sqrt{\frac{1-\epsilon}{\epsilon}\sigma_i}$.
• Proposition 4 (p. 725, Eq. (11)), semivariance sets: the four-term minimum with $\sqrt{\sigma_i^+/\epsilon}$ and $\sqrt{(1-\epsilon)\sigma_i^-}/\epsilon$.
• Corollary 1 (p. 723): a route set is feasible in RVRP($\mathcal P$) over (5) if and only if it is feasible in the deterministic CVRP with demands $q_i=\sup_{\mathbb P\in\mathcal P}\mathbb P\text{-VaR}_{1-\epsilon}[\tilde q_i]$.

Significance

Theorem 3 says that over (5) the worst case of a sum is the sum of the worst cases. Because the value-at-risk is not additive for a fixed distribution, and the online supplement exhibits distributions in such a set for which the individual values-at-risk are not additive, the statement is about the ambiguity set, not about any of its members. Its consequence, Corollary 1, is that RVRP($\mathcal P$) over (5) is a deterministic CVRP with inflated demands, so existing branch-and-cut and branch-and-cut-and-price codes solve it unchanged. Propositions 2–4 make those inflated demands explicit for three standard dispersion measures, so that the whole reduction is in closed form. The corollary also exposes a limitation: under (5) the worst-case distribution does not depend on the route set, and the model cannot represent known dependencies between customers.

The results are proved in the paper's online supplement; none has a machine-checked proof. A formalization produces a checked worst-case value-at-risk calculus over moment sets with support constraints, including sharp one-sided Chebyshev-type bounds under mean-absolute-deviation, variance and semivariance constraints, which are reusable in distributionally robust optimization beyond vehicle routing.

Difficulty

The value-at-risk is neither subadditive nor superadditive in general, so neither inequality of Theorem 3 follows from properties of a single distribution. The inequality "$\ge$" requires combining near-worst-case distributions of the individual customers into one joint distribution in $\mathcal P$ that is simultaneously near-worst for the sum; the inequality "$\le$" requires bounding the value-at-risk of the sum for an arbitrary joint law using only marginal information. In Propositions 2–4 the supremum is typically not attained: the distribution concentrating mass at the claimed worst-case value violates the mean constraint, and the value is reached only as a limit of distributions in $\mathcal P$. An argument that exhibits a single maximizer therefore fails, and the statements must be proved as equalities of suprema.

Formalization scope

Customers are Fin n (0-based) and demand vectors are Fin n → ℝ. An ambiguity set is a set of measures on Fin n → ℝ, each required to be a probability measure; the support condition is P (Set.Icc qlo qhi) = 1 and expectations are Bochner integrals. The sets are sets of joint laws on $\mathbb R^n$, never products of marginals. In (5) each expectation $\mathbb E_{\mathbb P}[\varphi_{i,l}(\tilde q_i)]$ is required to exist; this is automatic for convex $\varphi_{i,l}$ on the bounded support. The value-at-risk is the published definition MultistageStochastic.valueAtRisk P Y (1 - ε), and the worst-case value-at-risk is the real supremum of its values over the ambiguity set; under the standing assumptions that set of values is nonempty (the Dirac law at $\boldsymbol\mu$ belongs to $\mathcal P$) and bounded (by the support), so the supremum is not a default value. The single-customer quantity is the case $S=\{i\}$. The standing assumptions ($\underline{\boldsymbol q}\ge\mathbf 0$, $\underline{\boldsymbol q}<\boldsymbol\mu<\overline{\boldsymbol q}$, convexity of $\varphi_{i,l}$, $\varphi_{i,l}(\mu_i)<\sigma_{i,l}$, $\boldsymbol\sigma,\boldsymbol\sigma^\pm>\mathbf 0$, $0<\epsilon<1$) are explicit hypotheses. Routes are lists of customers; a route set has nonempty routes whose concatenation is a permutation of all customers. Costs are not formalized, since both routing problems minimize the same cost over their feasible route sets.

All targets are equalities or equivalences; a one-sided inequality, a statement asserting that some distribution attains the value, or a formulation over product measures is a different theorem and does not count.

Contributions welcome: the reduction of the chance constraint to a value-at-risk bound, the right-continuity lemmas for the value-at-risk of a measure on $\mathbb R^n$, two-point constructions in the ambiguity sets, and one-sided Chebyshev-type bounds with support constraints.

Selected references

• S. Ghosal and W. Wiesemann, The Distributionally Robust Chance-Constrained Vehicle Routing Problem, Operations Research 68(3):716–732, 2020. https://doi.org/10.1287/opre.2019.1924
• G. Laporte, Y. Nobert and M. Desrochers, Optimal routing under capacity and distance restrictions, Operations Research 33(5):1050–1073, 1985. https://doi.org/10.1287/opre.33.5.1050
• G. Casella and R. L. Berger, Statistical Inference, 2nd ed., Duxbury, 2002.

Motivation

The capacitated vehicle routing problem (CVRP) asks for a set of minimum-cost routes by which a fleet of identical vehicles of capacity $Q$, based at a depot, serves every customer exactly once without any vehicle carrying more than its capacity. In practice customer demands are not known when routes are planned. Ghosal and Wiesemann (Oper. Res. 68(3), 2020) study the distributionally robust CVRP: the demand vector $\tilde{\boldsymbol q}$ is random, its distribution is known only to lie in an ambiguity set $\mathcal P$, and every route must respect its capacity with probability at least $1-\epsilon$ under every distribution in $\mathcal P$.

Exact CVRP solvers rely on compact two-index vehicle flow formulations strengthened by rounded capacity inequalities, which bound from below the number of vehicles entering any customer subset $S$ by a demand estimator $d(S)$. The paper shows (its Theorem 1) that the robust two-index formulation is exact whenever the demand estimator is subadditive and demands are nonnegative, and that this fails for some natural ambiguity sets: sets that fix the marginal distribution of each customer's demand violate it (Example 1). This mission formalizes the paper's positive result for the most widely used class of ambiguity sets, the moment ambiguity sets of distributionally robust optimization (see El Ghaoui et al. 2003, Delage and Ye 2010, Wiesemann et al. 2014).

Setting

There are $n$ customers, indexed $i=1,\dots,n$; the demand vector is $\tilde{\boldsymbol q}\in\mathbb R^n$. Fix

• a rectangular support $\mathcal Q=[\underline{\boldsymbol q},\overline{\boldsymbol q}]$ with $\underline{\boldsymbol q}\ge\mathbf 0$;
• a mean vector $\boldsymbol\mu\in\mathbb R^n$;
• a dispersion measure $\boldsymbol\varphi=(\varphi_1,\dots,\varphi_p):\mathbb R^n\to\mathbb R^p$ (for example mean absolute deviations $|q_i-\mu_i|$, variances $(q_i-\mu_i)^2$ or Huber losses) and bounds $\boldsymbol\sigma\in\mathbb R^p$.

The moment ambiguity set is

where $\mathcal P_0(\mathbb R^n)$ denotes all probability distributions on $\mathbb R^n$. The paper's standing assumptions are $\boldsymbol\mu\in\operatorname{int}\mathcal Q$, each $\varphi_l$ closed and convex, and $\boldsymbol\varphi(\boldsymbol\mu)<\boldsymbol\sigma$.