Optimization

Motivation

A retailer often knows more about her own demand than the supplier who must produce for her. In a decentralized supply chain the supplier sets a production quantity before demand is realized, and an under-informed supplier produces too little or too much. The retailer can shape what the supplier believes by committing in advance to a disclosure policy, a rule that maps what she knows to messages she sends. This is the Bayesian persuasion or information design framework of Kamenica and Gentzkow (2011), applied by Candogan and Gurkan (2024) to a newsvendor supplier.

The natural expectation is that the retailer either tells the supplier everything or nothing. The paper shows the answer depends on the supplier's critical ratio, and that it can be non-monotone. For nested demand supports (the setting of the first missions in this series) partial disclosure appears for low critical ratios. This mission formalizes the paper's §4 extension to supports that overlap without being nested. There, under an explicit condition on the supports, the optimal policy moves from partial disclosure to no disclosure to full disclosure as the critical ratio rises.

Setting

The state is $\omega\in\{0,1\}$ with prior $p_0=\mathbb P(\omega=0)\in[0,1]$. In state $\omega$ the retailer's demand $D_\omega$ is uniform on $[a_\omega,b_\omega]$. The supports intersect:

$$b_0>b_1>a_0>a_1\ge 0 .$$

Write $\delta_u=b_0-b_1$, $\delta_d=a_0-a_1$, $\delta_{\mathsf{IS}}=b_1-a_0$; all three are positive.

The supplier holds a belief $p=\mathbb P(\omega=0)$ and chooses a quantity $Q\ge 0$ that minimizes the newsvendor cost (2),

$$p\,\mathbb E\big[\xi(D_0-Q)^+ + (1-\xi)(Q-D_0)^+\big]+(1-p)\,\mathbb E\big[\xi(D_1-Q)^+ + (1-\xi)(Q-D_1)^+\big],$$

where $\xi=C_s/(C_s+C_e)\in(0,1)$ is the critical ratio of the shortage cost $C_s$ and the excess cost $C_e$. A best-response profile $Q^*$ assigns an optimal quantity $Q^*_p$ to every belief $p\in[0,1]$.

A policy $\Gamma=(\mathcal M,\pi)$ consists of a finite message space $\mathcal M$ and probabilities $\pi(m\mid\omega)$. After message $m$ the supplier's belief is the Bayes posterior (1),

$$p_m=\frac{\pi(m\mid 0)\,p_0}{\pi(m\mid 0)\,p_0+\pi(m\mid 1)(1-p_0)} .$$

The retailer orders the realized demand and bears only the shortage. Her design problem (3) minimizes, over policies $\Gamma$ and best-response profiles $Q^*$, the expected shortage

$$\mathbb E\Big[p(D_0-Q^*_p)^+ + (1-p)(D_1-Q^*_p)^+\ \Big|\ \Gamma\Big],$$

where $p$ is the induced posterior. Full disclosure reveals $\omega$. No disclosure sends one uninformative message. The function

$$K_{\mathsf{IS}}(p)=p\,\mathbb E[(D_0-Q^*_p)^+]+(1-p)\,\mathbb E[(D_1-Q^*_p)^+]$$

of (B.1) is the retailer's cost when the posterior is $p$, and $\kappa_{\mathsf{IS}}$ denotes its lower convex envelope on $[0,1]$.

Formalization targets

Goal: Proposition 3 (p. 15)

Assume $\delta_d>2\delta_u$ and $\delta_{\mathsf{IS}}>\max\big(\delta_d-2\delta_u,\ \delta_d\delta_u/(\delta_d-2\delta_u)\big)$. Let $\breve\xi=(\delta_d-2\delta_u)/(\delta_d-\delta_u)$ and $\underline\tau_{\mathsf{IS}}(p)=(1-p)(a_0-a_1)/(b_1-a_1)$. Then:

$$\begin{aligned} \xi\in[\breve\xi,1) &\implies \text{full disclosure is optimal},\\ \xi\in[\underline\tau_{\mathsf{IS}}(p_0),\breve\xi) &\implies \text{no disclosure is optimal},\\ \xi\in(0,\underline\tau_{\mathsf{IS}}(p_0)) &\implies \Gamma^*_{\mathsf{IS}} \text{ of (7) is optimal}, \end{aligned}$$

where $\Gamma^*_{\mathsf{IS}}$ has two messages, sends $m_0$ in state $0$ with probability 1, and sends $m_0$ in state $1$ with probability $\frac{\xi(b_1-a_1)}{(a_0-a_1)-\xi(b_1-a_1)}\cdot\frac{p_0}{1-p_0}$.

Milestones (the paper's proof, App. C.1)

1. Proposition 2 (p. 15): the supplier's optimal quantity $Q^*_p$ is unique and given by the three-branch formula (6), with thresholds $\underline\tau_{\mathsf{IS}}(p)\le\bar\tau_{\mathsf{IS}}(p)=1-p(b_0-b_1)/(b_0-a_0)$.
2. (B.2) (p. 25): the optimal value of (3) is $\kappa_{\mathsf{IS}}(p_0)$, the Kamenica–Gentzkow reduction.
3. Equivalence of hypotheses (p. 32): the hypotheses of Proposition 3 hold if and only if $\bar\tau_{\mathsf{IS}}(1)>\breve\xi>\underline\tau_{\mathsf{IS}}(0)$.
4. $K_{\mathsf{IS}}$ in closed form (pp. 32–33), in the three regimes of (6).
5. Lemma 2 (p. 31): $\kappa_{\mathsf{IS}}$ is the chord $(1-p)K_{\mathsf{IS}}(0)+pK_{\mathsf{IS}}(1)$ for $\xi\ge\breve\xi$; it is $K_{\mathsf{IS}}$ itself for $\xi\in[\underline\tau_{\mathsf{IS}}(0),\breve\xi)$; and for smaller $\xi$ it is $K_{\mathsf{IS}}$ above $\breve p=1-\xi(b_1-a_1)/(a_0-a_1)$ and the chord from $0$ to $\breve p$ below.
6. The posteriors of $\Gamma^*_{\mathsf{IS}}$ (p. 32): $m_0$ has probability $p_0/\breve p$ and induces posterior $\breve p$, while $m_1$ induces posterior $0$.

Significance

The result. With nested supports, more information can only hurt the retailer at low critical ratios. With overlapping supports, Proposition 3 shows the regimes of full, no and partial disclosure can occur in a different order. It also gives a sufficient condition on the shape of the supports for that pattern. Together with the paper's Theorem 1 (nested) and Theorem 3 (disjoint), it gives the optimal policy for the main configurations of two uniform supports. The explicit thresholds tell a practitioner which disclosure regime applies from four interval endpoints and a cost ratio.

Formalizing it. The paper's argument is in its Online Appendix (C.1, pp. 30–35). It cites Kamenica–Gentzkow for the value of the design problem and proves the envelope lemma through second-derivative sign computations. None of this is machine-checked. A complete development yields a formal concavification theorem for a finite-state persuasion problem over all finite message spaces, which is reusable well beyond this paper. It also yields a checked closed form for the newsvendor quantile under a two-uniform mixture. The goal and every milestone are open on the platform; only the published convex-envelope definition is reused.

Difficulty

The obvious argument compares full disclosure, no disclosure and one candidate partial policy, and picks the best of the three. That proves nothing, because optimality is claimed against every policy on every finite message space. The reduction to the convex envelope (milestone 2) is what makes the comparison finite, and it is itself a theorem about splitting a prior into posteriors.

The envelope of $K_{\mathsf{IS}}$ is the second obstacle. $K_{\mathsf{IS}}$ is piecewise rational in $p$, with two regime boundaries that move with $p$. Its curvature changes sign across the boundaries, and the sign of its second derivative depends on $\xi$ relative to $\breve\xi$. Verifying that the claimed $\kappa_{\mathsf{IS}}$ is convex at the kink $\breve p$ requires a one-sided slope inequality whose sign rests on the hypotheses on $\delta_d,\delta_u,\delta_{\mathsf{IS}}$. The equivalence of milestone 3 is where those hypotheses enter.

Formalization scope

All objects live in the namespace SCInfoDesign.Intersecting. States are Fin 2; $\omega=0$ is the state with demand on $[a_0,b_0]$, and beliefs are always $\mathbb P(\omega=0)$. The uniform expectation is $\frac{1}{b-a}\int_a^b$. Policies are stochastic maps from Fin 2 to any finite type; the paper does not bound the message space, and finite spaces are the standard Kamenica–Gentzkow setting. The supplier's cost is normalized by $C_s+C_e$, which leaves its minimizers unchanged, so $\xi\in(0,1)$ is the only cost parameter. A message of probability zero carries the default posterior $0$ and weight $0$. No disclosure is the one-message policy. $K_{\mathsf{IS}}$ uses the largest optimal quantity, which is the unique one here. The envelope is the published BiconvexProg.BranchBound.convexEnvelope on $[0,1]$.

Standing assumptions, added and disclosed because the paper uses them implicitly: $0<\xi<1$; $a_1\ge 0$ (nonnegative demand, so the constraint $Q\ge 0$ never binds); $p_0\in[0,1]$. Nondegeneracy $a_\omega<b_\omega$ follows from the support ordering. Two printed slips are corrected in the statements and quoted as printed in the milestones: $b_h$ for $b_0$ in the $K_{\mathsf{IS}}$ display, and the label $m_1$ for $m_0$ on p. 32. The overlapping indicators of (C.2) at $p=\breve p$ are read piecewise.

Trivializing encodings are excluded. Optimality is over all finite policies and all best-response profiles, not over the three named policies. The supplier's response is an argmin of (2), never the closed form (6), which is a milestone. Each named policy is also asserted to be a policy.

Contributions are welcome on any milestone. The concavification theorem (milestone 2) and the uniform-mixture newsvendor quantile (milestone 1) are the reusable pieces. Proposition 5 (shift case) and the second-derivative display (C.3) are not posed here.

Selected references

• O. Candogan, H. Gurkan, The Value of Information Design in Supply Chain Management, Management Science, 2024. https://doi.org/10.1287/mnsc.2023.03004 (statements cited from the SSRN preprint, abstract 4378997, https://ssrn.com/abstract=4378997)
• E. Kamenica, M. Gentzkow, Bayesian Persuasion, American Economic Review 101(6), 2590–2615, 2011. https://doi.org/10.1257/aer.101.6.2590
• F. A. Al-Khayyal, J. E. Falk, Jointly Constrained Biconvex Programming, Mathematics of Operations Research 8(2), 273–286, 1983 (source of the published convex-envelope definition). https://doi.org/10.1287/moor.8.2.273

Motivation

A retailer usually knows more about her future demand than the supplier who has to produce for her. If the supplier must commit to a production quantity before the order arrives, the retailer bears the cost of every unit he fails to produce. She cannot pay him or contract on quantities, but she can decide how much of her demand information to share, and she can commit to that disclosure rule in advance. Which information should she share?

Candogan and Gurkan (Management Science, 2024; preprint SSRN 4378997) answer this question in a two-state model with uniform demand, using the Bayesian persuasion framework of Kamenica and Gentzkow (2011). Their main text treats nested demand supports. This mission formalizes their extension to disjoint supports, where the high-demand state's support lies entirely above the low-demand state's (Theorem 3). It is the fourth of four missions on the paper; the others cover nested supports (Theorem 1), the value of information (Theorem 2) and intersecting supports (Proposition 3).

Setting

There are two states $\omega\in\{0,1\}$ with prior $p_0=\mathbb P(\omega=0)\in[0,1]$. In state $i$ the retailer's demand is $D_i\sim U[a_i,b_i]$ with $a_i<b_i$ and $a_i\ge0$. Here the supports are disjoint, $b_1<a_0$, so state $0$ is the high-demand state.

A disclosure policy $\Gamma=(\pi,\mathcal M)$ is a finite message space $\mathcal M$ and, for each state $\omega$, a probability distribution $\pi(\cdot\mid\omega)$ on $\mathcal M$. The retailer commits to $\Gamma$, observes $\omega$, and sends a message $m\sim\pi(\cdot\mid\omega)$. Message $m$ has probability $\mathbb P(m)=p_0\pi(m\mid0)+(1-p_0)\pi(m\mid1)$, and the supplier's posterior is given by Bayes' rule (1):

$$p_m=\frac{p_0\,\pi(m\mid0)}{\mathbb P(m)}.$$

The supplier has unit shortage cost $C_s>0$ and unit excess cost $C_e>0$, with critical ratio $\xi=C_s/(C_s+C_e)\in(0,1)$. At belief $p$ he solves the newsvendor problem (2), here normalized by $C_s+C_e$:

$$\min_{Q\ge0}\ p\,\mathbb E\big[\xi(D_0-Q)^++(1-\xi)(Q-D_0)^+\big]+(1-p)\,\mathbb E\big[\xi(D_1-Q)^++(1-\xi)(Q-D_1)^+\big].$$

A best-response profile $Q^*$ assigns to every belief $p\in[0,1]$ an optimal quantity $Q^*_p$; the set of them is $\mathcal B(\Gamma)$.

The retailer's cost at belief $p$ and quantity $Q$ is her expected shortage $R(p,Q)=p\,\mathbb E[(D_0-Q)^+]+(1-p)\,\mathbb E[(D_1-Q)^+]$. Her design problem (3) is

$$\min_{\Gamma,\ Q^*\in\mathcal B(\Gamma)}\ \sum_{m\in\mathcal M}\mathbb P(m)\,R\big(p_m,Q^*_{p_m}\big).$$

A policy is optimal if, paired with some best-response profile, it attains this minimum against every finite-message policy and every best-response profile. Full disclosure sends $m_i$ exactly in state $i$; no disclosure sends one message. The retailer's cost function (B.1) is $K_{DS}(p)=R(p,\bar Q_p)$, where $\bar Q_p$ is the largest optimal quantity at $p$, and $\kappa_{DS}$ is its lower convex envelope on $[0,1]$, the greatest convex function on $[0,1]$ below $K_{DS}$.

Formalization targets

Goal: Theorem 3 (p. 16)

Let $\tilde p=\max\big(1-\xi,\ 2(b_0-a_0)/(b_1-a_1)\big)$. For every $p_0\in[0,1]$:

$$2(b_0-a_0)\ge b_1-a_1\ \Longrightarrow\ \text{full disclosure is optimal;}$$ $$b_1-a_1>2(b_0-a_0)\ \Longrightarrow\ \begin{cases}\text{no disclosure is optimal}, & p_0\ge\tilde p,\\ \Gamma^*_{DS}\text{ is optimal}, & p_0<\tilde p,\end{cases}$$

where $\Gamma^*_{DS}$ has messages $m_0,m_1$ with $\pi^*_{DS}(m_0\mid\omega=0)=1$ and $\pi^*_{DS}(m_0\mid\omega=1)=\frac{1-\tilde p}{\tilde p}\frac{p_0}{1-p_0}$ (8). The paper writes "there exists $\tilde p$" and then gives its value; the goal states the value.

Milestones (App. C.2 and App. B)

1. Proposition 6 (p. 37): the supplier's optimal quantity, $Q^*_p=\xi(b_1-a_1)/(1-p)+a_1$ for $p<1-\xi$ and $(\xi-1+p)(b_0-a_0)/p+a_0$ for $p>1-\xi$; at $p=1-\xi$ every $Q\in[b_1,a_0]$ is optimal.
2. The value claim after (B.2) (p. 25): the optimal value of (3) is $\kappa_{DS}(p_0)$.
3. (C.9) (p. 38): $K_{DS}$ in closed form.
4. (C.13) (p. 39): $\lim_{x\to(1-\xi)^-}K_{DS}(x)-K_{DS}(1-\xi)=(1-\xi)(a_0-b_1)>0$.
5. Lemma 3 (p. 38): $\kappa_{DS}$ is the chord $pK_{DS}(1)+(1-p)K_{DS}(0)$ when $2(b_0-a_0)/(b_1-a_1)\ge1$, and otherwise the chord from $(0,K_{DS}(0))$ to $(\tilde p,K_{DS}(\tilde p))$ followed by $K_{DS}$ itself on $[\tilde p,1]$.

Significance

The result shows that the shape of the optimal disclosure policy is decided by the relative width of the two supports and, below a threshold, by the prior alone: when the high-demand support is at least half as wide as the low-demand one, the retailer reveals everything, whatever the supplier's cost structure. Otherwise the critical ratio enters only through $\tilde p$, and the optimal partial policy pools the high state with part of the low state so that the supplier's posterior lands exactly at $\tilde p$. Together with the nested and intersecting cases, it shows that the non-monotone dependence of informativeness on $\xi$ found under nested supports is not universal.

The paper proves the result in its Online Appendix (App. C.2, pp. 37–40), by citation of Kamenica–Gentzkow for the reduction to a convex envelope and by a case analysis for the envelope. To our knowledge none of it is machine-checked. This mission produces a formal model of persuasion with a newsvendor receiver, a formal proof of the concavification step for finite message spaces, and the envelope computation. Formalization also pins down a boundary case the printed proof leaves implicit (see Formalization scope).

Difficulty

The reduction to the envelope is cited from Kamenica and Gentzkow in the paper, so it has to be established from scratch for this model, with its joint choice of policy and best response and its finite message spaces. The envelope itself requires handling a function that is concave on $[0,1-\xi)$, convex on $(1-\xi,1]$ and discontinuous at $1-\xi$, where it jumps down. The obvious argument — treat $K_{DS}$ as continuous and compare one-sided derivatives — fails at that point, and the jump is what makes the chord to $\tilde p=1-\xi$ admissible.

The newsvendor step is not just the critical-fractile formula: at $p=1-\xi$ the mixture c.d.f. is flat at level $\xi$ on $[b_1,a_0]$, so the supplier's best response is not unique there.

Formalization scope

The Lean development lives in the namespace SCInfoDesign.Disjoint. Conventions:

• States are Fin 2, beliefs are $\mathbb P(\omega=0)$, and uniform expectations are interval integrals divided by the interval length.
• The supplier's cost (2) is divided by $C_s+C_e$, so $\xi\in(0,1)$ is the parameter; this does not change his optimal quantities.
• Message spaces are finite types; optimality is over all finite policies and all best-response profiles. The paper does not bound $\mathcal M$; binary messages already attain the optimum.
• No disclosure is the one-message policy; every uninformative policy has the same cost.
• A message of probability $0$ gets posterior $0$ and weight $0$ in (3).
• Standing hypotheses, implicit in the paper and stated in every item: $a_0<b_0$, $a_1<b_1$, $0\le a_0$, $0\le a_1$, $0<\xi<1$, $b_1<a_0$, $p_0\in[0,1]$.
• The boundary $p=1-\xi$. Proposition 6 and (C.9) print the quantity $b_1$ there. The paper's own design problem (3) and its footnote 9 let the retailer select the supplier's best response, and she prefers the largest one, $a_0$. $K_{DS}$ is defined with the largest optimal quantity; with $b_1$, (C.13) and Lemma 3 are false whenever $\tilde p=1-\xi$. Proposition 6 is therefore stated with the optimal set $[b_1,a_0]$ at the boundary.

The formalization is not trivial by construction: the supplier's response is an argmin of (2), not the closed form of Proposition 6, and optimality quantifies over every finite policy with every best response, not over the three named policies.

Infrastructure needed: interval integrals of piecewise-linear functions, the convex envelope (the published BiconvexProg.BranchBound.convexEnvelope), and a Jensen/splitting argument for Bayes-plausible posteriors. The concavification step and the newsvendor argmin for uniform mixtures are reusable beyond this mission, by the three sibling missions in particular. Proofs of any milestone are welcome.

Selected references

• O. Candogan, H. Gurkan, The Value of Information Design in Supply Chain Management, Management Science, 2024. https://doi.org/10.1287/mnsc.2023.03004 (preprint: https://ssrn.com/abstract=4378997)
• E. Kamenica, M. Gentzkow, Bayesian Persuasion, American Economic Review 101(6), 2011. https://doi.org/10.1257/aer.101.6.2590
• R. Levi, G. Perakis, J. Uichanco, The data-driven newsvendor problem: new bounds and insights, Operations Research 63(6), 2015. https://doi.org/10.1287/opre.2015.1422
• S. Boyd, L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004. https://doi.org/10.1017/CBO9780511804441

Motivation

A retailer often knows more about her own demand than the supplier who produces for her. When the supplier must commit to a production quantity before demand is realized, what the retailer tells him shapes how much he produces, and therefore how much demand she can serve. Information design (Bayesian persuasion, Kamenica and Gentzkow, 2011) asks how a sender should commit in advance to a randomized disclosure rule to steer a receiver's action.

O. Candogan and H. Gurkan, The Value of Information Design in Supply Chain Management (SSRN 4378997; Management Science, 2024, DOI 10.1287/mnsc.2023.03004) solve this problem for a supplier facing a newsvendor problem with uniform demand. Their Theorem 1 identifies the retailer's optimal policy: full disclosure, no disclosure, or an explicit two-message partial disclosure, according to thresholds on the critical ratio. Their Theorem 2, the goal of this mission, quantifies how much the optimal policy is worth compared with the two naive policies a practitioner would use by default, and how this gain moves with the retailer's prior and the supplier's cost structure.

Setting

The state is $\omega\in\{0,1\}$ with prior $p_0=\mathbb P(\omega=0)$. Demand is $D_0\sim U[a_0,b_0]$ in state $0$ and $D_1\sim U[a_1,b_1]$ in state $1$, with nested supports $a_0\le a_1<b_1\le b_0$.

Supplier. At belief $p=\mathbb P(\omega=0)$ the supplier chooses $Q\ge0$ to minimize the expected newsvendor cost

$$S_\xi(p,Q)=p\,\mathbb E\big[\xi(D_0-Q)^++(1-\xi)(Q-D_0)^+\big]+(1-p)\,\mathbb E\big[\xi(D_1-Q)^++(1-\xi)(Q-D_1)^+\big],$$

where $\xi=C_s/(C_s+C_e)\in(0,1)$ is the critical ratio of the unit shortage cost $C_s$ to the total unit cost $C_s+C_e$.

Retailer. The retailer learns $\omega$ and sends a message $m$ from a finite set $\mathcal M$ according to a committed policy $\pi(m\mid\omega)$. Message $m$ has probability $\mathbb P(m)=p_0\pi(m\mid0)+(1-p_0)\pi(m\mid1)$ and induces the posterior $p_m=p_0\pi(m\mid0)/\mathbb P(m)$. The supplier best-responds with an optimal quantity $Q^*(p_m)$, and the retailer pays her expected shortage

$$R(p,Q)=p\,\mathbb E[(D_0-Q)^+]+(1-p)\,\mathbb E[(D_1-Q)^+].$$

Her optimal expected cost $V_\xi(p_0)$ is the infimum of $\sum_m\mathbb P(m)\,R(p_m,Q^*(p_m))$ over all finite message sets, all policies and all best responses of the supplier.

Naive policies. Under no disclosure the supplier keeps the prior, and the retailer pays $K(p_0)=R(p_0,Q^*_{p_0})$. Under full disclosure he learns $\omega$, and she pays $K_F(p_0)=(1-p_0)K(0)+p_0K(1)$. The values of information are

$$VI_{ND}(\xi,p_0)=K(p_0)-V_\xi(p_0),\qquad VI_{FD}(\xi,p_0)=K_F(p_0)-V_\xi(p_0).$$

Thresholds. $\underline\tau(p)=p(a_1-a_0)/(b_0-a_0)$, $\hat p=\xi(b_0-a_0)/(a_1-a_0)$, $p_0^*=\sqrt{\hat p}$ and $\xi^*=1-\tfrac12(a_1-a_0)/(b_0-b_1+a_1-a_0)$.

Formalization targets

Goal: Theorem 2 (p. 13)

In the partial-disclosure regime $\xi\in(0,\underline\tau(p_0)]$, with $a_0<a_1$:

$$VI_{ND}\ \text{is unimodal in } p_0 \text{ with peak } p_0^*=\sqrt{\xi(b_0-a_0)/(a_1-a_0)}\ \text{and decreasing in } \xi;$$ $$VI_{FD}\ \text{is decreasing in } p_0 \text{ and unimodal in } \xi \text{ with peak } \xi^*.$$

For fixed $\xi$ the regime is $p_0\in[\hat p,1]$; for fixed $p_0$ it is $\xi\in(0,\underline\tau(p_0)]$.

Milestones

1. Proposition 1 (p. 8): the supplier's optimal quantity is unique and given in closed form.
2. (B.2) (p. 25): $V_\xi(p_0)=\kappa(p_0)$, the lower convex envelope of $K$ on $[0,1]$.
3. (B.5) (p. 28): $K$ in closed form for $\xi\le(a_1-a_0)/(b_0-a_0)$.
4. Lemma 1 (p. 25): $\kappa$ in closed form in the three regimes of $\xi$.
5. The four derivative displays (p. 30): $\partial VI_{ND}/\partial\xi$, $\partial VI_{ND}/\partial p_0$, $\partial VI_{FD}/\partial\xi$, $\partial VI_{FD}/\partial p_0$ in the regime.

Significance

The result. Theorem 2 tells a retailer when designing information is worth the effort. Against no disclosure, the gain is largest at the intermediate prior $p_0^*$ and shrinks as shortages become relatively more expensive for the supplier. Against full disclosure, the gain shrinks as the prior probability of the wide-support state $\omega=0$ grows and peaks at the intermediate critical ratio $\xi^*$. These comparative statics are what the paper's managerial discussion (pp. 13–14, Figures 4–5) rests on.

Formalizing it. The result is proved in the paper (Online Appendix B, pp. 24–30), by citing Kamenica–Gentzkow for the reduction to the convex envelope and by explicit calculus. No part of it is machine-checked. A complete formalization would contain a self-contained proof of the concavification reduction for a two-state sender–receiver game with finite message sets, the newsvendor quantile of a uniform mixture, and an exact convex-envelope computation, each reusable beyond this paper.

Difficulty

The derivative formulas are routine once $K$ and $\kappa$ are known in closed form. The work lies upstream. The optimal cost is an infimum over all finite policies and all best responses, and turning it into $\kappa(p_0)$ requires the Kamenica–Gentzkow argument: Jensen's inequality over Bayes-plausible posterior distributions for the lower bound, and a two-point splitting for attainment. $\kappa$ itself is a supremum over all convex minorants, and identifying it requires showing that $K$ is convex below $\hat p$ and concave above, and that the chord from $(\hat p,K(\hat p))$ to $(1,K(1))$ is supporting. Finally, $K$ is defined through an argmin, so its closed form needs the uniqueness of the newsvendor quantile. A solver who differentiates the closed forms of p. 28 directly proves only the last step.

Formalization scope

All objects live in the namespace SCInfoDesign.ValueInfo. The supports are bundled in a structure Params. The critical ratio $\xi$ is an explicit argument of every object, because Theorem 2 varies it.

Conventions.

• Uniform expectations are interval integrals divided by the interval length.
• The supplier's cost is the paper's cost (2) divided by $C_s+C_e$, which has the same minimizers.
• Message sets are finite (Fin n).
• A zero-probability message gets the junk posterior $0$ and weight $0$.
• $K$ uses the largest optimal quantity, which is the unique one here.
• $\kappa$ is the published BiconvexProg.BranchBound.convexEnvelope on $[0,1]$.
• The value of information is the difference, not its absolute value; the difference is nonnegative.
• "Unimodal with peak $x^*$" means strictly increasing up to $x^*$ and strictly decreasing from $x^*$, on the regime.
• The $\xi$-claims are stated for $p_0<1$: at $p_0=1$ both values are identically $0$.

Added hypotheses. These are the paper's implicit standing assumptions: $a_0<b_0$ and $a_1<b_1$, nonnegative demand ($0\le a_0$, $0\le a_1$), and $0<\xi<1$. The goal and the derivative displays also assume $a_0<a_1$: otherwise the regime is empty and $\hat p$ is $0/0$.

Ruled out. The optimal cost is not the cost of the paper's policy $\Gamma^*$, and the supplier's response is an argmin of (2), not the closed form of Proposition 1. Theorem 2 is therefore a statement about the game, not about a formula.

Infrastructure. A complete development needs the concavification theorem for finite policies (milestone 2, reusable for every two-state persuasion model), the uniform-mixture newsvendor quantile (milestone 1), the exact computation of a convex envelope (milestone 4) and one-variable calculus. Contributions of any milestone, of general lemmas on convex envelopes on an interval, or of the Kamenica–Gentzkow reduction in general form are welcome. The proofs of the paper are in its Online Appendix.

Selected references

• O. Candogan, H. Gurkan, The Value of Information Design in Supply Chain Management, Management Science, 2024 (read as SSRN 4378997). https://ssrn.com/abstract=4378997 , https://doi.org/10.1287/mnsc.2023.03004
• E. Kamenica, M. Gentzkow, Bayesian Persuasion, American Economic Review 101(6), 2011. https://doi.org/10.1257/aer.101.6.2590
• R. Levi, G. Perakis, J. Uichanco, The Data-Driven Newsvendor Problem: New Bounds and Insights, Operations Research 63(6), 2015. https://doi.org/10.1287/opre.2015.1422

Motivation

A retailer who sees her own demand before her supplier does can decide how much of that knowledge to pass upstream. Sharing everything is not obviously best: the supplier uses the information to set his production quantity for his own benefit, and the retailer bears a cost when he under-produces. Candogan and Gurkan (SSRN 4378997; published in Management Science, 2024, doi:10.1287/mnsc.2023.03004) treat this as a Bayesian persuasion (information design) problem in the sense of Kamenica and Gentzkow (AER 2011): the retailer commits in advance to a signalling policy, and the supplier best-responds to the posterior belief that each signal induces. The paper characterizes the retailer's optimal policy in closed form for uniform demand. This mission covers its first main result, the case where one demand support is nested inside the other.

The question links the supply-chain literature on information sharing between firms, where sharing is usually all-or-nothing, with the persuasion literature, where optimal signals are typically partial.

Setting

The state is $\omega\in\{0,1\}$, with prior $p_0=\mathbb P(\omega=0)\in[0,1]$. Demand is $D_\omega$, where $D_0$ is uniform on $[a_0,b_0]$ and $D_1$ is uniform on $[a_1,b_1]$. The supports are nested: $0\le a_0\le a_1<b_1\le b_0$ and $a_0<b_0$.

A disclosure policy $\Gamma=(\pi,\mathcal M)$ is a finite message space $\mathcal M$ and conditional probabilities $\pi(m\mid\omega)$. After message $m$ the supplier holds the posterior

$$p=\frac{\pi(m\mid\omega=0)\,p_0}{\pi(m\mid\omega=0)\,p_0+\pi(m\mid\omega=1)(1-p_0)}.$$

Full disclosure sends message $m_i$ exactly in state $i$; no disclosure sends the same message in both states.

At belief $p$ the supplier solves the newsvendor problem

$$\min_{Q\ge 0}\; p\,\mathbb E\big[\xi(D_0-Q)^+ + (1-\xi)(Q-D_0)^+\big] + (1-p)\,\mathbb E\big[\xi(D_1-Q)^+ + (1-\xi)(Q-D_1)^+\big],$$

where $\xi=C_s/(C_s+C_e)\in(0,1)$ is his critical ratio (shortage cost $C_s$, excess cost $C_e$). A best-response profile $Q^*$ picks an optimal quantity $Q^*_p$ for every belief $p\in[0,1]$. The retailer pays the expected shortage $p\,\mathbb E(D_0-Q^*_p)^+ + (1-p)\,\mathbb E(D_1-Q^*_p)^+$ at the induced posterior. Her design problem (3) minimizes the expectation of this cost over the random posterior, jointly over policies $\Gamma$ and best-response profiles $Q^*$. The function $K(p)$ of (B.1) is her cost when both parties hold belief $p$.

The thresholds are

$$\xi_h=\frac{a_1-a_0}{b_0-a_0-b_1+a_1},\qquad \underline\tau(p)=\frac{p(a_1-a_0)}{b_0-a_0},\qquad \bar\tau(p)=1-\frac{p(b_0-b_1)}{b_0-a_0}.$$

Formalization targets

Goal: Theorem 1 (p. 9)

For every prior $p_0\in[0,1]$:

$$\xi\in[\xi_h,1)\Rightarrow\text{full disclosure is optimal};\qquad \xi\in[\underline\tau(p_0),\xi_h]\Rightarrow\text{no disclosure is optimal};$$ $$\xi\in(0,\underline\tau(p_0)]\Rightarrow\Gamma^*\text{ is optimal},\quad \pi^*(m_1\mid\omega=0)=\frac{1-p_0}{p_0}\,\frac{\xi(b_0-a_0)}{(a_1-a_0)-\xi(b_0-a_0)},\ \ \pi^*(m_1\mid\omega=1)=1.$$

Milestones

1. Proposition 1 (p. 8): the supplier's optimal quantity $Q^*_p$ is unique and has an explicit three-piece form in $(p,\xi)$.
2. (B.2) (p. 25): the optimal value of (3) is $\kappa(p_0)$, where $\kappa$ is the lower convex envelope of $K$ on $[0,1]$.
3. (B.5) (p. 28): $K$ in closed form when $\xi\le(a_1-a_0)/(b_0-a_0)$.
4. Lemma 1 (p. 25): $\kappa$ in the three regimes of $\xi$.
5. The $\Gamma^*$ display (p. 26): under $\Gamma^*$, message $m_0$ has probability $(p_0-\hat p)/(1-\hat p)$ and induces posterior $1$, and, when $p_0<1$ (so that $m_1$ has positive probability), $m_1$ induces $\hat p=\xi(b_0-a_0)/(a_1-a_0)$.

Significance

The result shows that the optimal amount of disclosure depends on the critical ratio. When $\xi$ is high the retailer reveals everything; in an intermediate band she reveals nothing; when $\xi$ is low she uses a two-message policy that always reveals the narrow-support state ($\omega=1$ always sends $m_1$) but pools part of the wide-support state with it. Corollaries 1–4 of the paper read the thresholds off this theorem (independence of the prior for large $\xi$, full disclosure when $a_0=a_1$, never full disclosure when $b_0=b_1$), and Theorem 2 of the paper, on the value of information design relative to full and no disclosure, is built on Lemma 1 and (B.5).

The paper proves the result in its Online Appendix, citing Kamenica and Gentzkow for the reduction to a convex envelope. None of it has been machine-checked. A formalization would make the persuasion reduction explicit for finite message spaces and best-response profiles, and would check the case analysis of the envelope, where the paper prints one overlapping-indicator slip (Lemma 1, case 3).

Difficulty

The obvious argument is to compare the three named policies and pick the cheapest. That is not a proof: optimality is over every policy on every finite message space, and it is only the convex-envelope reduction that cuts the comparison down to splittings of the prior into posteriors. The reduction itself requires showing that the attainable expected costs are exactly the convex combinations of values of $K$ at Bayes-plausible posteriors. The envelope computation then needs the shape of $K$: the supplier's quantity is piecewise defined, so $K$ is a piecewise rational function of $p$ whose convexity changes across the boundaries $\underline\tau(p)=\xi$ and $\bar\tau(p)=\xi$. In the low-$\xi$ regime $K$ is neither convex nor concave on $[0,1]$, so its greatest convex minorant is a genuine mixture of $K$ itself and a line segment, whose junction point $\hat p$ has to be located exactly.

Formalization scope

States are Fin 2; a policy on a finite type $M$ is a map $\pi : \mathrm{Fin}\,2\to M\to\mathbb R$ with nonnegative entries and rows summing to $1$. The paper does not bound $\mathcal M$; finite message spaces are a convention, and binary spaces already attain the optimum. Uniform expectations are interval integrals divided by the length. The supplier's cost is normalized by $C_s+C_e$ and parameterized by $\xi$, which leaves its minimizers unchanged. A message of probability zero is given posterior $0$ and weight $0$.

The supplier's response is defined as an argmin of (2), never by the closed form of Proposition 1, and optimality quantifies over all finite policies and all best-response profiles, never over the three named policies; a formalization that hard-codes either would make the goal a statement about a formula. $K$ is evaluated at the largest optimal quantity, which is the unique one under the mission's hypotheses. The envelope $\kappa$ is the published definition BiconvexProg.BranchBound.convexEnvelope (greatest convex minorant) on $[0,1]$.

Standing hypotheses, stated in every theorem: $a_0<b_0$, $a_1<b_1$, $0<\xi<1$, $p_0\in[0,1]$, and nesting $a_0\le a_1$, $b_1\le b_0$. The hypotheses $0\le a_0$, $0\le a_1$ are added: demand is nonnegative, and without them the constraint $Q\ge0$ can bind. Equal supports are allowed; the threshold $\xi_h$ is then $0/0=0$ in Lean and the goal remains true. Lemma 1's third case is formalized as the piecewise function its two indicators intend.

A complete development needs: the convex-envelope (concavification) theorem for finite-support distributions on $[0,1]$, the newsvendor quantile characterization for a mixture of uniforms, and calculus for piecewise rational functions. The first two are reusable beyond this mission. Contributions to any milestone are welcome.

Selected references

• O. Candogan, H. Gurkan, The Value of Information Design in Supply Chain Management, Management Science, 2024. SSRN preprint: https://ssrn.com/abstract=4378997; DOI: https://doi.org/10.1287/mnsc.2023.03004
• E. Kamenica, M. Gentzkow, Bayesian Persuasion, American Economic Review 101(6), 2011. https://doi.org/10.1257/aer.101.6.2590
• R. Levi, G. Perakis, J. Uichanco, The Data-Driven Newsvendor Problem: New Bounds and Insights, Operations Research 63(6), 2015. https://doi.org/10.1287/opre.2015.1422

Why the price of borrowing a stock matters

To sell a stock short, an investor must first borrow it, and the owner who lends it charges a lending fee. Securities lending is a large market, and the fee varies across stocks: D'Avolio (2002) documents that shorting costs are positively related to the dispersion of investors' beliefs. Short-sale constraints have a long history in asset pricing (Miller 1977; Harrison and Kreps 1978; Jones and Lamont 2002), but most models either forbid short sales outright or take the fee as an exogenous parameter. Neither explains where the fee comes from, nor when a lending market is active at all.

Evgeniou, Hugonnier and Prieto build a dynamic general equilibrium model in which the fee is endogenous: two investors with logarithmic utility disagree about the expected return of a risky asset, and a lending agent, acting for the asset owners, sets the fee charged to short sellers to maximize the owners' fee revenue. Their §3 derives the equilibrium shorting cost in closed form at every state of the economy. This mission formalizes that derivation.

Setting

The economy has a riskless asset and two risky assets with strictly positive volatilities $\sigma_1,\sigma_2$. Asset 1 can be shorted at a cost; asset 2 cannot be shorted at all. There are two investors, an optimist $o$ and a pessimist $p$, with wealths $W^{(o)},W^{(p)}>0$. Each investor $a$ perceives market prices of risk (Sharpe ratios) $\theta^{(a)}_1,\theta^{(a)}_2$, and the optimist is more optimistic about asset 1: $\theta^{(p)}_1\le\theta^{(o)}_1$, the disagreement $\Delta\ge0$.

A short position in asset 1 pays a shorting cost $\Phi$ per dollar shorted, and a long position earns a lending yield $\Gamma$. Both are measured per unit of volatility of asset 1: $\phi=\Phi/\sigma_1$ and $\gamma=\Gamma/\sigma_1$. A position $m$ in asset 1 earns fees at the rate

$$\Lambda(m;\Phi,\Gamma)=m^+\Gamma-m^-\Phi ,$$

with $m^+=\max\{m,0\}$ and $m^-=\max\{-m,0\}$. Investor $a$ chooses wealth fractions $p=(p_1,p_2)$ with $p_2\ge0$ to solve the mean-variance problem

$$\max_{p\in\mathbb R\times\mathbb R_+}\Big\{\Lambda(p_1;\Phi,\Gamma)+p_1\sigma_1\theta^{(a)}_1+p_2\sigma_2\theta^{(a)}_2-\tfrac12(p_1\sigma_1+p_2\sigma_2)^2\Big\},$$

which is what logarithmic utility reduces to at each instant. The lending agent's revenue per unit of volatility at fee $y$ is

$$R(y)=\sum_a y\,\big(\theta^{(a)}_1+y\big)^-\,W^{(a)} .$$

An equilibrium at a state consists of these quantities such that: the no-dominance condition $\theta^{(a)}_2=\theta^{(a)}_1+\gamma$ holds for both investors (equation (7)); each investor's portfolio is optimal; asset 1, in positive supply $S_1>0$, clears; the lending market clears (fees paid by short sellers equal fees received by long holders); and $\phi$ is the least maximizer of $R$ over $y\ge\gamma$. The inactive set is $\mathcal L=\{\gamma=0\}$ and the active set $\mathcal S$ is its complement.

Formalization targets

Goal: equations (15)–(17)

At every equilibrium state,

$$\gamma=0\iff\theta^{(p)}_2\ge0,\qquad \phi=-\tfrac12\,\theta^{(p)}_1\,\mathbb 1_{\{\theta^{(p)}_2<0\}} .$$

Lending is active exactly where the pessimist perceives a strictly negative net Sharpe ratio on long positions, and there the lending agent charges half the Sharpe ratio $-\theta^{(p)}_1$ the pessimist could earn by shorting absent frictions.

Milestones, in attack order

1. Proposition 1 (p. 17): the optimal portfolios of the mean-variance problem under (7) and $\phi\ge\gamma$.
2. (11) (p. 18): the optimist is long, $\theta^{(o)}_2=\theta^{(o)}_1+\gamma>0$.
3. (14) (p. 18): $\gamma\sigma_1S_1=(\phi-\gamma)(\theta^{(p)}_1+\phi)^-W^{(p)}$.
4. (12)–(13) (p. 18): the maximizers of the revenue over $y\ge\gamma$, and their least element $\max\{\gamma,-\tfrac12\theta^{(p)}_1\}$.

Two companion statements are also included: (18) (p. 20), that the pessimist is strictly short on $\mathcal S$, and the fee flow $(\pi^{(p)}_1)^-\Phi=\tfrac14(\theta^{(p)}_1)^2W^{(p)}\mathbb 1_{\mathcal S}$ (p. 19).

Significance

The goal is the paper's description of the short market. It identifies the active set by a condition on one observable-in-principle quantity, the pessimist's net Sharpe ratio, and it gives the fee as a fixed fraction of the pessimist's frictionless Sharpe ratio. The rest of the paper rests on it: the one-asset closed forms of §4.1, the trading regions of §3.3, and the pricing results of Proposition 2 all start from (15)–(16). The fee-flow identity shows that the optimist captures a quarter of the pessimist's frictionless excess return, which is the upper bound Remark 1 attributes to any alternative fee-setting mechanism.

The result is proved in the paper, partly in the text and partly in Appendix A. Some steps are argued informally: (11) rests on the sentence "agents cannot be short simultaneously in equilibrium", and (14) on "substituting the optimal portfolios of Proposition 1 into the market clearing conditions". As far as is known, none of it has been machine-checked. A formalization makes each step explicit, including the degenerate states the text passes over. In checking the statements against each other, three printed slips were found and are corrected here (see Formalization scope).

Difficulty

The goal combines optimality, clearing and revenue maximization, and the obvious argument fails at its degenerate edge. On the inactive set the shorting cost equals the lending yield ($\phi=\gamma=0$). There Proposition 1's characterization of optimal portfolios no longer holds: portfolios that short asset 1 to buy asset 2 are also optimal. So the step "substitute the optimal portfolios" is not available, and (14) must be obtained from the clearing conditions directly in that case. Similarly the revenue maximizer is not unique on the inactive set; the shorting cost is pinned down only by the paper's selection of the least maximizer, and (16) is false for any other selection. Finally, (11) requires an argument that the two investors cannot both be short while asset 1 is in positive supply. This uses optimality of both portfolios, not just of one.

Formalization scope

Everything is stated at one state $(\omega,t)$ of the paper's continuous-time economy, about real numbers. The continuous-time economy of §2 (Brownian filtrations, consumption streams, the dynamics of wealth) is the paper's motivation and is not formalized; the formalized statements are its instantaneous equilibrium conditions. The time index is dropped throughout, and the paper's "arbitrary process $x_t$" in Proposition 1 becomes an arbitrary real number.

Conventions:

• Rates are per unit of volatility; the dollar rates are $\Phi=\phi\sigma_1$ and $\Gamma=\gamma\sigma_1$, never obtained by division.
• $m^+$ and $m^-$ are written as $\max\{m,0\}$ and $\max\{-m,0\}$; indicators are if … then … else 0.
• Dollar positions are $\pi^{(a)}_1=W^{(a)}p^{(a)}_1$.
• The standing assumptions are hypotheses of every equilibrium statement: $\sigma_1,\sigma_2>0$ (the standing assumption of §3), $S_1>0$, $W^{(o)},W^{(p)}>0$, and $\theta^{(p)}_1\le\theta^{(o)}_1$.
• The shorting-cost condition (4) is stated in its per-volatility form (10), over $y\ge\gamma$, with the least maximizer selected as in (13). A single lending agent is built in.
• Consumption clearing and asset-2 clearing are not part of the equilibrium predicate; no statement uses them, so leaving them out makes every statement more general.

Corrected slips of the page, each disclosed in the item concerned:

1. Proposition 1's "the optimal portfolio satisfies (9)" fails when $\phi=\gamma$; the converse direction is stated under $\phi>\gamma$, and the constraint $0\le x\le\theta_2$ only where $\theta_2\ge0$.
2. The indicator in (12) should be $\mathbb 1_{\{\theta^{(p)}_1+\gamma\ge0\}}$, not $\mathbb 1_{\{\theta^{(p)}_1\ge0\}}$; the least maximizer (13) is unaffected.
3. (18) prints "$\neq\emptyset$"; its proof shows the set is empty, which is what is stated.

The results (11), (13) and (14) are not built into the equilibrium predicate. With them assumed, the goal would reduce to a four-line computation; they are separate items to be proved. The definitions are short and self-contained, needing only real arithmetic from Mathlib. Proofs of the milestones, and proofs of the goal that use the milestones, are welcome.

Selected references

• T. Evgeniou, J. Hugonnier, R. Prieto, Asset Pricing with Costly Short Sales, Swiss Finance Institute Research Paper N°22-21, version of September 22, 2022 — the source of this mission. Published as J. Hugonnier, R. Prieto, Asset Pricing with Costly Short Sales, Management Science (2024), https://doi.org/10.1287/mnsc.2023.01887, whose numbering is not used here.
• G. D'Avolio, The market for borrowing stock, Journal of Financial Economics 66 (2002), 271–306.
• C. Jones, O. Lamont, Short-sale constraints and stock returns, Journal of Financial Economics 66 (2002).
• R. Radner, Existence of equilibrium of plans, prices and price expectations in a sequence of markets, Econometrica 40 (2) (1972), 289–303.

Motivation

Two-stage adjustable robust optimization models decisions taken in two steps around an uncertain demand: a first-stage decision is fixed now, the demand is revealed, and a second-stage (recourse) decision reacts to it. The objective is the worst-case total cost over a set of possible demands. Computing the optimal adjustable solution is intractable in general, and even for a single budget constraint it cannot be approximated within $\Omega(\log n/\log\log n)$ under a standard complexity assumption (Feige, Jain, Mahdian, Mirrokni, IPCO 2007), where $n$ is the number of decision variables.

Affine policies, in which the recourse is restricted to an affine function of the revealed demand (Ben-Tal et al. 2004), are computable by one linear program and are widely used in practice. The question is how much they lose in the worst case.

Uncertainty sets in applications are rarely a single budget: demand is usually grouped (by region, product family or time period) with a separate budget per group. When the groups are disjoint the set is a Cartesian product of budget sets, a class studied by Gupta et al. and by Feige et al. in the robust covering literature.

Timeline. Bertsimas and Goyal (2012) proved that affine policies are within $O(\sqrt m)$ of the adjustable optimum for general uncertainty sets and that this is tight for some sets. El Housni and Goyal (arXiv:1807.00163, 2018; Mathematics of Operations Research 2021) proved $O(\log n/\log\log n)$ for a single budget set (Theorem 3.1, the first mission of this series) and $O(\log^2 n/\log\log n)$ for disjoint constrained budgeted sets (Theorem 4.1, the goal of this mission).

Setting

Let $A\in\mathbb R^{m\times n}$, a non-negative recourse matrix $B\in\mathbb R^{m\times n}_+$, costs $c,d\in\mathbb R^n_+$ and a polyhedral set $\mathcal X\subseteq\mathbb R^n$ be given. For an uncertainty set $\mathcal U\subseteq\mathbb R^m$ of right-hand sides, problem (1.1) is

$$z_{AR}(\mathcal U)=\min_{x\in\mathcal X}\ c^Tx+\max_{h\in\mathcal U}\ \min_{y(h)\ge0}\big\{d^Ty(h)\ :\ Ax+By(h)\ge h\big\}.$$

A first-stage $x$ and a recourse rule $y(\cdot)$ form a feasible solution when $x\in\mathcal X$ and $y(h)\ge0$, $Ax+By(h)\ge h$ for every $h\in\mathcal U$. The affine problem (2.1) restricts the rule to $y(h)=Ph+q$ (still requiring $Ph+q\ge0$ on $\mathcal U$); its value is $z_{Aff}(\mathcal U)\ge z_{AR}(\mathcal U)$.

Let $S_1,\dots,S_L$ be a partition of $[m]$ and $w_{\ell i}\in[0,1]$ weights. The disjoint constrained budgeted set (4.1) is

$$\mathcal U=\Big\{h\in[0,1]^m\ :\ \sum_{i\in S_\ell}w_{\ell i}h_i\le1\ \ \forall\ell\in[L]\Big\}.$$

With $L=1$ it is the budget of uncertainty set of the first mission.

The fractional covering value (3.2) of a requirement $h$ is $z(h)=\min_{y\ge0}\{d^Ty: By\ge h\}$. In an online fractional covering problem the rows to be covered arrive in batches and a solution may only be increased; an online algorithm $\mathcal A$ is $\rho$-competitive when its cost on every sequence is at most $\rho$ times the offline optimum $\Theta$. Throughout, $\log$ is the natural logarithm and $\beta=8\log n/\log\log n$.

Formalization targets

Goal: Theorem 4.1

$$z_{Aff}(\mathcal U)=O\Big(\frac{\log^2n}{\log\log n}\Big)\cdot z_{AR}(\mathcal U)$$

for every instance with $\mathcal U$ a disjoint constrained budgeted set: there are $C>0$ and $N$ such that $z_{Aff}\le C\frac{\log^2n}{\log\log n}z_{AR}$ for all $n\ge N$, all $m$, every number $L$ of blocks and all data. The constant is unfixed, and the bound must not depend on $L$.

Milestones (the paper's proof, in order)

1. Lemma 3.3 (structural result), restated from the first mission: if covering each row $i\in\mathcal J$ costs more than $4\gamma\frac{\log n}{\log\log n}w_i$ while every scenario $\mathcal W\subseteq\mathcal J$ with $\sum_{\mathcal W}w_i\le1$ costs at most $\gamma$, then $z(\mathcal J)\le4\gamma\frac{\log n}{\log\log n}$ (for $n$ large).
2. Lemma 4.1 — for a greedy scenario $a_1,\dots,a_L$ chosen by Algorithm 1, the online cost $\nu_L$ is at most $\rho\cdot\mathrm{OPT}$.
3. Lemma 4.2 — the affine solution (4.7), a linear part on the thresholded components plus a static part, is feasible.
4. Lemma 4.3 — the linear part costs at most $\beta\rho\cdot\mathrm{OPT}$ for every $h\in\mathcal U$.
5. Lemma 4.4 — the static part costs at most $(1+2\rho+\beta\rho)\cdot\mathrm{OPT}$.

With $\rho=O(\log n)$, Lemmas 4.3 and 4.4 give the goal.

Significance

The result. For disjoint budgets the bound is within a $\log n$ factor of the hardness bound for a single budget, and it does not depend on the number of groups $L$. It shows that affine policies stay near-optimal beyond the single-budget case, for a class that models grouped demand. The paper notes that it is open whether the extra $\log n$ factor is necessary. Gupta et al. give an $O(\log n)$-approximation for a special case with 0/1 matrices and equal weights, but their algorithm is not an affine policy.

Formalizing it. The theorem is proved on paper; no machine-checked proof is known. The formal development makes explicit what the paper uses about the online covering algorithm (monotone, covering, competitive), handles the "without loss of generality" relabelling of the blocks in the greedy scenario, and records two gaps in the proof of Lemma 4.4 (zero weights, and a zero increment $\nu_\ell-\nu_{\ell-1}$, for which Lemma 3.3 is stated with $\gamma>0$).

Difficulty

The thresholds that split cheap from expensive components cannot use the single quantity $\mathrm{OPT}$ as in the single-budget case: a scenario may activate one budget in every block at once, and summing per-block bounds gives a factor $L$. That is the $O(L\log n/\log\log n)$ bound of the paper's Section 5. Removing the dependence on $L$ requires per-block thresholds that add up to $O(\log n)\cdot\mathrm{OPT}$, and the paper obtains them from the increments of an online covering algorithm along a greedily chosen worst sequence of scenarios. A proof of the goal therefore needs an $O(\log n)$-competitive online fractional covering algorithm, Buchbinder and Naor's Theorem 4.1, posed on this platform as BNCovPack.Covering.theorem_4_1 (b57de23d-5953-424f-a729-5a018aa74b37, open). That theorem requires positive costs, so zero-cost columns, which this paper allows, need separate handling. The static part also needs Lemma 3.3, the core of the first mission.

Formalization scope

• Data. Vectors are functions on Fin m, Fin n with the componentwise order; matrices are Matrix (Fin m) (Fin n) ℝ; Lean indices and blocks are 0-based. First stage and recourse share the dimension $n$, as on p. 1. The partition is S : Fin L → Finset (Fin m), pairwise disjoint and covering Fin m (empty blocks allowed).
• Values. $z_{AR}$, $z_{Aff}$, $z(h)$, $\Theta$ and $z_{Sta}$ are infima in the extended reals, $+\infty$ when infeasible. A formalization with real infima (equal to $0$ on infeasible problems) or without $Ph+q\ge0$ would trivialize the goal and is excluded, as is a constant $C$ that depends on the instance or on $L$.
• Standing assumptions of p. 1: $B\ge0$, $c,d\ge0$, $\mathcal X$ polyhedral, $w_{\ell i}\in[0,1]$, $S$ a partition. "$\mathcal U\subseteq[0,1]^m$ compact convex with $e_i\in\mathcal U$" holds for the set (4.1) and is not added.
• Added hypotheses and corrections. (i) $c^Tx\ge0$ for $x\in\mathcal X$: Theorem 4.1 is false without it (already for $L=1$), and it holds whenever $\mathcal X\subseteq\mathbb R^n_+$. (ii) $n\ge3$ where $\beta\ge0$ is needed, and a threshold $N_0$ in Lemma 3.3, which as printed fails at $n=2$. (iii) Covering solutions $v_i$ are required only for $i\in\mathcal I$.
• The online algorithm is an abstract structure OnlineCover with ratio $\rho$: starting at $0$, non-negative, monotone, covering every revealed coverable row, and $\rho$-competitive on disjoint batches. The milestones hold for every such algorithm, with the paper's $O(\log n)$ written as $\rho$. The goal does not mention the algorithm. Algorithm 1 is a predicate on a run (a bijection of blocks and the chosen scenarios) with its maximality clause, so ties are arbitrary.
• Thresholds are in multiplied form $\alpha_iz(e_i)\le w\beta(\nu_\ell-\nu_{\ell-1})$; no division by a weight that may be $0$.
• Infrastructure. Lemma 3.3 is shared with the first mission and needs LP duality and randomized rounding. Buchbinder–Naor's theorem, or any $O(\log n)$-competitive online fractional covering algorithm, is needed for the goal. Proofs of any milestone are welcome.

The source is arXiv:1807.00163v2; its printed page numbers equal the PDF page numbers.

Selected references

• O. El Housni, V. Goyal, On the Optimality of Affine Policies for Budgeted Uncertainty Sets, arXiv:1807.00163v2, 2019; Mathematics of Operations Research 46(2), 2021. https://arxiv.org/abs/1807.00163
• N. Buchbinder, J. Naor, Online primal-dual algorithms for covering and packing, Mathematics of Operations Research 34(2), 2009. https://doi.org/10.1287/moor.1080.0363
• D. Bertsimas, V. Goyal, On the power and limitations of affine policies in two-stage adaptive optimization, Mathematical Programming 134(2), 2012. https://doi.org/10.1007/s10107-011-0444-4
• U. Feige, K. Jain, M. Mahdian, V. Mirrokni, Robust combinatorial optimization with exponential scenarios, IPCO 2007, LNCS 4513.
• A. Ben-Tal, A. Goryashko, E. Guslitzer, A. Nemirovski, Adjustable robust solutions of uncertain linear programs, Mathematical Programming 99(2), 2004. https://doi.org/10.1007/s10107-003-0454-y