Inventory and Supply Chain

Completed

Operations Research Optimization Probability·Captain: mikedeng1

On Properties of Stochastic Inventory Systems I: Using the EOQ Order Quantity in the Stochastic (Q, r) Model Raises Costs by at Most 1/8Research Paper

Motivation

The economic order quantity (EOQ) is the most widely used formula in inventory management. It assumes that demand is a deterministic constant stream. Real demand is random, and the model that accounts for this, the continuous-review $(Q, r)$ policy with stochastic demand, has no closed-form optimum: for decades its optimal parameters were computed numerically, one instance at a time, which gave little insight into how the stochastic system behaves. Practitioners nevertheless kept using the EOQ quantity in stochastic systems and observed that the cost penalty was small (Wagner, O'Hagan and Lundh 1965; Naddor 1975; Archibald and Silver 1978), without an analytical explanation.

Zheng (Management Science 38(1), 1992) supplied that explanation. By minimising the average cost first over the reorder point and then over the order quantity, he obtained two simple optimality equations and compared the stochastic model with the EOQ model under the same cost structure. One of the results is the goal of this mission: for every leadtime-demand distribution, using the EOQ order quantity in the stochastic system raises the average cost by at most one eighth. The paper extends Federgruen and Zheng (1988), who treated the discrete-demand version of the cost function.

Setting

A single item faces demand at rate $\lambda > 0$ . Orders are delivered after a fixed leadtime $L > 0$ , and stockouts are backordered. Each order costs a fixed $K > 0$ . Inventory is held at cost rate $h > 0$ per unit and backorders are penalised at cost rate $p > 0$ per unit. Let $D \ge 0$ be the demand during a leadtime, with mean $E(D) = \lambda L$ . The newsvendor cost

G(y) = E\big[h(y - D)^+ + p(D - y)^+\big]

is the rate at which expected inventory costs accrue at time $t + L$ when the inventory position at time $t$ is $y$ . It is convex, and it is assumed, as in the paper, to attain its minimum at a unique point $y^0$ .

A $(Q, r)$ policy orders $Q$ units whenever the inventory position falls to the reorder point $r$ . Its long-run average cost is

c(Q, r) = \frac{\lambda K + \int_r^{r+Q} G(y)\,dy}{Q}. \qquad (1)

For a fixed $Q > 0$ let $r(Q)$ be an optimal reorder point, and set

H(Q) = G(r(Q)) \ (Q > 0),\quad H(0) = G(y^0),\quad C(Q) = c(Q, r(Q)),\quad A(Q) = Q H(Q) - \int_0^Q H(y)\,dy .

$C(Q)$ is the average cost when the reorder point is chosen optimally for $Q$ ; an order quantity $Q^* > 0$ minimising $C$ over $Q > 0$ is the optimal order quantity, and $C^* = C(Q^*)$ is the optimal cost.

The EOQ model is the special case in which the leadtime demand is the constant $\lambda L$ . Its cost rate is $G_d(y) = h(y - \lambda L)^+ + p(\lambda L - y)^+$ , and its optimal order quantity is

Q^*_d = \sqrt{\frac{2\lambda K(h+p)}{hp}} .

The subscript $d$ marks every object of the EOQ model ( $r_d$ , $H_d$ , $A_d$ ).

Formalization targets

Goal: Theorem 5

R = \frac{C(Q^*_d) - C^*}{C^*} \;\le\; \frac18 - \frac12\left(\frac12 - \frac{Q^*_d}{Q^*}\right)^2 \;\le\; \frac18 .

$C(Q^*_d)$ is the stochastic cost at the EOQ quantity with the reorder point re-optimised for it. The bound holds for every leadtime-demand distribution and every value of the parameters.

Milestones

In the order the goal's proof uses them:

Lemma 1 (joint convexity of $c$ ), Lemma 2 ( $r = r(Q) \iff G(r) = G(r+Q)$ ), Lemma 3 (properties of $r(Q)$ ), Corollary 1 ( $G(r(Q)) \le \max(G(r), G(r+Q))$ );
Eq. (7) ( $C(Q) = (\lambda K + \int_0^Q H)/Q$ ), Lemma 4 ( $H$ increasing, convex, asymptotic slope $hp/(h+p)$ ), Lemma 5 ( $C$ convex), Eq. (8) ( $H(Q^*) = C(Q^*)$ ), Theorem 1 ( $(Q, r)$ optimal iff $c(Q,r) = G(r) = G(r+Q)$ ), Lemma 6 ( $A$ increasing convex, $Q = Q^* \iff A(Q) = \lambda K$ , comparative statics in $K$ );
Eqs. (18), (20) (the EOQ model: $H_d(Q) = hpQ/(h+p)$ and the formula for $Q^*_d$ ), Eq. (22) ( $G_d \le G$ ), Lemma 7 ( $H_0 \le H_d \le H$ , $A \le A_d$ ), and the first inequality of Theorem 2, $Q^*_d \le Q^*$ .

Significance

The theorem is a distribution-free worst-case guarantee for the most common heuristic in inventory practice. It says that the EOQ formula, which needs only the mean demand rate and three cost parameters, loses at most $12.5\%$ against the true optimum, and that the loss is smaller when $Q^*_d/Q^*$ is close to $\frac12$ or to $1$ . Combined with the paper's Theorem 2 (the gap $Q^* - Q^*_d$ is bounded as $K$ grows), it implies that the relative loss vanishes as the fixed ordering cost grows. The milestones along the way (the optimality conditions of Theorem 1, the monotonicity of the optimal reorder point, the comparison of $H$ with its EOQ counterpart) are the standard structural facts about continuous $(Q, r)$ systems and are reused throughout the inventory literature.

The result is proved in the paper. No machine-checked version of it, or of the $(Q, r)$ optimality conditions for the continuous cost (1), is known to exist. The platform has related but different formalizations: the discrete cost function with integer $Q$ (InventoryControl_rqDiscrete), the $(R, Q)$ cost under normal demand (InventoryControl_rq), and the EOQ without backorders (InventoryControl_eoq). A complete development here provides the continuous $(Q, r)$ machinery for an arbitrary leadtime-demand distribution.

Difficulty

The paper's proofs differentiate $r(Q)$ and $H(Q)$ twice (Eqs. (4), (5)), which presupposes a leadtime demand with a smooth density. The formalization does not assume one, so that discrete demand, such as the Poisson demand of the paper's own numerical study, is covered. Every step that the paper takes through derivatives, in particular the convexity of $H$ and the slope bound $H' \le hp/(h+p)$ , has to be established by other means: through one-sided derivatives or chord arguments for the convex function $G$ , whose kinks are where the derivative-based argument breaks. The definition of $r(Q)$ as a minimiser also means its existence and uniqueness must be proved before any property of $H$ , $C$ or $A$ can be used.

Formalization scope

The model is a probability measure $\mu$ on $\mathbb{R}$ (the law of $D$ ), concentrated on $[0,\infty)$ , integrable, with mean $\lambda L$ ; $G$ is the integral of $h\max(y-x,0) + p\max(x-y,0)$ against $\mu$ . The standing assumptions are bundled in IsQRModel: $\lambda, L, h, p > 0$ , the conditions on $\mu$ , and the unique minimiser of $G$ (paper, p. 90). $K > 0$ is a separate hypothesis. No density is assumed.
$c$ , $r(Q)$ , $y^0$ , $H$ , $H_0$ , $C$ , $A$ and optimality of an order quantity are defined for an arbitrary cost rate $G$ and applied both to the newsvendor cost and to $G_d$ ; the EOQ objects $r_d$ , $H_d$ , $A_d$ are these definitions at $G_d$ , and Eqs. (18), (20) are theorems.
$r(Q)$ is a chosen minimiser of $c(Q,\cdot)$ (never defined by $G(r) = G(r+Q)$ , which is Lemma 2). $H(0) := G(y^0)$ ; right-continuity of $H$ at $0$ is part of the Lemma 4 milestone. Order quantities range over $(0,\infty)$ for $c$ and $C$ and over $[0,\infty)$ for $H$ , $H_0$ , $A$ .
$Q^*$ in the goal is any $Q > 0$ with $C(Q) \le C(Q')$ for all $Q' > 0$ ; Lemma 6 asserts that exactly one exists, so the goal is not vacuous. $Q^*_d$ is the explicit square-root formula.
Readings of informal words: "increasing" in Lemmas 4 and 6 means strictly increasing on $[0,\infty)$ ; " $Q^*$ increasing, $r^*$ decreasing in $K$ " means strictly; "asymptotic slope $hp/(h+p)$ " means that every chord of $H$ on $[0,\infty)$ has slope at most $hp/(h+p)$ and $H(Q)/Q \to hp/(h+p)$ ; Lemma 3 part 3 is stated as strict monotonicity of $r(Q)$ and $r(Q) + Q$ , and its derivative clause $-1 < r'(Q) < 0$ is omitted because $r$ need not be differentiable without a density; "the optimal order quantity" means existence and uniqueness; Lemma 7 is stated for $Q \ge 0$ .
A trivializing formalization is ruled out: $C(Q^*_d)$ is the stochastic cost with the reorder point re-optimised in the stochastic model (not the EOQ reorder point $r^*_d$ ), and no positivity of $C^*$ is assumed (it follows from the model).
Out of scope: the discrete cost (2), the §4 numerical study, and the unnumbered remarks after Theorem 5.
Needed infrastructure: interval integrals of convex functions, partial minimisation of jointly convex functions, Jensen's inequality for $\mu$ , and one-sided derivatives of convex functions. The generic $(Q, r)$ machinery (optimality conditions for arbitrary convex $G$ ) is reusable for other continuous-review models. Proofs of any milestone, and alternative proofs that avoid the paper's differentiability assumptions, are welcome.

Selected references

Yu-Sheng Zheng, On Properties of Stochastic Inventory Systems, Management Science 38(1):87–103, 1992. https://doi.org/10.1287/mnsc.38.1.87
Awi Federgruen and Yu-Sheng Zheng, An Efficient Algorithm for Computing an Optimal (r, Q) Policy in Continuous Review Stochastic Inventory Systems, Operations Research 40(4):808–813, 1992. https://doi.org/10.1287/opre.40.4.808
Paul H. Zipkin, Inventory Service-Level Measures: Convexity and Approximation, Management Science 32(8):975–981, 1986. https://doi.org/10.1287/mnsc.32.8.975
George Hadley and Thomson M. Whitin, Analysis of Inventory Systems, Prentice-Hall, 1963.
Daniel P. Heyman and Matthew J. Sobel, Stochastic Models in Operations Research, Vol. II, McGraw-Hill, 1984.

18 thms5 active usersReviewed

Completed

Operations Research Optimization Probability·Captain: mikedeng1

On Properties of Stochastic Inventory Systems II: The Optimal Order Quantity of the Stochastic (Q, r) Model Exceeds the EOQ by a Bounded GapResearch Paper

Motivation

The continuous-review $(Q, r)$ policy is the standard control rule for a single stocked item with random demand: whenever the inventory position falls to the reorder point $r$ , an order of fixed size $Q$ is placed. It is implemented in a large share of commercial inventory systems. Choosing the two parameters jointly has traditionally required numerical search (Hadley and Whitin, 1963; Federgruen and Zheng, 1992). In practice the order quantity is therefore often taken from the deterministic economic order quantity (EOQ) formula with backorders, and the reorder point is then set for the random demand.

Zheng (1992) turned this practice into a question with an exact answer: how does the optimal order quantity $Q^*$ of the stochastic model compare with the EOQ quantity $Q^*_d$ computed from the same cost data and the same mean demand? Its Theorem 2 answers it with a two-sided bound. This mission formalizes that theorem. Companion missions of the same series formalize the paper's cost bounds (Theorem 3), the flatness of the cost curve (Theorem 4) and the $1/8$ bound on the cost of using the EOQ quantity (Theorem 5).

Setting

Demand arrives at rate $\lambda > 0$ and replenishment orders arrive after a fixed leadtime $L > 0$ . Shortages are backordered. Holding costs accrue at rate $h > 0$ per unit held, backorder penalties at rate $p > 0$ per unit short, and every order costs $K > 0$ . The leadtime demand $D$ is a nonnegative random variable with law $\mu$ and mean $\mathbb{E}(D) = \lambda L$ . The expected inventory cost rate at inventory position $y$ is the newsvendor cost

G(y) = \mathbb{E}\big[h(y - D)^+ + p(D - y)^+\big],

assumed, as in the paper, to attain its minimum at a unique point $y^0$ . The long-run average cost of the policy $(Q, r)$ is

c(Q, r) = \frac{\lambda K + \int_r^{r+Q} G(y)\,dy}{Q}.

For each $Q > 0$ , let $r(Q)$ be an optimal reorder point, i.e. a minimizer of $c(Q, \cdot)$ . The analysis runs through the curves

H(Q) = G(r(Q))\ (Q > 0),\quad H(0) = G(y^0),\qquad H_0(Q) = H(Q) - G(y^0),\qquad A(Q) = QH(Q) - \int_0^Q H(y)\,dy,

and through the cost $C(Q) = c(Q, r(Q))$ of order quantity $Q$ with the reorder point set optimally. The optimal order quantity $Q^*$ is the minimizer of $C$ over $Q > 0$ .

The EOQ model is the case of a constant leadtime demand $\lambda L$ . Its cost rate is $G_d(y) = h(y - \lambda L)^+ + p(\lambda L - y)^+$ , and the same construction gives $r_d$ , $H_d$ , $A_d$ and the optimal quantity

Q^*_d = \sqrt{\frac{2\lambda K(h+p)}{hp}}.

Formalization targets

Goal: Theorem 2 (p. 96)

For $K > 0$ , let $\bar Q$ , $\bar Q_1$ , $\bar Q_2$ be the positive solutions of

Q H_0(Q) = 2\lambda K,\qquad H_0(Q) = H_d(Q^*_d),\qquad \int_0^Q H_0(y)\,dy = \lambda K.

Each has exactly one positive solution, and

Q^*_d \le Q^* \le \bar Q,\qquad \bar Q \le \bar Q_1,\qquad \bar Q \le \bar Q_2.

Moreover, with $\lambda, L, h, p$ and the demand law fixed, $K \mapsto \bar Q_1(K) - Q^*_d(K)$ is nondecreasing on $(0, \infty)$ and converges to a finite constant as $K \to \infty$ .

Milestones

The milestones are the paper's own numbered results that feed Theorem 2, listed in the order the argument uses them:

Lemma 2 (p. 90): for $Q > 0$ , $r$ is optimal iff $G(r) = G(r + Q)$ .
Eq. (7) (p. 91): $C(Q) = (\lambda K + \int_0^Q H(y)\,dy)/Q$ .
Lemma 4 (p. 91): $H$ is increasing and convex with asymptotic slope $hp/(h+p)$ .
Lemma 6 (p. 92): $A$ is increasing and convex, and $Q = Q^*$ iff $A(Q) = \lambda K$ .
Eqs. (18), (20) (p. 94): $H_d(Q) = \frac{hp}{h+p}Q$ , and $Q^*_d$ is optimal for the EOQ model.
Lemma 7 (p. 95): $H_0 \le H_d \le H$ and $A \le A_d$ .
Lemma 8 (p. 95): $\int_0^Q H \ge \tfrac12 QH(Q) \ge A(Q) \ge \tfrac12 QH_0(Q) \ge \int_0^Q H_0$ , with equalities for deterministic demand.

Significance

The result. Theorem 2 says that the EOQ formula always underestimates the optimal order quantity when leadtime demand is random. The underestimate is bounded by $\bar Q_1 - Q^*_d$ , a quantity that stays bounded however large the ordering cost is. So the relative error of the EOQ quantity vanishes as $K$ grows. The first inequality, $Q^*_d \le Q^*$ , is also an ingredient of the paper's Theorem 3 (cost bounds) and Theorem 5 (the EOQ quantity raises costs by at most $1/8$ ). The explicit bounds $\bar Q$ , $\bar Q_1$ , $\bar Q_2$ bracket $Q^*$ and give a search interval for it.

Formalizing it. The theorem has been proved on paper since 1992. No machine-checked version of it, or of the continuous-review $(Q, r)$ cost of Eq. (1), exists on this platform. The inventory items already here treat the discrete cost with integer order quantities, a normally distributed demand, or the EOQ without backorders. This mission provides a machine-checked version of the paper's optimality conditions for a general demand distribution. The paper's argument differentiates $G$ twice, i.e. it tacitly assumes a density. The formal statements do not, so a formal proof must redo those steps with one-sided (convexity) arguments. The printed argument for the limit in part (b) shows only that a derivative tends to zero. A complete proof of convergence is part of the work.

Difficulty

The obvious route to $Q^*_d \le Q^*$ compares the two cost curves $C$ and $C_d$ directly. It fails because $C \ge C_d$ pointwise, and a pointwise inequality between two convex functions says nothing about the order of their minimizers. The stochastic curve $H$ is defined only implicitly, as $G$ evaluated at a minimizer of a parametric integral, so its growth relative to the linear $H_d$ has to be established before any comparison of order quantities. For part (b), a vanishing derivative does not imply convergence ( $\log K$ also has a vanishing derivative), so the printed proof of the limit does not go through as written.

Without a density, $r(Q)$ need not be differentiable. Every derivative in the paper's proofs (of $r$ , $H$ and $A$ ) must be replaced by monotonicity or chord arguments.

Formalization scope

The Lean development uses the namespace ZhengQR.OrderQty. Its conventions:

Parameters. $\lambda, L, K, h, p$ are reals, all assumed strictly positive. $K > 0$ is implicit in the paper; at $K = 0$ the optimal quantity degenerates.
Demand. The law $\mu$ of $D$ is a probability measure on $\mathbb{R}$ that is integrable, has mean $\lambda L$ and is carried by $[0, \infty)$ . No density is assumed, so discrete laws such as the Poisson of the paper's §4 are allowed.
Standing assumption. $G$ has a unique global minimizer (p. 90). It is a hypothesis of every statement about the stochastic model.
Generic machinery. $c$ , $r(Q)$ , $y^0$ , $H$ , $C$ , $A$ , $H_0$ and optimality of $Q$ are defined for an arbitrary cost rate $G$ and applied to both the newsvendor cost and $G_d$ . So Eqs. (18) and (20) are theorems, not definitions. $r(Q)$ and $y^0$ are chosen minimizers, never solutions of Lemma 2's equation. $r(Q)$ minimizes $\int_r^{r+Q}G$ , which for $Q > 0$ has the same minimizers as $c(Q, \cdot)$ , so $H$ , $H_0$ and $A$ do not depend on $K$ .
Domains. $H$ , $H_0$ and $A$ are used on $[0, \infty)$ , $c$ and $C$ for $Q > 0$ only, and $Q^*$ is a $Q > 0$ minimizing $C$ over $(0, \infty)$ .
Readings of informal words.
- Lemma 4's "increasing" and Lemma 6's "increasing/decreasing" mean strictly.
- Lemma 4's "asymptotic slope $hp/(h+p)$ " means $H(Q)/Q \to hp/(h+p)$ together with the chord bound $H(Q') - H(Q) \le \frac{hp}{h+p}(Q' - Q)$ for $0 \le Q < Q'$ .
- " $\bar Q \overset{\text{def}}{=} \{Q : \dots\}$ " means the unique positive solution. The goal quantifies over every positive solution and separately asserts that exactly one exists.
- Theorem 2's "increasing function of $K$ " means nondecreasing, which is what the paper's proof establishes (a nonnegative derivative).
- "Converges to a constant" means a finite real limit.
- Lemma 8's "the leadtime demand is deterministic" means the EOQ model with cost rate $G_d$ .
Ruling out trivial readings. The goal's hypotheses are satisfiable (for example by a deterministic leadtime demand). Existence of $Q^*$ (Lemma 6) and of $\bar Q$ , $\bar Q_1$ , $\bar Q_2$ (the goal itself) is asserted, so neither the bounds nor the limit hold vacuously.

Infrastructure needed includes the following. Much of it is reusable for any single-item inventory model:

differentiation under the expectation, or one-sided substitutes, for $G$ ;
convexity of $H$ as the inverse of the width of the sublevel sets of $G$ ;
the envelope identity behind Eq. (7);
elementary convex-analysis facts about chords.

Contributions welcome: proofs of the milestones in any order, general lemmas on the newsvendor cost, and a complete convergence argument for part (b).

Selected references

Y.-S. Zheng, On Properties of Stochastic Inventory Systems, Management Science 38(1):87–103, 1992. https://doi.org/10.1287/mnsc.38.1.87
A. Federgruen, Y.-S. Zheng, An Efficient Algorithm for Computing an Optimal (r, Q) Policy in Continuous Review Stochastic Inventory Systems, Operations Research 40(4):808–813, 1992. https://doi.org/10.1287/opre.40.4.808

10 thms3 active usersReviewed

Completed

Operations Research Optimization Probability·Captain: mikedeng1

On Properties of Stochastic Inventory Systems III: Bounds between the Optimal Costs of the Stochastic (Q, r) Model and the EOQ ModelResearch Paper

Motivation

The continuous-review $(Q, r)$ policy — order a fixed quantity $Q$ whenever the inventory position falls to the reorder point $r$ — is the textbook policy for a single item with random demand and a positive replenishment leadtime (Hadley and Whitin 1963). Its optimal parameters have no closed form, so practice routinely falls back on the deterministic economic order quantity (EOQ) model with backorders, whose optimum is explicit. How much the deterministic model misjudges the stochastic system's cost is therefore a practical question, and before Zheng (1992) it had been studied only numerically (Wagner, O'Hagan and Lundh 1965; Naddor 1975; Archibald and Silver 1978).

Zheng's paper answers it analytically. This mission targets its Theorem 3, which brackets the optimal cost of the stochastic model by the optimal cost of the EOQ model with the same parameters.

Setting

Demands arrive at rate $\lambda>0$ and orders arrive after a fixed leadtime $L>0$ . Each order costs $K>0$ ; holding and backorder costs accrue at rates $h>0$ and $p>0$ per unit per unit time. The leadtime demand $D$ is a nonnegative random variable with $E(D)=\lambda L$ . The inventory cost rate at inventory position $y$ is the newsvendor cost

G(y)=E\big[h(y-D)^+ + p(D-y)^+\big],

assumed to attain its minimum at a unique point $y^0$ .

For order quantity $Q>0$ and reorder point $r$ , the long-run average cost is

c(Q,r)=\frac{\lambda K+\int_r^{r+Q}G(y)\,dy}{Q}.

Let $r(Q)$ be a reorder point minimizing $c(Q,\cdot)$ , and define $H(Q)=G(r(Q))$ for $Q>0$ , $H(0)=G(y^0)$ , and $C(Q)=c(Q,r(Q))$ . The optimal order quantity $Q^*$ minimizes $C$ over $Q>0$ , and $C^*=C(Q^*)$ . Write $H_0(Q)=H(Q)-G(y^0)$ and

C_0(Q)=\frac{\lambda K+\int_0^Q H_0(y)\,dy}{Q},

the controllable cost, so that $C(Q)=G(y^0)+C_0(Q)$ ; $C^*_0=C_0(Q^*)$ . The constant $G(y^0)$ is the newsboy cost.

The EOQ model is the same construction with demand constant at $\lambda L$ : $G_d(y)=h(y-\lambda L)^+ + p(\lambda L-y)^+$ , with functions $H_d$ , $C_d$ , optimal quantity $Q^*_d=\sqrt{2\lambda K(h+p)/(hp)}$ and optimal cost $C^*_d=C_d(Q^*_d)$ .

Formalization targets

Goal: Theorem 3 (p. 97)

C^*_0\le\frac{Q^*_d}{Q^*}\,C^*_d,\qquad C^*_d\le C^*\le G(y^0)+\frac{Q^*_d}{Q^*}\,C^*_d.

All three inequalities are part of the goal. The weaker remark after the proof, $C^*_d\le C^*\le C^*_d+G(y^0)$ , drops the factor $Q^*_d/Q^*$ and is not the goal.

Milestones

Eq. (7): $C(Q)=\big(\lambda K+\int_0^Q H(y)\,dy\big)/Q$ for $Q>0$ .
Eq. (8): $Q>0$ is optimal iff $H(Q)=C(Q)$ .
Eqs. (13)–(15): $C(Q)=G(y^0)+C_0(Q)$ , and $H_0(Q^*)=C_0(Q^*)$ .
Lemma 6: $A(Q)=QH(Q)-\int_0^QH$ is increasing and convex; $Q=Q^*$ iff $A(Q)=\lambda K$ ; $Q^*$ increases and $r^*$ decreases in $K$ .
Eqs. (18), (20): $H_d(Q)=\frac{hp}{h+p}Q$ , and $Q^*_d$ is the EOQ optimum.
Lemma 8: $\int_0^QH\ge\tfrac12QH(Q)\ge A(Q)\ge\tfrac12QH_0(Q)\ge\int_0^QH_0$ , with equalities for deterministic demand.
Eq. (22): $G_d(y)\le G(y)$ for all $y$ .

Significance

Theorem 3 says that randomness of leadtime demand raises the total optimal cost above the EOQ's, yet the controllable part of that cost — the part the order quantity actually trades off — is smaller than the EOQ's cost, scaled by $Q^*_d/Q^*$ . Combined with $Q^*_d\le Q^*$ (Theorem 2 of the paper), the gap $C^*-C^*_d$ is at most the newsboy cost $G(y^0)$ , independent of $K$ , so the EOQ cost is a good proxy when $K$ is large relative to $G(y^0)$ . The same machinery yields the paper's Theorem 5, that using $Q^*_d$ in the stochastic model costs at most $1/8$ more than the optimum.

The result was proved in 1992; no machine-checked proof is known to exist. Formalizing it requires the continuous $(Q,r)$ model as a whole — optimal reorder points, the one-variable reduction through $H$ , and the area function $A$ — none of which is in Mathlib. The companion missions of this series formalize Theorems 2, 4 and 5 of the same paper on the same model.

Difficulty

The middle inequality compares minima of two different functions: $C_d\le C$ pointwise follows from Jensen's inequality, but only after the reorder point of each model is chosen optimally, so the comparison has to pass through the definition of $C$ as a minimum over $r$ . The outer inequalities depend on Lemma 8, whose proof uses convexity of $H$ and a slope comparison $H'\le H_d'$ (Lemmas 4 and 7). The paper argues these through first and second derivatives of $r(Q)$ and $G$ , which exist only when the leadtime demand has a smooth distribution; the formal statements assume no density, so a proof must either avoid derivatives or handle one-sided ones. Existence of optimal reorder points and of $Q^*$ is asserted in the paper without a separate argument.

Formalization scope

Everything lives in the namespace ZhengQR.CostBounds. The machinery (qrCost, reorderPt, idealPt, Hfun, Cfun, Afun, H0fun, C0fun, IsOptQty) is defined for an arbitrary $G:\mathbb R\to\mathbb R$ and instantiated at the stochastic $G$ and at $G_d$ . A structure QRModel holds the parameters, the demand distribution $\mu$ (a probability measure on $\mathbb R$ ) and the standing assumptions.

Conventions committed to:

Positivity of $\lambda,L,K,h,p$ ; $D\ge0$ almost surely; $D$ integrable with $E(D)=\lambda L$ ; $G$ has a unique minimizer (p. 90). No density is assumed.
$r(Q)$ is a chosen minimizer of $c(Q,\cdot)$ over $\mathbb R$ , not a solution of $G(r)=G(r+Q)$ ; $y^0$ is a chosen minimizer of $G$ . Both use junk value $0$ when no minimizer exists, which never happens under the assumptions.
$H(0)=G(y^0)$ ; statements about $H$ and $A$ are on $[0,\infty)$ , about $c$ , $C$ , $C_0$ for $Q>0$ .
"Optimal order quantity" means $Q>0$ and $C(Q)\le C(Q')$ for all $Q'>0$ ; the goal takes any such $Q^*$ and Lemma 6 states that exactly one exists, so the goal is not vacuous.
$C^*_d$ is $C_d(Q^*_d)$ , with $Q^*_d$ the explicit formula (20); milestone 5 proves it is the EOQ optimum. $C^*_0$ is $C_0(Q^*)$ , which equals $\min_{Q>0}C_0$ by (13).
"Increasing" in Lemma 6 is read strictly, as the proof gives. Lemma 8 is stated for $Q\ge0$ ; "deterministic" means $\mu$ is the Dirac mass at $\lambda L$ .

A formalization in which $C^*_d$ were an arbitrary number, or $Q^*$ an arbitrary positive real, would make the goal false or empty; both are tied to the model above.

Needed infrastructure: existence of minimizers of convex coercive functions on $\mathbb R$ , differentiation of parametric integrals $\int_{r(Q)}^{r(Q)+Q}G$ , and properties of the newsvendor cost (convexity, coercivity, Jensen). Most of it is reusable for any continuous-review inventory model. Proofs of any milestone, and of lemmas the paper uses but this mission does not list (Lemmas 2–5, 7), are welcome.

Selected references

Y.-S. Zheng, On Properties of Stochastic Inventory Systems, Management Science 38(1):87–103, 1992. https://doi.org/10.1287/mnsc.38.1.87
G. Hadley and T. M. Whitin, Analysis of Inventory Systems, Prentice-Hall, 1963.
P. Zipkin, Inventory Service-Level Measures: Convexity and Approximation, Management Science 32(8):975–981, 1986. https://doi.org/10.1287/mnsc.32.8.975
A. Federgruen and Y.-S. Zheng, An Efficient Algorithm for Computing an Optimal (r, Q) Policy in Continuous Review Stochastic Inventory Systems, Operations Research 40(4):808–813, 1992. https://doi.org/10.1287/opre.40.4.808

10 thms4 active usersReviewed

Completed

Operations Research Optimization Probability·Captain: mikedeng1

On Properties of Stochastic Inventory Systems IV: The (Q, r) Cost Is Flatter in the Order Quantity than the EOQ CostResearch Paper

Motivation

The continuous-review $(Q, r)$ policy is the standard replenishment rule of inventory theory: whenever the inventory position (stock on hand plus on order minus backorders) drops to the reorder point $r$ , order a fixed order quantity $Q$ . It is used in practice and taught in every operations management course, usually after the deterministic economic order quantity (EOQ) model, which is the same system with a constant demand stream.

Practitioners and textbooks rely on a robustness property of the EOQ: its cost is very insensitive to the choice of order quantity. If the order quantity is off by a factor $\alpha$ , the cost rises only by the factor $\tfrac12(\alpha + 1/\alpha)$ ; ordering 50% too much costs about 8% extra. The insensitivity of the stochastic $(Q, r)$ system to its control parameters had been observed numerically (Wagner, O'Hagan and Lundh 1965; Naddor 1975; Archibald and Silver 1978), but, as Zheng notes, no analytical result on it was known.

Timeline:

1963: Hadley and Whitin derive the $(Q, r)$ cost for Poisson demand.
1986: Zipkin proves that the average backorders of a $(Q,r)$ policy are jointly convex in $(Q, r)$ under continuous demand (Zipkin 1986).
1992: Zheng derives simple optimality conditions for the continuous $(Q, r)$ model and compares it with the EOQ model under the same cost structure. One of the results is that the stochastic cost curve is flatter in the order quantity than the EOQ curve (Zheng 1992). This mission formalizes that result.

Setting

Demands arrive at rate $\lambda>0$ ; orders arrive after a fixed leadtime $L>0$ ; all stockouts are backordered. Each order costs $K>0$ ; holding costs accrue at rate $h>0$ per unit in stock and penalty costs at rate $p>0$ per unit backordered. The leadtime demand $D\ge 0$ has distribution $\mu$ with finite mean $E(D) = \lambda L$ .

The inventory cost rate at inventory position $y$ is

G(y) = E\big[h(y-D)^+ + p(D-y)^+\big],

assumed to attain its minimum at a unique point $y^0$ . The long-run average cost of the policy $(Q, r)$ is

c(Q, r) = \frac{\lambda K + \int_r^{r+Q} G(y)\,dy}{Q}, \qquad Q>0.

For fixed $Q>0$ let $r(Q)$ be a reorder point minimizing $c(Q,\cdot)$ , and let

C(Q) = c(Q, r(Q)), \qquad H(Q) = G(r(Q))\ (Q>0), \quad H(0) = G(y^0).

$C$ is the cost of the order quantity $Q$ when the reorder point is always chosen optimally for it. An optimal order quantity $Q^*$ minimizes $C$ over $Q>0$ , and $C^* = C(Q^*)$ .

The EOQ model is the same system with the constant leadtime demand $\lambda L$ . Its cost rate is $G_d(y) = h(y-\lambda L)^+ + p(\lambda L-y)^+$ , and $r_d$ , $H_d$ , $C_d$ are the objects above at $G_d$ , with optimum $Q^*_d$ and $C^*_d$ .

Formalization targets

Goal: Theorem 4

\frac{C(\alpha Q^*)}{C^*} \le \frac12\left(\alpha + \frac1\alpha\right) \qquad \forall \alpha>0.

The goal holds for every demand distribution satisfying the standing assumptions and every optimal $Q^*$ . Both regimes, $\alpha<1$ and $\alpha>1$ , are included.

Milestones

In the order the proof uses them:

Eq. (7): $\int_{r(Q)}^{r(Q)+Q} G = \int_0^Q H$ , hence $C(Q) = \big(\lambda K + \int_0^Q H(y)dy\big)/Q$ for $Q>0$ .
Lemma 4: $H$ is increasing and convex on $[0,\infty)$ with asymptotic slope $hp/(h+p)$ .
Eq. (8): an optimal $Q^*$ exists, and $Q>0$ is optimal iff $H(Q) = C(Q)$ .
Eq. (18): $H_d(Q) = \frac{hp}{h+p}Q$ , with $r_d(Q) = \lambda L - \frac{h}{h+p}Q$ .
Lemma 7: $H_0(Q) \le H_d(Q) \le H(Q)$ and $A(Q)\le A_d(Q)$ , where $H_0 = H - G(y^0)$ and $A(Q) = QH(Q) - \int_0^Q H$ .
Eqs. (26)–(27): $H(\alpha Q)\le \alpha H(Q)$ for $\alpha>1$ and $H(\alpha Q)\ge\alpha H(Q)$ for $0<\alpha<1$ .
Lemma 9: $\int_Q^{\alpha Q} H(y)\,dy \le \frac{\alpha^2-1}{2}\,Q H(Q)$ for all $\alpha>0$ , $Q>0$ .

Significance

In the EOQ model the relative cost of a scaled order quantity is exactly $C_d(\alpha Q^*_d)/C^*_d = \tfrac12(\alpha + 1/\alpha)$ (Eq. (25) of the paper). Theorem 4 shows that the stochastic system is at least as forgiving. The bound holds for every leadtime-demand distribution with a unique newsvendor minimizer, and it does not depend on the parameters $K$ , $h$ , $p$ , $\lambda$ or $L$ . Because the reorder point is re-optimized for each quantity, the bound applies to the practical question of how much a misestimated lot size costs when the safety stock is set correctly.

Together with the other results of the paper (the $1/8$ bound for the EOQ heuristic and the bounds between $Q^*$ and $Q^*_d$ , which are separate missions of this series), it gives a closed-form account of why the EOQ is a good heuristic for stochastic systems.

The result has a complete published proof. It has not been machine-checked. The work that remains is a formal proof for general distributions: the paper differentiates $G$ and $r(Q)$ twice, and a formal proof has to replace those derivatives with arguments that need no density.

Difficulty

$C(Q)$ is defined through an inner minimization over the reorder point, so its shape in $Q$ is controlled by the implicitly defined function $H(Q) = G(r(Q))$ rather than by $G$ directly. The obvious approach would bound $C(\alpha Q^*)$ with the reorder point fixed at $r(Q^*)$ . That approach is the wrong comparison: it bounds a larger quantity, and the resulting bound depends on the distribution.

The paper's proof uses three properties of $H$ : that it is convex, that its slope never exceeds the EOQ slope $hp/(h+p)$ , and that it dominates $H_d$ . The paper obtains these from the derivatives $r'(Q)$ and $H'(Q)$ under a smooth demand distribution. Without a density, $r(Q)$ is only an argmin and $H$ need not be differentiable, so none of these three properties can be read off a derivative formula; the asymptotic slope in particular depends on the finite mean $E(D) = \lambda L$ and on the behaviour of $G$ at $\pm\infty$ .

Formalization scope

The mission is set in Lean 4 with Mathlib. All objects are real valued.

Model. The structure QRModel bundles $\lambda, L, K, h, p>0$ , a probability measure $\mu$ on $\mathbb{R}$ with integrable identity, $\int x\,d\mu = \lambda L$ , $D\ge 0$ almost surely, and the unique-minimizer hypothesis on $G$ . $K>0$ is implicit in the paper and made explicit here. No density is assumed; deterministic and discrete demands are allowed, and the paper's own numerical study uses Poisson demand.
Generic machinery. $c$ , $r(Q)$ , $y^0$ , $H$ , $H_0$ , $C$ and $A$ are defined for an arbitrary cost rate and instantiated at $G$ and at $G_d$ . $r(Q)$ and $y^0$ are chosen minimizers; they are never defined by the equation $G(r) = G(r+Q)$ , which is a lemma of the paper. $H(0) = G(y^0)$ . Values at $Q<0$ (and of $c$ , $C$ at $Q\le 0$ ) are junk, and every statement restricts to $Q>0$ or $Q\ge 0$ .
Readings of informal words. "Increasing" in Lemma 4 is strict on $[0,\infty)$ , since the proof shows $H'>0$ . "Asymptotic slope $hp/(h+p)$ " is stated as $H(Q)/Q\to hp/(h+p)$ together with the chord bound $H(Q_2)-H(Q_1)\le \frac{hp}{h+p}(Q_2-Q_1)$ for $0\le Q_1\le Q_2$ . The chord bound is the derivative-free form of $H'\le hp/(h+p)$ that the proofs of Lemmas 7–9 use. "The optimal order quantity" is IsOptQty Q, meaning $Q>0$ and $C(Q)\le C(Q')$ for all $Q'>0$ . Its existence is asserted in the Eq. (8) milestone, so the goal is not vacuous. " $\forall\alpha>0$ " is a real $\alpha>0$ with real division $1/\alpha$ . In Lemma 9 the integral $\int_Q^{\alpha Q}$ is oriented, as on the page.
Ruling out trivializations. $C(\alpha Q^*)$ re-optimizes the reorder point for $\alpha Q^*$ ; holding it at $r(Q^*)$ would be a different theorem. $C^*>0$ is a consequence of the model, not a hypothesis.

A complete development needs the following:

integrability and continuity of $G$ ;
existence of the optimal reorder point;
convexity of $H$ ;
the asymptotics $G - G_d\to 0$ at $\pm\infty$ ;
Jensen's inequality $G_d\le G$ (Eq. (22));
existence of $Q^*$ .

These facts about newsvendor cost functions are reusable in the other missions of this series. Contributions of any of them as separate lemmas are welcome.

Selected references

Y.-S. Zheng, On Properties of Stochastic Inventory Systems, Management Science 38(1):87–103, 1992. https://doi.org/10.1287/mnsc.38.1.87
P. H. Zipkin, Inventory Service-Level Measures: Convexity and Approximation, Management Science 32(8):975–981, 1986. https://doi.org/10.1287/mnsc.32.8.975
G. Hadley and T. M. Whitin, Analysis of Inventory Systems, Prentice-Hall, 1963.
H. M. Wagner, M. O'Hagan and B. Lundh, An Empirical Study of Exactly and Approximately Optimal Inventory Policies, Management Science 11(7):690–723, 1965. https://doi.org/10.1287/mnsc.11.7.690
A. Federgruen and Y.-S. Zheng, An Efficient Algorithm for Computing an Optimal (r, Q) Policy in Continuous Review Stochastic Inventory Systems, Operations Research 40(4):808–813, 1992. https://doi.org/10.1287/opre.40.4.808

11 thms3 active usersReviewed

Operations Research Optimization Probability·Captain: mikedeng1

Single-Period Multiproduct Inventory Models with Substitution: No Order for a Product Stocked Above Its Base-Stock LevelResearch Paper

Motivation

A retailer or manufacturer that stocks several grades of the same item (memory chips of different speeds, steel of different strengths, seats in fare classes) can often meet demand for a lower grade with a higher one when the lower grade runs out. This downward substitution changes the stocking decision: each product now protects the demand of every class below it, so the optimal stock of one product depends on the stock of all the others, and the single-product newsvendor answer no longer applies product by product.

Bassok, Anupindi and Akella (Operations Research 47(4), 1999) set up a single-period model with $N$ products and full downward substitution and showed that the optimal ordering policy still has a simple structure: there is a base-stock vector $y^*$ ; products below it are ordered up to it, and a product already at or above its base-stock level is not ordered at all. Earlier work on multiproduct ordering, Veinott (1965) and Ignall and Veinott (1969), gave monotonicity conditions through a substitute matrix condition on the Hessian of the cost, which is hard to verify for a general $N$ -product substitution structure; the paper works instead with concavity, submodularity and explicit first partial derivatives. Two-product substitution models had been analysed by McGillivray and Silver (1978) and Parlar and Goyal (1984).

Setting

There are $N$ products and $N$ demand classes, both numbered $1,\dots,N$ . Class $i$ can be served by product $j$ whenever $j \le i$ , at a unit substitution cost $b$ when $j < i$ . Each class $i$ has unit revenue $p_i$ and unit backorder cost $\pi_i$ ; each product $j$ has unit purchase cost $c_j$ and effective unit salvage value $s_j$ (salvage value minus holding cost, possibly negative). Put $a_{ji} = p_i$ if $j = i$ , $a_{ji} = p_i - b$ if $j < i$ , and $T_k = p_k + \pi_k - b$ . The standing assumptions are: (1) $\pi_i + p_i \ge \pi_j + p_j$ for $i < j$ ; (2) $s_i \ge s_j$ for $i < j$ ; (3) $a_{ij} + \pi_j - s_i \ge 0$ for $i \le j$ .

The sequence of events: the starting inventory $x$ is observed; stock is raised to $y \ge x$ at unit costs $c$ ; the demand vector $d$ is realized; stock is allocated to classes; leftovers are salvaged. For fixed $y$ and $d$ the allocation is the linear program

G(y,d) = \max \sum_{i}\sum_{j \le i} a_{ji} w_{ji} + \sum_i s_i v_i - \sum_i \pi_i u_i

subject to $u_i + \sum_{j\le i} w_{ji} = d_i$ , $v_j + \sum_{i \ge j} w_{ji} = y_j$ , and $w, u, v \ge 0$ , where $w_{ji}$ is the amount of product $j$ given to class $i$ , $u_i$ the shortage of class $i$ and $v_j$ the leftover of product $j$ . The expected profit is

P(x,y) = -\sum_k c_k (y_k - x_k) + \mathbb E\, G(y, D),

and the ordering problem is $\max_{y \ge x} P(x,y)$ ; a maximizer is an optimal level $\bar y(x)$ .

Allocation Algorithm (A) serves the classes in the order $1,2,\dots,N$ , class $i$ first from product $i$ and then from the leftovers of products $i-1,\dots,1$ . The subproblem shortage $S^k_j$ is the unmet demand of class $j$ when (A) runs on the classes $k,\dots,j$ with the products $k,\dots,j$ only; $\vec S^k_{a,n} = 0$ means $S^k_m = 0$ for all $a \le m \le n$ . The paper's first partial derivatives of $P$ are sums of salvage values, substitution costs and the $T_k$ , weighted by probabilities of such shortage events.

Formalization targets

Goal: Theorem 2

With $y^*$ a maximizer of $P(0,\cdot)$ over $y \ge 0$ , every optimal level $\bar y$ for every starting inventory $x \ge 0$ satisfies

x_i \ge y^*_i \implies \bar y_i = x_i .

Milestones

Proposition 1: Algorithm (A) is feasible and optimal for the allocation LP, and its value is $G(y,d)$ .
Proposition 2: $y \mapsto P(x,y)$ is concave and submodular on $\{y \ge 0\}$ .
Eq. (4): the explicit formula for $\partial P/\partial y_i$ in terms of shortage probabilities.
Theorem 1: there is $y^* \ge 0$ with $\bar y(x) = y^*$ whenever $0 \le x \le y^*$ .
Lemmas 1, 2, 3, 5: identities and monotonicity properties of the shortage probabilities used to compare $\partial P/\partial y_i$ and $\partial P/\partial y_{i+1}$ .

Significance

Theorems 1 and 2 give the optimal ordering policy of the substitution model its base-stock form: a vector $y^*$ , computed once, determines the decision for every starting inventory in the region $x \le y^*$ and fixes the order of every overstocked product elsewhere. The paper builds its bounds on $y^*$ , its iterative algorithm for two products and its computational study of the value of substitution (§3) on this structure. Proposition 1 turns the second-stage linear program into a closed-form greedy allocation, which is what makes the derivative formula (4) explicit.

The results are proved in the paper, but none of them has been machine-checked. Several steps of the paper are informal: Proposition 1 is proved by reference to Monge sequences of transportation problems, the proof of Theorem 2 treats only the adjacent pair $j = i+1$ , and the paper uses independence of demand classes, densities and a unique optimal level without stating them. A formal development makes these hypotheses explicit and checks each step. The model, the greedy allocation and the shortage calculus are reusable for other multi-product newsvendor and assortment models.

Difficulty

The obvious argument for Theorem 2 is the one-dimensional one: if $x_i \ge y^*_i$ then $\partial P/\partial y_i \le 0$ at $\bar y$ , so product $i$ should not be raised. It fails because $\partial P/\partial y_i$ depends on the other coordinates: at $\bar y$ some products are raised above $x$ and others kept at $x_j > y^*_j$ , and concavity plus submodularity alone do not control the sign. For a general concave submodular function the conclusion is false; a three-variable quadratic in which raising one coordinate lowers the optimal level of a second one, which in turn raises the marginal value of the first, is a counterexample. The proof has to use the specific structure of the substitution model, through the pairwise comparison of the partial derivatives in Eq. (4). The derivative formula itself requires a careful account of how an extra unit of product $i$ propagates through the greedy allocation of every later class.

Formalization scope

Products and classes are indexed by Fin N (the paper's index $k$ is Lean index $k-1$ ); stocks, demands and prices are real. The allocation LP is encoded with the upward arcs $w_{ji}$ , $i < j$ , forbidden (fixed to $0$ ), as in the paper's proof of Proposition 1; $G$ is the supremum of the LP objective. The demand law is a product $\nu_1 \otimes \dots \otimes \nu_N$ . Submodularity is the lattice inequality $P(x, y \vee y') + P(x, y \wedge y') \le P(x,y) + P(x,y')$ , which is equivalent to the paper's nonpositive cross partials (Definition 2) for twice differentiable functions. Derivatives are stated with HasDerivAt, and the derivative inequalities of Lemmas 2 and 5 in the stronger monotone form, so that no statement is made true by a junk value of deriv. The "…" in Eq. (4) and in the lemmas are expanded as finite sums with the general term inferred from the printed first and last terms.

Hypotheses the paper uses without stating, made explicit here:

the substitution cost is nonnegative, $b \ge 0$ (Proposition 1 is false for $b < 0$ );
the demand classes are independent (product forms in Lemma 3 and Appendix B);
each demand is nonnegative, has finite mean and has a density;
$s_i < c_i < p_i + \pi_i$ for every product (Theorem 1's proof);
every demand law charges every nonempty open interval of $[0,\infty)$ , standing in for the uniqueness of the optimal level $\bar y(x)$ that the notation presupposes (Theorems 1 and 2).

The goal quantifies over every maximizer $y^*$ of $P(0,\cdot)$ and every optimal $\bar y$ ; it is not an existence statement, and $y^*$ is not chosen by the prover. Without the full-support hypothesis the universal statement fails already for one product (a flat-topped profit). Lemmas 4 and 6 of the paper are not included: under the definitions used here both are false as printed (small two- and three-product computations with exponential demands show it), and Theorem 3 comes after the goal and fails as printed for $x_i \ge y^*_i$ .

A proof needs integrals of piecewise-linear functions of the demand vector, differentiation under the integral sign, and facts about product measures. Contributions of any of the milestones, and of general lemmas on the greedy allocation (monotonicity of $S^k_j$ in $y$ and $d$ ), are welcome.

Selected references

Y. Bassok, R. Anupindi, R. Akella, Single-Period Multiproduct Inventory Models with Substitution, Operations Research 47(4):632–642, 1999. https://doi.org/10.1287/opre.47.4.632
A. F. Veinott, Jr., Optimal Policy for a Multi-Product, Dynamic, Nonstationary Inventory Problem, Management Science 12(3):206–222, 1965. https://doi.org/10.1287/mnsc.12.3.206
E. Ignall, A. F. Veinott, Jr., Optimality of Myopic Inventory Policies for Several Substitute Products, Management Science 15(5):284–304, 1969. https://doi.org/10.1287/mnsc.15.5.284
A. J. Hoffman, On Simple Linear Programming Problems, in V. Klee (ed.), Convexity, Proceedings of Symposia in Pure Mathematics, Vol. 7, AMS, 1963.

12 thms2 active usersReviewed

Completed

Dynamic Programming Operations Research Optimization·Captain: mikedeng1

Integrating Replenishment Decisions with Advance Demand Information II: With Zero Set-up Cost the Myopic Base-Stock Policy Is Optimal When Myopic Levels Are NondecreasingResearch Paper

Motivation

Many firms learn about demand before it has to be served: customers place orders days or weeks ahead of the date they want delivery. Gallego and Özer (Management Science 47(10), 2001) model this advance demand information in a periodic-review inventory system and ask how the optimal replenishment policy should use it. Classical inventory theory (Arrow, Harris and Marschak 1951; Scarf 1959; Veinott 1965, 1966; Iglehart 1963) assumes that nothing about future demand is known when an order is placed. With advance orders the state of the system is no longer a single number, and it is not a priori clear whether the familiar policy structures survive.

This mission covers the paper's zero set-up cost case (Section 5). The companion mission Integrating Replenishment Decisions with Advance Demand Information I covers the positive set-up cost case and its $(s, S)$ policies.

Setting

Time is divided into periods $t = 1, \dots, T$ . The supply lead time is an integer $L \ge 0$ , and the information horizon is $N$ . In period $t$ customers place orders $D_t = (D_{t,t}, \dots, D_{t,t+N})$ , where $D_{t,s} \ge 0$ is demand placed in period $t$ for delivery in period $s$ . Throughout, $N > L + 1$ ; write $M = N - L - 1 \ge 1$ .

At the start of period $t$ the decision maker knows two things. The first is the modified inventory position $x_t$ : on-hand stock plus outstanding orders minus backorders, net of the demand already observed for the protection period $t, \dots, t+L$ . The second is the vector

o_t = (o_{t,t+L+1}, \dots, o_{t,t+N-1}) \in \mathbb{R}^M

of demands already observed for periods beyond the protection period. The decision maker raises the position to $y \ge x_t$ at zero fixed cost, the demand vector $D_t$ is realised, and the state moves to

x_{t+1} = y - \sum_{k=0}^{L+1} D_{t,t+k} - o_{t,t+L+1}, \qquad o_{t+1,s} = o_{t,s} + D_{t,s}\ (s = t+L+2, \dots, t+N),

with $o_{t,t+N} = 0$ .

Costs enter through a single-period cost $G_t : \mathbb{R} \to \mathbb{R}$ (holding, backorder and linear ordering cost, charged against the demand over the protection period) and one-period discount factors $\alpha_{t+1} > 0$ . The optimal cost-to-go $J_t$ and the cost $V_t$ of ordering up to $y$ satisfy

J_t(x, o) = \min_{y \ge x} V_t(y, o), \qquad V_t(y, o) = G_t(y) + \alpha_{t+1}\,\mathbb{E}\,J_{t+1}(x_{t+1}, o_{t+1}), \qquad J_{T+1} \equiv 0,

where the expectation is over $D_t$ . The base-stock level in period $t$ is the smallest minimizer

y_t(o) = \min\{y : V_t(y, o) = \min_x V_t(x, o)\},

and the myopic level is the smallest minimizer of the single-period cost,

y^m_t = \min\{y : G_t(y) = \min_x G_t(x)\}.

A function $f(x, \theta)$ has decreasing differences if $f(x_1, \theta) - f(x_2, \theta) \le f(x_1, \theta') - f(x_2, \theta')$ whenever $x_1 \ge x_2$ and $\theta \ge \theta'$ componentwise.

Formalization targets

Goal: Theorem 5 (p. 1352)

If $t \mapsto y^m_t$ is nondecreasing on $\{1, \dots, T\}$ , then for every period $t$ and every observed-demand vector $o \ge 0$ ,

y_t(o) = y^m_t .

The optimal order-up-to level then ignores all advance information beyond the protection period. A second item states the paper's stationary special case: if $G_t = G$ for all $t$ , the smallest minimizer $y^m$ of $G$ is the optimal base-stock level in every period.

Milestones: Theorem 4 (p. 1351)

For every period $t$ and every fixed $o_t$ :

$V_t(\cdot, o_t)$ is convex and $V_t(x, o_t) \to \infty$ as $|x| \to \infty$ ;
$y_t(o_t)$ exists and $J_t(x, o_t) = V_t(\max(y_t(o_t), x), o_t)$ : a state-dependent base-stock policy is optimal;
$J_t(\cdot, o_t)$ is nondecreasing and convex;
$V_t(x, o)$ has decreasing differences in $(x, o)$ ;
$J_t(x, o)$ has decreasing differences in $(x, o)$ ;
$y_t(o)$ is nondecreasing in $o$ .

Parts 1–3 are what the goal's proof uses. Parts 4–6 are the paper's second zero set-up result, monotonicity of the base-stock level in observed demand.

Significance

The theorem identifies when advance demand information beyond the protection period can be ignored. When the myopic levels do not decrease over time, which includes stationary costs and ramping-up demand, the $(1 + M)$ -dimensional dynamic program collapses to a sequence of one-dimensional newsvendor-type problems. That is both a computational simplification and a managerial statement: information about demand after the protection period does not change the order. Theorem 4, Part 5 gives the complementary monotone comparative statics. When the myopic condition fails, more observed demand never lowers the order-up-to level.

The results are proved in the paper, with the proofs in Appendix B. No machine-checked version exists. This mission produces a formal account of the finite-horizon recursion with a multi-dimensional information state, and checks the base-stock and myopic-optimality arguments against it.

Difficulty

The obvious induction carries convexity of $J_{t+1}$ backward, but here the future cost is evaluated at a random next state $(x_{t+1}, o_{t+1})$ whose first coordinate depends on the current observed demand $o_{t,t+L+1}$ . Showing that the base-stock level does not depend on $o_t$ therefore needs more than convexity. It needs to know where $J_{t+1}(\cdot, o_{t+1})$ is flat, uniformly in the random $o_{t+1}$ , and that the next position cannot exceed the current order-up-to level. The latter holds only on the reachable states, where observed demands are nonnegative. For a sufficiently negative $o_{t,t+L+1}$ the next period starts above its myopic level whatever is ordered now, and the conclusion fails. On the analytic side, every infimum and expectation in the recursion must be shown to be finite and attained before the order-theoretic argument can start.

Formalization scope

The model is parametrised by $L$ and $M \ge 1$ , with $N = L + M + 1$ . The demand vector is a function on $\{0, \dots, N\}$ and $o$ a function on $\{0, \dots, M-1\}$ , ordered componentwise. $J_t$ is defined by backward recursion with $J_t \equiv 0$ for $t > T$ . The minimum over $y \ge x$ is a real infimum and the expectation a Bochner integral against the law $\mu_t$ of $D_t$ . Attainment and finiteness are consequences proved in the theorems, not assumptions. Base-stock and myopic levels are characterised as smallest minimizers (IsLeast), never through sInf.

The single-period cost $G_t$ is a primitive rather than being assembled from $c_t$ , $g_t$ and the lead-time demand; the paper's $G_t$ has the assumed properties, so the theorems cover the paper's model. Hypotheses the paper uses without stating, all placed on primitives and labelled in the statements:

nonnegative demands, $D_{t,s} \ge 0$ almost surely;
coercivity of $G_t$ (the paper states it for $\tilde G_t$ only);
$\alpha_{t+1} > 0$ ;
finiteness of the expectation in (9), guaranteed by linear growth of $G_t$ and finite first moments of $D_t$ . This covers piecewise-linear holding and backorder costs with any finite-mean demand (including the paper's Poisson example), but excludes superlinear costs;
in the goal, $o \ge 0$ , the set of reachable states.

The goal cannot be trivialised: the hypotheses are satisfied by concrete instances (for example $G_t(y) = |y|$ with any finite-mean nonnegative demand), and the conclusion identifies the base-stock level exactly rather than asserting that some minimizer exists.

Out of scope: the reduction of the control problem to the functional equation (Appendix A, Özer 2000), the infinite-horizon Theorem 6, and Lemma 5, whose proof argues on the integers and whose real-valued form with a unit forward difference is unverified. Contributions of general lemmas are welcome: convexity and attainment for $\inf_{y \ge x}$ of a convex coercive function, and preservation of convexity and decreasing differences under expectation. All of them are reusable in other inventory models.

Selected references

G. Gallego, Ö. Özer, Integrating Replenishment Decisions with Advance Demand Information, Management Science 47(10):1344–1360, 2001. https://doi.org/10.1287/mnsc.47.10.1344.10261
A. F. Veinott, Optimal Policy for a Multi-Product, Dynamic, Nonstationary Inventory Problem, Management Science 12(3):206–222, 1965. https://doi.org/10.1287/mnsc.12.3.206
D. L. Iglehart, Optimality of (s, S) Policies in the Infinite Horizon Dynamic Inventory Problem, Management Science 9(2):259–267, 1963. https://doi.org/10.1287/mnsc.9.2.259
D. M. Topkis, Supermodularity and Complementarity, Princeton University Press, 1998. https://doi.org/10.1515/9781400822539

9 thms2 active usersReviewed

Algorithmic Game Theory Operations Research Optimization+1·Captain: mikedeng1

A Supply Chain Theory of Factoring and Reverse Factoring 1: The Supplier's Equilibrium Choice Among Recourse, Non-Recourse and Reverse FactoringResearch Paper

Motivation

Small and medium-sized suppliers that sell to large retailers typically ship first and are paid weeks or months later. Until the invoice is paid, the supplier's cash is trapped in accounts receivable, while production has to be financed up front. Factoring (selling or pledging the receivable to a financial intermediary for immediate cash) and reverse factoring (a buyer-initiated program in which the retailer approves the invoice and the supplier is paid early by the retailer's bank) are the standard remedies, and reverse factoring programs of large buyers are often coupled with an extension of payment terms. Which of these instruments a supplier should use, and how the answer depends on the credit ratings of the two firms, is the question addressed by Kouvelis and Xu, "A Supply Chain Theory of Factoring and Reverse Factoring", Management Science 67(10):6071–6088, 2021 (doi:10.1287/mnsc.2020.3788). The paper embeds each financing scheme in the pull wholesale-price game of Cachon (2004) and compares the resulting equilibria.

Setting

A retailer (the Stackelberg leader) offers a wholesale price $w$ to a capital-constrained supplier (the follower), who then chooses a production quantity $q \ge 0$ and carries the inventory; the retail price $p$ is fixed, and $0 < c < p$ is the unit production cost. Demand $D \ge 0$ has density $f$ , complementary distribution function $\bar F$ , finite mean, $f > 0$ on $[0, \mathbb Z]$ ( $\mathbb Z \le +\infty$ ), and a strictly increasing failure rate $z = f/\bar F$ (strict IFR). Expected sales are $S(q) = \int_0^q \bar F(\xi)\,d\xi$ , and $k(q) = S(q)/\bar F(q)$ .

Each firm $j \in \{s, r\}$ has a credit rating $C_j \in (C_{\min}, C_{\max})$ . The default probability $\rho_j = \rho(C_j) \in [0,1]$ is strictly decreasing in the rating, and the interest-rate premium $\eta_j = \eta(C_j) > 0$ is decreasing. Production takes a lead time $t_1$ , payment follows after a term $t_2$ , and the supplier faces a Poisson liquidity shock of rate $\lambda_s$ during production (the retailer, rate $\lambda_r$ ). Under a scheme $i \in \{\mathcal F, \mathcal N, \mathcal R\}$ (recourse, non-recourse, reverse factoring, the last with a payment extension $\tau \ge 0$ ), the supplier's expected profit is

\pi_i(q; w) = (1-\rho_s)\big(\Lambda_i e^{-\lambda_s t_1} w S(q) - c q e^{\eta_s t_1}\big),

with coefficients $\Lambda_{\mathcal F} = (1-\rho_r) + (1-\rho_s) - e^{\eta_s t_2}$ , $\Lambda_{\mathcal N} = e^{-\eta_r t_2}(1-\rho_r)$ , $\Lambda_{\mathcal R} = e^{-\eta_r(t_2+\tau)}$ , and effective unit cost $c_i = c\,e^{(\eta_s+\lambda_s)t_1}/\Lambda_i$ . The retailer's profit is $e^{-\lambda_s t_1}(1-\rho_r)(p-w)S(q)$ under factoring and carries the extra factor $2 - e^{-\lambda_r \tau}$ under reverse factoring.

Formalization targets

Goal: Proposition 5

For a given $\tau \ge 0$ , let $\mathbb C_3$ be the unique supplier rating with $\Lambda_{\mathcal F} = \Lambda_{\mathcal R}$ , $\mathbb C_1$ the one with $\Lambda_{\mathcal F} = \Lambda_{\mathcal N}$ , and $\mathbb C_{\mathcal F}, \mathbb C_{\mathcal N}, \mathbb C_{\mathcal R}$ the feasibility thresholds ( $c_i = p$ ). With all three schemes available,

e^{-\eta_r\tau} < 1-\rho_r:\quad \mathcal F \text{ adopted} \iff C_s > \mathbb C_{\mathcal F}\vee\mathbb C_1,\qquad \mathcal N \text{ adopted} \iff \mathbb C_{\mathcal N} < C_s \le \mathbb C_1;

1-\rho_r \le e^{-\eta_r\tau}:\quad \mathcal F \text{ adopted} \iff C_s > \mathbb C_{\mathcal F}\vee\mathbb C_3,\qquad \mathcal R \text{ adopted} \iff \mathbb C_{\mathcal R} < C_s \le \mathbb C_3.

Milestones

Proposition 2 (p. 6078): recourse factoring is feasible iff $C_s > \mathbb C_{\mathcal F}$ , and then the unique equilibrium solves $p\bar F(q) = c_{\mathcal F}[1+z(q)k(q)]$ , $w = c_{\mathcal F}/\bar F(q)$ .
Proposition 3 (p. 6079): the same for non-recourse factoring with $c_{\mathcal N}$ .
§5.2 (p. 6082, Proposition EC.2): the same for reverse factoring with $c_{\mathcal R}(\tau)$ .
§4.4 (p. 6080, Lemma EC.2): between feasible schemes, the supplier's equilibrium profits are ordered as the $\Lambda_i$ .
Proposition 4 (p. 6080): the choice between $\mathcal F$ and $\mathcal N$ alone.

A follow-on item states Corollary 1(i) (p. 6081): when the retailer's rating is at least the supplier's, non-recourse factoring strictly dominates recourse factoring whenever the latter is feasible.

Significance

Proposition 5 is the paper's main prediction: non-recourse factoring is the choice of medium-rated suppliers, recourse factoring of highly rated ones, and reverse factoring with a fixed payment extension is chosen only by low-to-medium-rated suppliers and only if the retailer's rating is not too high relative to the extension. The paper uses it to explain the documented reluctance of suppliers to join reverse-factoring programs that come with extended payment terms (Wuttke, Rosenzweig and Heese 2019; Corsten 2010, a teaching case), and it is the starting point of the paper's Proposition 6 on the retailer's optimal payment extension, which is the subject of the second mission of this series.

The results are proved in the paper's Online Appendix B. To the best of available knowledge none of them, and no model of supply chain finance, has a machine-checked proof. A formal development would also supply a reusable treatment of the pull wholesale-price game under a strictly IFR demand with an arbitrary effective unit cost, of which Propositions 2, 3 and EC.2 are three instances.

Difficulty

The case analysis of Proposition 5 is short once the milestones are available; the substance lies in them. Proposition 2 requires solving a bilevel problem: the follower's best response has to be identified for every wholesale price, including prices at which the supplier produces nothing, and the leader's objective has to be shown to have a single maximizer. The natural route through the first-order condition needs the IFR property to exclude multiple stationary points, and it has to cope with a support end $\mathbb Z$ that may be finite (where $\bar F$ vanishes and $k$ , $z$ lose meaning) or infinite. Lemma EC.2 requires the equilibrium supplier profit as an explicit function of the effective cost and a monotonicity argument for it; comparing the $\Lambda_i$ directly, without the equilibrium, does not prove it. The proofs themselves are not in the main text.

Formalization scope

Demand is a probability measure μ on ℝ with a density f, the support end Z : EReal, and the complementary distribution function Fbar μ x = μ((x, ∞)). The model data, the coefficients coef, the effective costs cF, cN, cR, the two profit functions, best responses, equilibria, feasibility and adoption are definitions; all theorems are for arbitrary data satisfying Params.Valid and DemandModel. Readings fixed by the formalization:

"Feasible": some wholesale price $w \ge 0$ with a supplier best response gives the retailer strictly positive profit. It is not defined as $c_i < p$ , which is what Propositions 2 and 3 prove.
"Adopted" / "should be adopted": the scheme is feasible and its equilibrium supplier profit is best among the feasible available schemes, with ties resolved $\mathcal R \succ \mathcal N \succ \mathcal F$ , the order forced by the paper's boundaries ( $C_s = \mathbb C_1$ , $C_s = \mathbb C_3$ , $C_r = \mathbb C_2$ ). Profits are compared, not the $\Lambda_i$ .
"The unique value of $C_s$ that satisfies …": a point of $(C_{\min}, C_{\max})$ satisfying the equation and the only such point. The equation $c_{\mathcal F} = p$ is cross-multiplied, $c\,e^{(\eta_s+\lambda_s)t_1} = p\Lambda_{\mathcal F}$ , since $\Lambda_{\mathcal F}$ may be $\le 0$ .
" $C_r > \mathbb C_2$ " is read through the paper's equivalence $\tau > -\eta_r^{-1}\ln(1-\rho_r)$ , i.e. $e^{-\eta_r\tau} < 1-\rho_r$ : the stated assumptions give no single crossing in $C_r$ .
"The unique equilibrium can be derived from …": the equilibrium exists and is unique, and it is exactly the solution of the system with $q \in (0, \mathbb Z)$ ; this part is stated under feasibility.
"Increasing/decreasing" is weak unless stated (p. 6075); $\rho$ is strictly decreasing, $\eta$ weakly.
Continuity of $f$ is read on $[0,\mathbb Z]$ , and $\mathbb Z$ as the upper end of the support.
Additions: wholesale prices are nonnegative; the retailer's reverse-factoring profit is the last line of the p. 6082 display (the middle line has a stray factor $w$ ).
Corollary 1(i): "higher credit rating" is read as $C_r \ge C_s$ , "dominates" as a strictly larger equilibrium supplier profit whenever recourse is feasible.

A formalization in which feasibility or adoption is defined by the inequalities being proved ( $c_i < p$ , largest $\Lambda_i$ ) makes the propositions trivial and is ruled out by the definitions above. The profit functions (7), (10) and the p. 6082 display are taken as the model; the derivation from bank and factor pricing (Eqs. (1), (5), (6), Lemma 1) is not formalized, and the unstated assumptions of Table EC.2 are not included. Contributions of reusable lemmas on $S$ , $k$ and $z$ under strict IFR are welcome.

Selected references

P. Kouvelis and F. Xu, A Supply Chain Theory of Factoring and Reverse Factoring, Management Science 67(10):6071–6088, 2021. https://doi.org/10.1287/mnsc.2020.3788
G. P. Cachon, The Allocation of Inventory Risk in a Supply Chain: Push, Pull, and Advance-Purchase Discount Contracts, Management Science 50(2):222–238, 2004. https://doi.org/10.1287/mnsc.1030.0189
D. A. Wuttke, E. Rosenzweig, H. S. Heese, An Empirical Analysis of Supply Chain Finance Adoption, Journal of Operations Management 65(3):242–261, 2019.
P. Kouvelis and W. Zhao, Who Should Finance the Supply Chain? Impact of Credit Ratings on Supply Chain Decisions, Manufacturing & Service Operations Management 20(1):19–35, 2018.

8 thms1 active userReviewed

Algorithmic Game Theory Operations Research Optimization+1·Captain: mikedeng1

A Supply Chain Theory of Factoring and Reverse Factoring 2: The Retailer's Optimal Reverse Factoring Payment ExtensionResearch Paper

Motivation

Large retailers pay their suppliers weeks or months after delivery, and small suppliers fill the gap with short-term finance. In factoring the supplier sells the receivable to a factor for immediate cash; in reverse factoring the retailer arranges the program with a bank, which pays the supplier early at a rate priced on the retailer's credit rating. Retailers commonly attach a condition: the supplier must accept a longer payment term. Wuttke et al. (Journal of Operations Management, 2019) report that buyers extended payment terms by 54 days on average on adopting reverse factoring and that many suppliers delayed adoption; Corsten (2010) reports suppliers resisting a program because of the demanded payment delay (both as cited by Kouvelis and Xu, pp. 6082–6083). How long an extension a retailer can demand, and what it gains by demanding it, is therefore a practical design question.

Kouvelis and Xu (Management Science 67(10), 2021) answer it inside a Stackelberg supply chain model with credit and liquidity risk. This mission formalizes their answer, Proposition 6 of §5.3: the retailer's optimal payment extension when she keeps the existing wholesale price.

Setting

Demand $D\ge0$ has density $f$ , distribution function $F$ and $\bar F=1-F$ ; $f>0$ on $[0,\mathbb Z]$ with $\mathbb Z\le+\infty$ the upper end of the support, $f$ is continuous there, the mean is finite, and the failure rate $z(\xi)=f(\xi)/\bar F(\xi)$ is strictly increasing. Write $S(q)=\int_0^q\bar F(\xi)\,d\xi$ for expected sales and $k(q)=S(q)/\bar F(q)$ .

A retailer (the leader) sets a wholesale price $w$ , and a capital-constrained supplier (the follower) chooses a production quantity $q\ge0$ ; the retail price $p$ exceeds the unit cost $c$ . Each firm $j\in\{s,r\}$ has a credit rating $C_j\in(C_{\min},C_{\max})$ , a default probability $\rho_j=\rho(C_j)\in[0,1]$ with $\rho$ strictly decreasing, and an interest premium $\eta_j=\eta(C_j)>0$ with $\eta$ decreasing. The lead time is $t_1$ , the payment term $t_2$ , and $\lambda_s,\lambda_r\ge0$ are the liquidity risks.

Under a post-shipment scheme with coefficient $\Lambda$ the supplier earns

\pi(q;w)=(1-\rho_s)\bigl(\Lambda e^{-\lambda_s t_1}wS(q)-c\,q\,e^{\eta_s t_1}\bigr),

with $\Lambda_{\mathcal F}=(1-\rho_r)+(1-\rho_s)-e^{\eta_s t_2}$ (recourse factoring), $\Lambda_{\mathcal N}=e^{-\eta_r t_2}(1-\rho_r)$ (non-recourse factoring) and $\Lambda_{\mathcal R}=e^{-\eta_r(t_2+\tau)}$ (reverse factoring with payment extension $\tau\ge0$ ). The retailer earns $\Pi=e^{-\lambda_s t_1}(1-\rho_r)(p-w)S(q)$ under factoring and

\Pi_{\mathcal R}(w,\tau)=e^{-\lambda_s t_1}(1-\rho_r)(2-e^{-\lambda_r\tau})(p-w)S(q_{\mathcal R})

under reverse factoring, where $q_{\mathcal R}$ is the supplier's best response. Its first-order condition is $w\bar F(q_{\mathcal R})=c_{\mathcal R}(\tau)=c\,e^{(\eta_s+\lambda_s)t_1+\eta_r(t_2+\tau)}$ (Eq. (12)).

Before reverse factoring, the supplier uses the better of the two factoring schemes. By Proposition 4 this is non-recourse, with equilibrium $(w^*_{\mathcal N},q^*_{\mathcal N})$ , when $\mathbb C_{\mathcal N}<C_s\le\mathbb C_1$ , and recourse, with $(w^*_{\mathcal F},q^*_{\mathcal F})$ , when $C_s>\mathbb C_{\mathcal F}\vee\mathbb C_1$ . The retailer keeps the existing wholesale price $w_s$ and solves problem (13): maximize $\Pi_{\mathcal R}(w_s,\tau)$ over $\tau\ge0$ , subject to the supplier's acceptance (his reverse factoring profit is at least his existing one). $\mathbb C^{\max}_{\mathcal R}$ is the rating at which $\Lambda_{\mathcal F}=e^{-\eta_r t_2}$ , and $\Xi_{[0,z]}(x)=\max\{0,\min\{z,x\}\}$ .

Formalization targets

Goal: Proposition 6

(i) If $C_s\ge\mathbb C^{\max}_{\mathcal R}$ , reverse factoring is dominated by recourse factoring. (ii) If $\mathbb C_{\mathcal N}<C_s<\mathbb C^{\max}_{\mathcal R}$ , reverse factoring should be offered with

\tau^*_{\mathcal R}=\Xi_{[0,\tau_s]}(\tau^*_0),\qquad \lambda_r k(q)z(q)+\eta_r=2\eta_r e^{\lambda_r\tau^*_0},\quad w_s\bar F(q)=c_{\mathcal R}(\tau^*_0),

where $\tau_s=-\eta_r^{-1}\ln(1-\rho_r)$ with $w_s=w^*_{\mathcal N}$ in the non-recourse case, and $\tau_s=-\eta_r^{-1}\ln[(1-\rho_r)+(1-\rho_s)-e^{\eta_s t_2}]-t_2$ with $w_s=w^*_{\mathcal F}$ in the recourse case.

Milestones, in attack order

Eq. (12): the supplier's best response under reverse factoring.
Proposition 4: which factoring scheme is in force before reverse factoring.
§5.3, $\tau_s$ : acceptance holds exactly on $[0,\tau_s]$ .
§5.3, $\tau^*_0$ : the retailer's unconstrained profit is unimodal around $\tau^*_0$ .

A follow-on item states Corollary 3(ii): the retailer's profit strictly increases, and the supplier's profit is unchanged when $\tau^*_0\ge\tau_s$ .

Significance

Proposition 6 is the paper's prescription for program design. It says which suppliers should be offered reverse factoring: every supplier below the indifference rating $\mathbb C^{\max}_{\mathcal R}$ and above the non-recourse feasibility threshold. It also gives the extension in closed form, the unconstrained optimum clipped to the supplier's acceptance limit. Two consequences are drawn in the paper: non-recourse factoring is dominated once the extension is optimized, and reverse factoring may leave the supplier exactly as well off as before, so it is not necessarily a win-win (Corollary 3).

The proofs are in the paper's Online Appendix B and have not been machine-checked. A formal proof here produces a checked derivation of the projection formula from the model's primitives. It covers the strict-IFR analysis of the follower's response, the reduction of the acceptance constraint to an interval, and the unimodality of the retailer's objective. The same analysis of the pull game with an effective unit cost recurs across the supply chain finance literature.

Difficulty

The retailer's objective depends on $\tau$ through two opposing channels: the liquidity factor $2-e^{-\lambda_r\tau}$ increases, while expected sales $S(q_{\mathcal R}(\tau))$ decrease because the supplier's effective cost rises. Neither factor is concave in $\tau$ , and the objective need not be concave. The natural move, to set the derivative to zero and call the root a maximum, proves nothing without a sign analysis. That analysis needs the monotonicity of $k\cdot z$ along the implicitly defined response $q_{\mathcal R}(\tau)$ , which is where strict IFR enters. The acceptance constraint compares the supplier's profits in two different games (reverse factoring at $\tau$ against the existing equilibrium). Reducing it to $\tau\le\tau_s$ requires the supplier's best-response profit as an explicit increasing function of his quantity. Identifying the existing equilibrium requires Proposition 4, whose "adopted" compares equilibrium profits of two Stackelberg games.

Formalization scope

The model is a single Lean structure SupplyChainFactoring.Extension.Model. Demand is a probability measure on $\mathbb R$ with a density $f$ , and $\mathbb Z$ is an extended real. "Continuous p.d.f. with $f>0$ in $[0,\mathbb Z]$ " is read as continuity on $[0,\mathbb Z]$ , with $f=0$ outside the support. Credit functions $\rho,\eta$ are real functions constrained on $(C_{\min},C_{\max})$ . The finance derivations behind the profit functions (Eqs. (1), (5), (6), Lemma 1) are not formalized: the profit functions are the model.

Readings of informal words, each also recorded in the item's Formalization Note:

Best response: a maximizer of the supplier's profit over $q\ge0$ ; equilibrium: a best response pair from which no nonnegative wholesale price with a best response gives the retailer more. Neither is defined through first-order conditions.
Feasible: some $w\ge0$ with a best response gives the retailer positive profit; adopted (Proposition 4): feasible, with equilibrium supplier profit at least (non-recourse) or strictly above (recourse) the other feasible scheme's.
Thresholds "the unique value of $C_s$ that satisfies …" are hypotheses in exactly that form; $c_{\mathcal N}=p$ and $c_{\mathcal F}=p$ are cross-multiplied because $\Lambda_{\mathcal F}$ can be $\le0$ .
In (13) $w$ is fixed at $w_s$ (§5.3's first sentence, footnote 23). $\pi^*_{\mathcal R}$ is the supplier's best-response profit under reverse factoring at $(w_s,\tau)$ , and $\max\{\pi^*_{\mathcal F},\pi^*_{\mathcal N}\}$ is his profit in the existing equilibrium.
Dominated (Proposition 6(i)): at every $\tau\ge0$ and every $w$ , the supplier's reverse factoring best-response profit is at most his recourse one. Should be offered (6(ii)): $\tau^*_{\mathcal R}$ solves (13) and the retailer's profit is at least her existing equilibrium profit.
$\tau^*_0$ is a hypothesis: it and some $q\in(0,\mathbb Z)$ solve the paper's two equations (the paper does not argue existence). Its optimality "without the nonnegativity constraint" is stated as unimodality of $\Pi_{\mathcal R}$ on the set of real $\tau$ with $c_{\mathcal R}(\tau)<w$ .
Always increases (Corollary 3(ii)) is strict; may remain unchanged when $\tau^*_0\ge\tau_s$ is read as "is unchanged whenever $\tau^*_0\ge\tau_s$ ".

Three misprints of the paper are corrected: $\Xi_{[0,z]}(x)=0$ "if $x<z$ " is read as "if $x<0$ "; "the retailer's maximization problem in (16)" refers to (13); the middle line of the $\Pi_{\mathcal R}$ display on p. 6082 carries a stray factor $w$ , and the last line is used.

The hypotheses on $\tau^*_0$ cannot be met when $\lambda_r=0$ , and the goal then says nothing about the case, as in the paper. The existing equilibrium, $\tau_s$ and $\tau^*_0$ are never free parameters: $\tau_s$ is the paper's explicit formula, and the reduction of acceptance to $\tau\le\tau_s$ is a milestone to be proved, not an assumption. Every logarithm is applied to a quantity the hypotheses force positive. A formalization that assumed acceptance equivalent to $\tau\le\tau_s$ or assumed unimodality would be trivial and is excluded.

The pull game with an effective cost has the same structure as Cachon's pull contract without salvage value (platform items CachonPushPull.*), but those items assume IGFR demand with a salvage value, so they are not reused. Reusable infrastructure welcome: the strict-IFR lemmas ( $k$ , $k\cdot z$ and $k(q)-q$ increasing) and the explicit best response of a newsvendor-type follower.

Selected references

P. Kouvelis, F. Xu, A Supply Chain Theory of Factoring and Reverse Factoring, Management Science 67(10):6071–6088, 2021. https://doi.org/10.1287/mnsc.2020.3788
G. P. Cachon, The Allocation of Inventory Risk in a Supply Chain: Push, Pull, and Advance-Purchase Discount Contracts, Management Science 50(2):222–238, 2004. https://doi.org/10.1287/mnsc.1030.0190
D. A. Wuttke, E. S. Rosenzweig, H. S. Heese, An Empirical Analysis of Supply Chain Finance Adoption, Journal of Operations Management 65(3):242–261, 2019. https://doi.org/10.1002/joom.1023

6 thms3 active usersReviewed

Completed

Dynamic Programming Operations Research Probability·Captain: mikedeng1

On the Optimality of Generalized (s, S) Policies: A Generalized (s, S) Policy Is Optimal in Every Period of the Finite-Horizon Inventory ProblemResearch Paper

Motivation

In a periodic-review inventory system a manager observes the stock level before ordering, decides how much to order, and then faces random demand. When ordering costs a fixed setup charge plus a constant price per unit, Scarf (1960) proved that an $(s,S)$ policy is optimal in every period of a finite-horizon problem: order up to $S$ when the stock falls below $s$ , otherwise order nothing. Real ordering costs are often not of this form. Quantity discounts, a choice between production facilities with different setup and marginal costs, or a supplier whose price schedule falls with volume all give an ordering cost that is concave and increasing but not "setup plus linear". Karlin had analysed the single-period problem with such costs; Porteus (1971) gave the first multiperiod result with random demand.

Timeline:

Scarf (1960): $(s,S)$ optimality for setup-plus-linear ordering cost, via $K$ -convexity of the expected cost-to-go.
Veinott (1966): an alternative proof of $(s,S)$ optimality under different conditions (quasi-convex one-period costs).
Porteus (1971): for concave increasing ordering costs and demand with a one-sided Pólya density, a generalized $(s,S)$ policy is optimal in every period; when the cost is piecewise linear with $r$ pieces it is an $(s,S)_r$ policy with at most $r$ reorder levels.

Setting

The ordering cost $c : [0,\infty) \to \mathbb R$ is concave, nondecreasing, and $c(0) = 0$ . For $z > 0$ , $C_2(z)$ is the supporting line of $c$ at $z$ with the smallest intercept, written as a pair (slope, intercept) $(\kappa, K)$ . The set of slopes that occur is $C$ , and $K_\kappa$ is the intercept belonging to slope $\kappa \in C$ , so $c(z) = \min_{\kappa \in C}\{K_\kappa + \kappa z\}$ for $z > 0$ . The limits $(c_0, K_0) = \lim_{z \downarrow 0} C_2(z)$ and $(c_\infty, K_\infty) = \lim_{z\to\infty} C_2(z)$ are assumed to exist.

Demands in successive periods are i.i.d. with density $\varphi$ . A function $\varphi$ is $PF_n$ if $0 < \int\varphi < \infty$ and $\det[\varphi(x_i - t_j)]_{i,j\le k} \ge 0$ for all $k \le n$ and increasing $x_1<\dots<x_k$ , $t_1<\dots<t_k$ ; it is a one-sided Pólya density if it is $PF_n$ for every $n$ , integrates to $1$ and vanishes on $(-\infty,0)$ . Exponential and Erlang densities are examples.

With holding-and-shortage cost $m$ (PF-integrable, bounded below), terminal cost $f_0$ , discount factor $0 \le \alpha \le 1$ , and convolution $(f*\varphi)(y) = \int f(y-x)\varphi(x)\,dx$ , the value functions are

h_n = m * \varphi + \alpha\, f_{n-1} * \varphi, \qquad f_n(x) = \inf_{y \ge x}\{c(y-x) + h_n(y)\},

where $n$ counts the periods remaining. $Y_n(x)$ is the set of minimizers $S \ge x$ . A generalized $(s,S)$ policy is a function $y$ with $y(x) = x$ for $x \ge s$ and $y(z) \ge y(x) \ge S \ge s$ for $z < x < s$ : no order above $s$ , and below $s$ an order-up-to level that is at least $S$ and does not increase with the starting stock.

Two function classes carry the argument. $f$ is non- $K$ -decreasing on $X$ if $f(x) \le f(y) + K$ for $x \le y$ in $X$ . For $K \ge 0$ , $C_a(K)$ consists of the piecewise continuous, PF-integrable functions with $f(x)\to\infty$ as $|x|\to\infty$ that are nonincreasing on $(-\infty,a)$ or $(-\infty,a]$ and non- $K$ -decreasing on the rest of the line. $C(K)$ is its continuous part. With $G_{\kappa n} = \kappa\cdot + h_n$ , the assumptions A1–A5 of §VI tie $m$ and $f_0$ to $c_0$ , $c_\infty$ and the $K_\kappa$ .

Formalization targets

Goal: Theorem 3

Under the standing assumptions and A1–A5, for every $n \ge 1$ the convolution $f_{n-1}*\varphi$ exists and

\exists\, s, S,\ \exists\, y \text{ generalized } (s,S) \text{ policy}: \quad y(x) \in Y_n(x) \ \ \forall x \in \mathbb R.

The statement fixes no numbers: $s$ and $S$ depend on $n$ and on the data.

Milestones

Lemma 9: $\bigcup_a C_a(K)$ equals the class of quasi- $K$ -convex, piecewise continuous, PF-integrable functions tending to $\infty$ as $|x| \to \infty$ .
Lemma 1: every $f \in C(K)$ has reals $s \le S$ with $S$ a global minimizer, $f > f(S) + K$ on $(-\infty,s)$ , $f$ nonincreasing there, and $f$ non- $K$ -decreasing on $[s,\infty)$ .
Lemma 5: for continuous $g$ , $f(x) = \int_0^\infty g(x-t)\lambda e^{-\lambda t}dt$ is $C^1$ with $f' = \lambda(g-f)$ .
Lemma 6: $g*\varphi$ is continuous and $C^1$ off a finite set for a one-sided Pólya $\varphi$ .
Lemma 10 and Theorem 1: $f \in C_a(K) \Rightarrow f*\varphi \in C(K)$ , first for exponential $\varphi$ , then for every one-sided Pólya density.
Theorem 2: if every $G_{\kappa n} \in C(K_\kappa)$ and every $Y_n(x) \ne \emptyset$ , a generalized $(s,S)$ policy is optimal in period $n$ .
Lemma 2: $f_n(x) \le f_n(y) + c(y-x)$ for $x \le y$ .
Lemma 3: the inductive step producing the hypotheses of Theorem 2 from properties of $f_{n-1}$ .

Significance

The result extends $(s,S)$ -type structure from setup-plus-linear to arbitrary concave increasing ordering costs, which covers quantity discounts and multi-facility production. When $c$ is piecewise linear with $r$ pieces, the optimal policy is an $(s,S)_r$ policy described by at most $r$ reorder points and order-up-to levels. That is a finite-dimensional family, which makes computing policies tractable. The class $C(K)$ and its closure under Pólya convolution (Theorem 1) are statements about functions of one real variable, independent of the inventory model. Quasi- $K$ -convexity extends both $K$ -convexity and quasi-convexity (Lemma 8 of the paper).

The theorem is classical and proved on paper; no machine-checked version is known. Its appendix leaves several steps as "easily proved by contradiction", which a formal proof has to fill in. The platform has Bertsekas's $K$ -convex $(s,S)$ lemma (BertsekasDP.kconvex_sS_structure, a result about $K$ -convex rather than $C(K)$ functions), but no Pólya frequency functions, no quasi- $K$ -convexity, and no concave-cost inventory model.

Difficulty

The obvious route copies Scarf: show that the cost-to-go is $K$ -convex and that $K$ -convexity survives taking expectations. With a concave ordering cost there is no single $K$ , and the relevant functions $G_{\kappa n}$ are generally not $K_\kappa$ -convex. The weaker property that does hold, membership in $C(K_\kappa)$ , is not preserved by convolution with an arbitrary density. It is preserved by one-sided Pólya densities, and Theorem 1 is the step that shows this: exponential kernels come first (via the differential identity (23)), and the general case needs the Schoenberg representation of one-sided Pólya densities as limits of convolutions of exponentials. The second difficulty is combining the different slopes $\kappa \in C$ into one policy (Theorem 2). Separate $(s,S)$ pairs for each $\kappa$ do not by themselves give a monotone policy.

Formalization scope

All functions are ℝ → ℝ; the ordering cost is used only on $[0,\infty)$ . The demand density is a function, not a measure; convolution is the Lebesgue integral over $\mathbb R$ . $PF_n$ uses Matrix.det over Fin k. The value functions are defined by structural recursion on $n : \mathbb N$ with $f_0$ the terminal cost; $h_n$ is used for $n \ge 1$ . $Y_n(x)$ is defined by the optimality inequality, never through the infimum. $G_{\kappa n}$ is defined by the paper's identity (7), $\kappa y + h_n(y)$ . $R^- = (-\infty,0)$ is open, and "increasing" is read as nondecreasing. Slopes in $C$ are written $\kappa$ to separate them from the cost function $c$ .

Added hypotheses and conventions:

$m$ piecewise continuous. The paper uses this without stating it (proof of Lemma 3). It is a hypothesis of Lemma 3 and Theorem 3.
Real-valued $f_n$ in Lemma 2. Following the convention of §X, Lemma 2 assumes each infimum defining $f_n$ is over a set bounded below.
Measurability of $m$ and $f_0$ (§X) is implied by their piecewise continuity and is not stated separately.

Lean returns $0$ for an infimum over a set unbounded below and for the integral of a non-integrable function. The goal therefore concludes that $f_{n-1}*\varphi$ exists and that $Y_n(x)$ is nonempty (so the infimum is a minimum); it does not assume these. It also does not quantify over arbitrary functions satisfying a Bellman equation or over an arbitrary set-valued $Y$ . Everything is built from the data $(c, m, \varphi, \alpha, f_0)$ . The class $C(K)$ includes PF-integrability and coercivity, without which Lemma 1 fails.

Welcome contributions: Pólya frequency functions and the exponential special cases (the exponential density is $PF_\infty$ ), Leibniz-rule lemmas for exponential kernels, the theory of $C(K)$ and quasi- $K$ -convex functions (reusable for other inventory models), and a formal Schoenberg representation (Theorem 6 of the paper, cited there and needed for Theorem 1). Theorems 4 and 5 (nonstationary and partial-backlogging extensions) are not part of this mission.

Selected references

E. L. Porteus, On the Optimality of Generalized (s, S) Policies, Management Science 17(7):411–426, 1971. https://doi.org/10.1287/mnsc.17.7.411
H. Scarf, The Optimality of (S, s) Policies in the Dynamic Inventory Problem, in Mathematical Methods in the Social Sciences, Stanford University Press, 1960.
A. F. Veinott Jr., On the Optimality of (s, S) Inventory Policies: New Conditions and a New Proof, SIAM Journal on Applied Mathematics 14(5):1067–1083, 1966. https://doi.org/10.1137/0114086
I. J. Schoenberg, On Pólya Frequency Functions I. The Totally Positive Functions and their Laplace Transforms, Journal d'Analyse Mathématique 1:331–374, 1951. https://doi.org/10.1007/BF02790092
S. Karlin, Total Positivity, Volume 1, Stanford University Press, 1968.

13 thms3 active usersReviewed

Completed

Dynamic Programming Operations Research Probability·Captain: mikedeng1

Optimal Policy for a Multi-Product, Dynamic, Nonstationary Inventory Problem: The Base Stock Ordering Policy Is OptimalResearch Paper

Motivation

An inventory manager who stocks many products, faces random demand and pays ordering, holding and shortage costs must decide each period how much of each product to order. In general the optimal decision depends on the whole state and is found by solving a dynamic programme, which becomes impractical as the number of products grows. Myopic (or base stock) policies avoid this: in each period they aim at a target level computed from that period's data alone. Knowing when such a policy is optimal over an infinite horizon tells a practitioner when the multi-period problem decouples into a sequence of one-period problems.

Arthur F. Veinott, Jr. gave such conditions in Optimal Policy for a Multi-Product, Dynamic, Nonstationary Inventory Problem (Management Science 12(3):206–222, 1965). Earlier results of this type were for a single product (the paper cites Karlin, Management Science 6(3), 1960, Bellman–Glicksberg–Gross, Management Science 2(1), 1955, Iglehart–Karlin 1962, and the Arrow–Karlin–Scarf volume of 1958); Veinott's model allows several products, several demand classes, costs and demand distributions that change over time, general ordering constraints and general stock dynamics (backlogging, lost sales, and mixtures), and it does not use the functional equation of dynamic programming. Instead, the proofs analyse the inventory process directly.

Setting

There are $n$ products and $m$ demand classes. Vectors are compared componentwise: $u \le v$ means $u_j \le v_j$ for all $j$ . In period $i = 1, 2, \dots$ the manager observes the inventory vector $x_i \in X_i \subseteq \mathbb{R}^n$ (negative coordinates are backlogs) and orders up to a vector $y_i \in Y_i \subseteq \mathbb{R}^n$ , subject to $y_i \ge q_i(x_i)$ , where $q_i$ is a vector of extended-real functions (for instance $q_i(x) = x$ forbids disposal). A random demand vector $D_i$ with law $\Phi_i$ and values in a Borel set $\mathfrak{D}_i \subseteq \mathbb{R}^m$ then occurs, and the next inventory vector is $x_{i+1} = s_i(y_i, D_i) \in X_{i+1}$ . The demands $D_1, D_2, \dots$ are independent. Ordering $y_i - x_i$ costs $c_i \cdot (y_i - x_i)$ , the holding and shortage cost is $g_i(y_i, D_i)$ , and $\alpha_i \ge 0$ is the discount factor of period $i$ .

Regrouping the ordering costs gives the one-period cost

W_i(y,t) = c_i\, y + g_i(y,t) - \alpha_i\, c_{i+1}\, s_i(y,t), \qquad G_i(y) = \int_{\mathfrak{D}_i} W_i(y,t)\, d\Phi_i(t),

with discount weights $\beta_1 = 1$ and $\beta_i = \alpha_1 \cdots \alpha_{i-1}$ . The integrals are assumed finite, and $G_i \ge \gamma_i$ with $\sum_i |\beta_i \gamma_i| < \infty$ . An ordering policy $\bar Y$ chooses $y_i$ as a Borel function of the past; it is feasible if $y_i \in Y_i$ and $y_i \ge q_i(x_i)$ for every possible history. Its cost is

f(x_1 \mid \bar Y) = \sum_{i=1}^\infty \beta_i\, E\, G_i(y_i) \in (-\infty, +\infty],

and a feasible policy of least cost is optimal.

Let $\bar y_i$ minimize $G_i$ over $Y_i$ . When $\bar y_i$ is not attainable from $x$ , the minimal feasible level $w_i(x)$ is the least element of $Y_i \cap \{y : y \ge q_i(x),\ y \ge \bar y_i\}$ . The base stock ordering policy orders up to $\bar y_i$ if $q_i(x_i) \le \bar y_i$ and up to $w_i(x_i)$ otherwise.

Formalization targets

The hypotheses are: (3a) $\bar y_i \in Y_i$ minimizes $G_i$ over $Y_i$ ; (3b) $q_{i+1}(s_i(\bar y_i, t)) \le \bar y_{i+1}$ for $t \in \mathfrak{D}_i$ ; (3c) $Y_i$ is closed and linearly ordered by $\le$ ; (3d) $G_i$ and $s_i(\cdot, t)$ are nondecreasing on $\{y \in Y_i : y \ge \bar y_i\}$ , and $q_i$ is nondecreasing where $q_i(x) \not\le \bar y_i$ .

Goal: Theorem 3.2

Under (3a)–(3d), the base stock ordering policy

\bar Y_i^*(H_i^*) = \begin{cases} \bar y_i, & q_i(x_i^*) \le \bar y_i, \\ w_i(x_i^*), & q_i(x_i^*) \not\le \bar y_i \end{cases}

is feasible and optimal: $f(x_1 \mid \bar Y^*) \le f(x_1 \mid \bar Y)$ for every feasible $\bar Y$ .

Milestones

A nonempty, closed, linearly ordered, bounded-below subset of $\mathbb{R}^n$ has a least element (p. 212); hence $w_i(x)$ exists and equals $\bar y_i$ when $q_i(x) \le \bar y_i$ .
$w_i$ is nondecreasing where $q_i(x) \not\le \bar y_i$ (p. 214).
Once $q_k(x_k^*) \le \bar y_k$ , the base stock policy orders up to $\bar y_i$ for all $i \ge k$ .
Theorem 3.1: under (3a) and (3b), if $q_1(x_1) \le \bar y_1$ , ordering up to $\bar y_i$ in every period is optimal, with cost $\sum_i \beta_i G_i(\bar y_i)$ .
The coupling (3.1): before the first period $T$ with $q_T(x_T^*) \le \bar y_T$ ,

\bar y_i < y_i^* = w_i(x_i^*) \le w_i(x_i) \le y_i.

Pathwise dominance: $G_i(y_i^*) \le G_i(y_i)$ for every $i$ and every possible demand path.
The reduction behind (2.3): $E\, W_i(y_i, D_i) = E\, G_i(y_i)$ , by independence of $y_i$ and $D_i$ .

Significance

The theorem shows that under (3a)–(3d) the infinite-horizon, nonstationary, multi-product problem is solved by one-period optimization: compute $\bar y_i$ from $G_i$ alone, and when it is unreachable order the least feasible amount. No value function is computed. It covers backlogging and lost sales, products stocked in fixed proportions, and time-varying cost and demand data, and Theorem 3.1 alone settles the frequent case in which the initial stock is small.

The result is proved in the paper. To our knowledge it has not been machine-checked: this mission produces a Lean model of a general stochastic, infinite-horizon, multi-product inventory problem (feasible policies, the expected discounted cost with $+\infty$ allowed), and a checked proof that a myopic policy is optimal in it. The model and its cost are reusable for other base stock and myopic optimality results.

Difficulty

The obvious argument would compare the base stock policy with an arbitrary policy period by period using (3a) alone. That fails once $\bar y_i$ is unreachable. The base stock policy then holds less stock than $\bar y_i$ would require, and it has to be shown that no other policy can reach a lower-cost level later. The proof couples the two trajectories along every demand path, using the monotonicity in (3d) and the linear order of $Y_i$ from (3c), until the base stock level becomes attainable, after which (3b) keeps it attainable. The formal difficulties are:

the existence and monotonicity of the least element $w_i(x)$ in a closed chain of $\mathbb{R}^n$ ;
the measurability of the base stock policy, which is part of its feasibility;
the passage from pathwise dominance to the expected discounted cost when the cost may be $+\infty$ .

Formalization scope

Periods are 0-based in Lean (Lean period $k$ is the paper's period $k+1$ ). Vectors are Fin n → ℝ with the product order; $q_i$ takes values in Fin n → EReal. Policies are functions of the past demands. The paper shows on p. 219 that this loses no generality once $x_1$ is fixed. The cost is excess, a $[0,\infty]$ -valued series of lower Lebesgue integrals of $\beta_i(G_i(y_i) - \gamma_i)$ , plus the finite real $\sum_i \beta_i\gamma_i$ , taken in EReal. A divergent series therefore gives $+\infty$ and never the junk value $0$ . "Minimal element" is IsLeast. The $G_i$ in the statements is the integral of $W_i$ built from the data, and the policy in the goal is constructed from $\bar y$ , $q$ , $w$ and $s$ . Neither is an arbitrary object satisfying the conclusion. The goal concludes optimality, which includes feasibility: a pathwise or conditional statement would not be the theorem.

Hypotheses added relative to the page, each used by the paper without being stated:

Order feasibility: from every $x \in X_i$ some $y \in Y_i$ with $y \ge q_i(x)$ exists (p. 212 asserts the set defining $w_i(x)$ has a minimal element, which needs it nonempty). The least-element lemma likewise assumes $A$ nonempty.
(3d)'s $q$ -clause in one-sided form: if $x \le x'$ in $X_i$ and $q_i(x) \not\le \bar y_i$ , then $q_i(x) \le q_i(x')$ . This is the form the proof on p. 214 uses; monotonicity on the region $\{q_i(x) \not\le \bar y_i\}$ alone admits a counterexample to Theorem 3.2.
Integrability of $W_i(y_i, D_i)$ in the milestone $E W_i = E G_i$ .
Borel measurability of $q_i$ on all of $\mathbb{R}^n$ rather than on $X_i$ (a harmless strengthening).

A complete development needs: least elements of closed chains in $\mathbb{R}^n$ ; measurability of the least-element selection $x \mapsto w_i(x)$ ; a Fubini/independence argument for $E\,W_i(y_i,D_i)=E\,G_i(y_i)$ ; and monotone summation of lower integrals. The least-element lemma and the cost encoding are reusable beyond this mission. Proofs of any milestone are welcome, as are alternative arguments.

Selected references

A. F. Veinott, Jr., Optimal Policy for a Multi-Product, Dynamic, Nonstationary Inventory Problem, Management Science 12(3):206–222, 1965. https://doi.org/10.1287/mnsc.12.3.206
R. Bellman, I. Glicksberg, O. Gross, On the Optimal Inventory Equation, Management Science 2(1):83–104, 1955. https://doi.org/10.1287/mnsc.2.1.83
S. Karlin, Dynamic Inventory Policy with Varying Stochastic Demands, Management Science 6(3):231–258, 1960. https://doi.org/10.1287/mnsc.6.3.231

11 thms3 active usersReviewed

Completed

Operations Research Optimization Probability·Captain: mikedeng1

On the Value of Mix Flexibility and Dual Sourcing in Unreliable Newsvendor Networks 1: The Risk-Neutral Flexibility Premium Is Nonnegative for Every ReliabilityResearch Paper

Motivation

A firm that sells several products must decide, before demand is known, how much production capacity to build and of what kind. Dedicated capacity makes one product; flexible capacity makes any of them. The classic argument for flexibility is demand pooling: capacity that can follow demand to whichever product needs it wastes less than capacity locked to one product (Fine and Freund 1990; Van Mieghem 1998).

When capacity itself is unreliable, as with a supplier that may fail to deliver, a plant that may be disrupted, or a batch that may be rejected, flexibility has a second face. A single flexible resource concentrates the firm's supply in one place, so one failure removes all of it, whereas several dedicated resources rarely fail together. This resource-aggregation effect works against flexibility. Tomlin and Wang (2005) set up a newsvendor network in which both effects are present and ask when a firm should pay more for flexible capacity than for dedicated capacity. Their first answer (Proposition 1) is that a risk-neutral firm facing equal reliabilities and costs never loses by choosing flexibility, whatever the joint distribution of demand. This mission formalizes that answer.

Setting

There are $N$ products with a common unit contribution margin $p>0$ . The demand vector $\tilde X=(\tilde X_1,\dots,\tilde X_N)$ is random, nonnegative and integrable; its total is $\tilde X_{N+1}=\tilde X_1+\dots+\tilde X_N$ .

Two networks are compared. In the dedicated network SD, resource $n\in\{1,\dots,N\}$ makes only product $n$ and has marginal total cost $c>0$ . In the flexible network SF, a single resource, labelled $N+1$ , makes every product and has marginal total cost $c_{N+1}$ .

Every resource $j$ is unreliable with a Bernoulli yield $\tilde Y_j\in\{0,1\}$ , $\mathbb P(\tilde Y_j=1)=\theta$ . The common reliability is $\theta\in[0,1]$ , the yields are mutually independent, and they are independent of demand. Investing $K_j\ge 0$ in resource $j$ delivers capacity $\tilde Y_jK_j$ and costs $(\lambda+(1-\lambda)\tilde Y_j)c_jK_j$ : the firm pays the committed cost $\lambda c_j$ per unit ordered and a further $(1-\lambda)c_j$ per unit delivered, with $\lambda\in[0,1]$ .

The realized profits are

W^{SD}(K)=\sum_{n=1}^N\Big(-(\lambda+(1-\lambda)\tilde Y_n)cK_n+p\min\{\tilde X_n,\tilde Y_nK_n\}\Big),

W^{SF}(K_{N+1})=-(\lambda+(1-\lambda)\tilde Y_{N+1})c_{N+1}K_{N+1}+p\min\{\tilde X_{N+1},\tilde Y_{N+1}K_{N+1}\},

and a risk-neutral firm maximizes the expected profit $V^{SD}_{RN}(K)=\mathbb E[W^{SD}(K)]$ or $V^{SF}_{RN}(K_{N+1})=\mathbb E[W^{SF}(K_{N+1})]$ over nonnegative investments. Let $V^{SD,*}$ and $V^{SF,*}$ be the optimal values. SF is (weakly) preferred if $V^{SF,*}\ge V^{SD,*}$ .

The indifference cost $c^I_{N+1}$ is a value of $c_{N+1}$ at which $V^{SF,*}=V^{SD,*}$ , and the flexibility premium is $\Delta=(c^I_{N+1}-c)/c$ . The firm prefers SF as long as $c_{N+1}\le(1+\Delta)c$ .

The $\alpha$ -expected shortfall of a random variable $Z$ is, for $\alpha\in(0,1)$ and the lower quantile $x_{(\alpha)}=\inf\{x:\mathbb P(Z\le x)\ge\alpha\}$ ,

ES_\alpha(Z)=-\frac1\alpha\Big(\mathbb E\big[Z\mathbf 1\{Z\le x_{(\alpha)}\}\big]+x_{(\alpha)}\big(\alpha-\mathbb P(Z\le x_{(\alpha)})\big)\Big).

Formalization targets

Goal: Proposition 1

For any demand random vector $\tilde X$ :

$\Delta_{RN}\ge 0$ for all $0\le\theta\le 1$ , that is, SF is preferred whenever $c_{N+1}\le c$ ;

0\le\theta\le\frac{\lambda c}{p-(1-\lambda)c}\ \Longrightarrow\ \Delta_{RN}=0;

$\Delta_{RN}=0$ if $\rho_X=\mathbf 1$ , i.e. all pairwise demand correlations equal $1$ .

No distributional form of demand is fixed and no constant is hard-coded beyond the paper's threshold.

Milestones

(9): the closed form of $V^{SF}_{RN}$ .
(10)–(11), (12)–(13): the optimal investments are critical fractiles

F_{X_{N+1}}(K^*_{N+1})=1-\frac{(\lambda+(1-\lambda)\theta)c_{N+1}}{\theta p},\qquad F_{X_n}(K^*_n)=1-\frac{(\lambda+(1-\lambda)\theta)c}{\theta p},

and the optimal values are $\theta p$ times partial expectations of demand.

(A-1) in expected-shortfall form: with $\alpha=1-(\lambda+(1-\lambda)\theta)c/(\theta p)\in(0,1)$ ,

V^{SF,*}\ge V^{SD,*}\ \text{at}\ c_{N+1}=c\iff \alpha\Big(\sum_n ES_\alpha(\tilde X_n)-ES_\alpha\Big(\sum_n\tilde X_n\Big)\Big)\ge 0 .

Subadditivity of $ES_\alpha$ (Acerbi and Tasche 2002).
The positivity threshold of part 2: investing is worthwhile iff $\theta>\lambda c/(p-(1-\lambda)c)$ .
Correlation $1$ implies $\tilde X_n=a\tilde X_1+b$ with $a>0$ , and $ES_\alpha(aX+b)=aES_\alpha(X)-b$ .

Significance

Proposition 1 separates the two effects of flexibility under unreliable supply. It shows that for a risk-neutral firm the demand-pooling benefit together with an upside effect of aggregation (one flexible resource succeeds more often than all dedicated ones together) always outweighs the downside aggregation risk. Even with no pooling benefit at all (perfectly correlated demand) the firm is indifferent, not averse. The later results of the paper (loss aversion, CVaR, dual sourcing) are measured against this baseline: a negative premium can appear only once the firm is risk-averse. The expected-shortfall form links newsvendor optimal values to a coherent risk measure, a connection that recurs in inventory risk analysis.

The result is proved in the paper, with a proof that cites Acerbi and Tasche (2002) for two properties of expected shortfall. No machine-checked version exists. A formalization adds three things: a proof for general demand distributions (the paper assumes a joint density and uses the continuous form of expected shortfall); a Lean development of Acerbi–Tasche expected shortfall for general integrable random variables, including subadditivity and affine equivariance; and a reusable model of newsvendor networks with Bernoulli yields and committed costs.

Difficulty

The newsvendor steps (9)–(13) are single-variable concave optimization, but they must be done without a density: the distribution function of total demand may have atoms and flat pieces, so the critical fractile need not be attained or may be attained on an interval, and optimal values must be expressed through lower quantiles. Subadditivity of expected shortfall is the heart of part 1 and is not elementary in the general (atomic) case, which is exactly why the correction term $x_{(\alpha)}(\alpha-\mathbb P(Z\le x_{(\alpha)}))$ appears. Part 3 requires identifying correlation $1$ with almost-sure positive affine dependence, which rests on the equality case of the Cauchy–Schwarz inequality in $L^2$ , and then handling nonnegativity constraints on the investments that the affine change of variables may violate. The obvious shortcut of computing everything from densities is not available, because the goal is stated for every demand vector and part 3 is incompatible with a joint density when $N\ge 2$ .

Formalization scope

Randomness lives on one probability space $(\Omega,\mu)$ ; demand is X : Ω → Fin N → ℝ and yields are Y : Ω → Fin (N + 1) → ℝ, where dedicated resource $n$ is Fin.castSucc n and the flexible resource $N+1$ is Fin.last N. Expectations are Bochner integrals and probabilities are μ.real. The standing assumptions are: $p>0$ , $c>0$ , $\lambda,\theta\in[0,1]$ ; demands measurable, almost surely nonnegative and integrable (integrability is needed for expected shortfall and makes every profit integrable); yields measurable, $\{0,1\}$ -valued almost surely with $\mathbb P(\tilde Y_j=1)=\theta$ , mutually independent, and independent of demand (the paper states the last in Appendix E). The paper's joint density of demand is deliberately not assumed.

The premium $\Delta$ and the indifference cost are not defined as real numbers, because Definition 1's indifference cost need not exist or be unique (for $\theta$ below the threshold both optimal values are $0$ for every $c_{N+1}$ near $c$ ). " $\Delta\ge 0$ " is encoded as "SF is weakly preferred for every $c_{N+1}\le c$ ", and " $\Delta=0$ " as "SF and SD are each weakly preferred to the other at $c_{N+1}=c$ ". Weak preference $V^{SF,*}\ge V^{SD,*}$ is stated as: every nonnegative SD investment is matched by some nonnegative SF investment; no real supremum is taken. Quantiles $F^{-1}$ in (10) and (12) appear only as parameters with the hypothesis $F(K^*)=$ fractile. Part 3 adds square integrability and positive variances, the conditions under which correlation coefficients exist; the threshold milestone adds almost surely positive demand and $N\ge 1$ for its "if" direction. When $p\le(1-\lambda)c$ the Lean value of the threshold is $\le 0$ , so part 2 then covers only $\theta=0$ , where it is true.

A formalization that assumed a joint density, took $\Delta$ as a free real satisfying Definition 1, or defined optimal values as real suprema over all of $\mathbb R^N$ would make parts of the goal vacuous or trivial; each is ruled out above.

Needed infrastructure: single-variable newsvendor optimality for general distributions; the Acerbi–Tasche expected shortfall with subadditivity and affine equivariance; the equality case of Cauchy–Schwarz for correlation. The expected-shortfall and correlation lemmas are reusable well beyond this mission, and contributions of them are especially welcome. Out of scope: the loss-averse and CVaR analyses (Propositions 2–3, §3.2–3.3), the perfect-reliability result (Proposition 4, a separate mission), the dual-sourcing networks (§4) and all numerical results.

Selected references

B. Tomlin and Y. Wang, On the value of mix flexibility and dual sourcing in unreliable newsvendor networks, Manufacturing & Service Operations Management 7(1):37–57, 2005. https://doi.org/10.1287/msom.1040.0063
C. Acerbi and D. Tasche, On the coherence of expected shortfall, Journal of Banking & Finance 26(7):1487–1503, 2002. https://doi.org/10.1016/S0378-4266(02)00283-2
C. H. Fine and R. M. Freund, Optimal investment in product-flexible manufacturing capacity, Management Science 36(4):449–466, 1990. https://doi.org/10.1287/mnsc.36.4.449
J. A. Van Mieghem, Investment strategies for flexible resources, Management Science 44(8):1071–1078, 1998. https://doi.org/10.1287/mnsc.44.8.1071

10 thms2 active usersReviewed

Completed

Operations Research Optimization Probability·Captain: mikedeng1

On the Value of Mix Flexibility and Dual Sourcing in Unreliable Newsvendor Networks 2: Under Perfect Reliability the Flexibility Premium Is Nonnegative for Every Nondecreasing UtilityResearch Paper

Motivation

A manufacturer that makes several products must decide, before demand is known, how much capacity to buy. It can buy dedicated capacity, one resource per product, or a single flexible resource that can make every product. Flexible capacity pools demand: a surplus of one product's demand can be served by capacity that would otherwise sit idle. A common intuition in the operations literature holds that a flexible strategy is preferable to a dedicated one when the unit costs are equal, and much of that literature therefore assumes the flexible resource costs more (for example Van Mieghem 1998).

Tomlin and Wang (2005) examine when this intuition is valid for firms that are not risk neutral and whose resources may fail. Their answer has two halves. A risk-neutral firm always values flexibility, whatever the reliability of its resources (their Proposition 1). A firm with perfectly reliable resources also always values flexibility, whatever its attitude to risk, as long as it prefers more wealth to less (their Proposition 4). When neither condition holds, dedicated capacity can be strictly preferred (their Remark 1 and numerical study). This mission formalizes the second half.

Setting

There are $N$ products with a common contribution margin $p>0$ . The random demand vector is $\tilde X=(\tilde X_1,\dots,\tilde X_N)$ , nonnegative, with an arbitrary joint distribution on a probability space. The firm has initial wealth $w_0$ .

In the dedicated network SD, the firm invests $K_n\ge 0$ in a resource that can make only product $n$ , at marginal total cost $c>0$ per unit. With perfectly reliable resources the whole investment is delivered, and the terminal wealth is

w^{SD}(K)=w_0+p\sum_{n=1}^N\min\{\tilde X_n,K_n\}-c\sum_{n=1}^N K_n .

In the flexible network SF, the firm invests $K_{N+1}\ge0$ in one resource that can make every product, at marginal total cost $c_{N+1}$ , and the terminal wealth is

w^{SF}(K_{N+1})=w_0+p\min\Big\{\sum_{n=1}^N\tilde X_n,K_{N+1}\Big\}-c_{N+1}K_{N+1}.

The firm chooses its investment to maximize one of three objectives of terminal wealth $W$ , with profit $\tilde W=W-w_0$ :

an expected utility $E[u(W)]$ , where $u$ ranges over $U_1$ , the set of utility functions that are nondecreasing in wealth;
the loss-averse objective $V_{LA}=w_0+E[\tilde W^+-\beta\tilde W^-]$ with $\beta\ge 1$ ;
the CVaR objective $V_{CVaR_\eta}=w_0+\max_v\{v+\tfrac1\eta E[\min\{\tilde W-v,0\}]\}$ with $\eta\in(0,1]$ , the mean of the left $\eta$ -tail of wealth.

SF is (weakly) preferred when its optimal objective value is at least that of SD. The flexibility premium is $\Delta=(c^I_{N+1}-c)/c$ , where the indifference cost $c^I_{N+1}$ is a flexible cost at which the firm is indifferent between the networks; the firm prefers SF as long as $c_{N+1}\le(1+\Delta)c$ .

Formalization targets

Goal: Proposition 4

With perfectly reliable resources and any demand distribution, $\Delta\ge 0$ for every $u\in U_1$ , for the loss-averse objective and for the CVaR objective. In the formalization: for every $c_{N+1}\le c$ ,

\forall K\ge 0\ \exists K_{N+1}\ge 0:\quad \mathcal V^{SD}(K)\le\mathcal V^{SF}(K_{N+1})

for $\mathcal V$ each expected utility with $u$ nondecreasing, and the loss-averse objective; for CVaR the same with the threshold $v$ quantified jointly with the investment.

Milestones

(A-4)–(A-6): at equal cost, investing $\sum_nK_n$ in the flexible resource gives a terminal wealth at least that of SD, for every demand realization.
The SF wealth first-order stochastically dominates the SD wealth: $F_{W^{SF}}\le F_{W^{SD}}$ .
$E[u(w^{SD}(K))]\le E[u(w^{SF}(\sum_nK_n))]$ for every nondecreasing $u$ .
The loss-averse objective is the expected utility of a nondecreasing piecewise-linear utility with breakpoint $w_0$ .
The CVaR comparison $V^{SD}_{CVaR}(K)\le V^{SF}_{CVaR}(\sum_nK_n)$ .

Significance

Proposition 4 shows that the intuition "flexibility is worth at least as much as dedicated capacity at the same price" survives any monotone risk attitude and any demand distribution, provided supply is reliable. Combined with Proposition 1 it isolates the interaction of risk aversion and unreliable supply as the only source of a negative flexibility premium, which is the paper's Remark 1 and the organizing message of its numerical study. The result requires no concavity, differentiability or distributional assumption, so it applies to the loss-averse and CVaR objectives used throughout the paper.

The result is proved in the paper (Appendix A); no machine-checked version is known. A formalization produces a reusable statement of the model, a pathwise pooling inequality, and the passage from a pathwise comparison of two random variables on one probability space to comparisons of expected utilities and of CVaR, which recurs in capacity-pooling and inventory-pooling arguments.

Difficulty

The pathwise inequality is elementary. The work lies in the passage from it to the objectives. The paper cites Levy (1992) for both the expected-utility and the CVaR comparison; the first holds for every nondecreasing $u$ , including discontinuous ones, and the second concerns a maximum over a real threshold that is not a priori attained. A formal proof must also make sure every expectation involved is a genuine integral: the utility is arbitrary, so the expected utility is finite only because, for a fixed nonnegative investment and nonnegative demand, both wealths are confined to a bounded interval. Finally, " $\Delta\ge 0$ " is a statement about optimal values, and the optimal SD investment need not exist; the argument has to be run for every SD investment, not for an optimal one.

Formalization scope

All declarations live in the namespace MixFlex.Reliable. The probability space is (Ω, μ) with IsProbabilityMeasure μ; demand is a measurable X : Ω → Fin N → ℝ with each coordinate almost surely nonnegative, and no density, independence or integrability is assumed. Expectations are Bochner integrals. Perfect reliability ( $\theta=1$ ) is built into the wealths (A-4)–(A-5), so the committed-cost fraction $\lambda$ does not appear. Standing parameters: $p>0$ , $c>0$ , $\beta\ge 1$ , $0<\eta\le1$ , $w_0$ arbitrary. The requirements $p,c>0$ and nonnegative, measurable demand are made explicit; the page treats them as part of the model.

The premium $\Delta$ and the indifference cost are not defined as real numbers, since the indifference cost need not be unique. " $\Delta\ge0$ " is encoded as "SF is weakly preferred for every $c_{N+1}\le c$ ", and "weakly preferred" as "every nonnegative SD investment is matched or beaten by a nonnegative SF investment", with no real suprema. For CVaR the maximum in (8) over the investment and the threshold is encoded in the same matching form. The milestones compare the objectives at the flexible cost $c$ , as (A-5) is printed.

A formalization in which the expected utility of a non-integrable wealth defaults to zero, or in which $\eta=0$ makes the CVaR bracket $w_0+v$ , would make the comparisons meaningless; the statements exclude both ( $K\ge0$ with nonnegative demand bounds the wealths; $\eta>0$ ). " $\Delta\ge0$ " is also not trivially true: for a flexible cost above $c$ SF can be strictly worse.

Out of scope: Propositions 1–3 and 5–8 (Proposition 1 is the companion mission on the risk-neutral premium), Remark 1's negative-premium claim and the numerical study. Welcome contributions: a general lemma that an almost-sure inequality between bounded random variables transfers to expected utilities of monotone functions, and a proof of the CVaR bracket comparison.

Selected references

B. Tomlin, Y. Wang, On the value of mix flexibility and dual sourcing in unreliable newsvendor networks, Manufacturing & Service Operations Management 7(1):37–57, 2005. https://doi.org/10.1287/msom.1040.0063
H. Levy, Stochastic dominance and expected utility: survey and analysis, Management Science 38(4):555–593, 1992. https://doi.org/10.1287/mnsc.38.4.555
R. T. Rockafellar, S. Uryasev, Conditional value-at-risk for general loss distributions, Journal of Banking & Finance 26(7):1443–1471, 2002. https://doi.org/10.1016/S0378-4266(02)00271-6
J. A. Van Mieghem, Investment strategies for flexible resources, Management Science 44(8):1071–1078, 1998. https://doi.org/10.1287/mnsc.44.8.1071

7 thms2 active usersReviewed

Completed

Mechanism Design Operations Research Optimization·Captain: mikedeng1

Supply Chain Coordination for False Failure Returns: A Coordinating Target Rebate Helps the Retailer, and the Manufacturer iff Coordinated Effort Is at Least Twice Decentralized EffortResearch Paper

Motivation

A false failure return is a product returned by a consumer as defective although it has no functional or cosmetic defect; managers attribute such returns to installation difficulties, a mismatch with the consumer's preferences, and remorse. Ferguson, Guide and Souza report (pp. 376–377) that false failures account for up to 80% of Hewlett-Packard's inkjet printer returns, roughly 5% of sales, and that the per-unit cost of a false failure return to computer manufacturers is around 25% of the product's price. The manufacturer absorbs most of that cost, while the retailer is the party able to prevent the returns in the short term, by spending time with customers before the sale and supporting them after it. The retailer bears the cost of that effort but captures only part of its benefit, so without an incentive it exerts too little.

The paper (Ferguson, Guide & Souza, MSOM 2006) models this as a single-period manufacturer–retailer problem with non-contractible retailer effort, and asks which contracts restore the supply chain's optimal effort and who gains from them. It belongs to the literature on supply chain coordination with contracts (Cachon 2003) and on channel rebates with sales effort (Taylor 2002); its object is a target rebate, a payment to the retailer for every false failure return below a target.

Setting

A manufacturer with unit cost $c$ sells to a retailer at wholesale price $w$ , who sells at retail price $p$ . Avoiding one false failure return is worth

M_m = m + \delta_m(w - c) \ \text{to the manufacturer},\qquad R_r = r + \delta_r(p - w)\ \text{to the retailer},

where $m$ and $r$ are the parties' return-processing costs and $\delta_m$ , $\delta_r$ are the unit sale impacts of avoiding the return (p. 381). Both are assumed positive.

The retailer chooses an effort $\rho \ge 1$ at cost $a\rho^2/2$ , $a > 0$ . At effort $\rho$ the number of false failures is a nonnegative random variable $X(\rho)$ with mean $\beta/\rho$ , where $\beta > 0$ is the expected number at the minimum effort $\rho = 1$ . The coordinated supply chain earns

\Pi(\rho) = (M_m + R_r)\,\beta\Big(1 - \frac1\rho\Big) - \frac{a\rho^2}{2},

maximized at the coordinated effort $\rho^C = [(M_m + R_r)\beta/a]^{1/3}$ . Without a contract the retailer earns $\pi_R(\rho) = -a\rho^2/2 + R_r\beta(1 - 1/\rho)$ and chooses the decentralized effort $\rho^D = \max\{(R_r\beta/a)^{1/3}, 1\}$ ; the manufacturer then earns $\pi_M(\rho^D) = M_m\beta(1 - 1/\rho^D)$ .

Under a target rebate contract $(u, T)$ the retailer receives $u$ for every false failure below the target $T$ , so the profits become

\pi_R(\rho \mid T, u) = u\,E\{[T - X(\rho)]^+\} - \frac{a\rho^2}{2} + R_r\beta\Big(1 - \frac1\rho\Big),\qquad \pi_M(\rho \mid T, u) = M_m\beta\Big(1 - \frac1\rho\Big) - u\,E\{[T - X(\rho)]^+\}.

The contract coordinates the supply chain when $\rho^C$ maximizes $\pi_R(\cdot \mid T, u)$ over $\rho \ge 1$ . In the uniform case of §3.1, $X(\rho) \sim \mathrm{Uniform}(0, 2\beta/\rho)$ , and the contract must satisfy $T < 2\beta/\rho^C$ .

Formalization targets

Goal: Proposition 2 (p. 383)

Assume $a, \beta, M_m, R_r > 0$ and $(M_m + R_r)\beta > a$ , and let $X(\rho)$ be uniform. For every coordinating contract $(u, T)$ with $u > 0$ , $0 < T < 2\beta/\rho^C$ ,

\pi_R(\rho^C \mid T, u) \ge \pi_R(\rho^D) \qquad\text{and}\qquad \Big(\pi_M(\rho^C \mid T, u) \ge \pi_M(\rho^D) \iff \rho^C \ge 2\rho^D\Big).

Milestones

The milestones follow the paper's §3–§3.1 and the appendix proof, in attack order: concavity of $\Pi$ and optimality of $\rho^C$ (Eqs. (1)–(2)); $\rho^C > 1$ in the interesting case; optimality of $\rho^D$ (Eqs. (3)–(4)); $\rho^C \ge \rho^D$ ; Proposition 1 (concavity of the retailer's rebate profit when $\partial^2 F(x\mid\rho)/\partial\rho^2 \le 0$ ); its uniform instance; the uniform closed form (8); the first-order condition (9); the coordinating target (10) together with the admissibility condition $u > M_m$ ; the manufacturer's profit $M_m\beta(\rho^C - 2)/\rho^C$ under a coordinating contract (25); the retailer's profit (27); and the retailer's gain in the two cases $\rho^D > 1$ (30) and $\rho^D = 1$ (31).

Significance

The result divides the effect of the contract between the two parties. The retailer is always at least as well off as without a contract; the manufacturer, who pays the rebate, gains exactly when the supply chain's optimal effort is at least twice what the retailer would exert alone. When $\rho^D > 1$ this is equivalent to $M_m \ge 7R_r$ (p. 383), so a target rebate pays for the manufacturer only when its own stake in avoiding a false failure dwarfs the retailer's. The companion result (10) shows that for every rebate $u > M_m$ exactly one admissible coordinating target exists, and none for $u \le M_m$ : a coordinating rebate is always larger than the manufacturer's own cost of a return.

The results are proved in the paper by calculus and algebra. None of them has a machine-checked proof that we know of, and nothing on Prove2Me models non-contractible effort or target rebates. The mission produces a checked version of the paper's model with the expectation taken as a genuine integral against the uniform law, a formal notion of coordination as the retailer's optimization, and statements that make explicit which hypotheses each step of the appendix uses. The definitions of effort-dependent profits and coordination are reusable for other effort-inducing contracts in the same paper and in the sales-effort literature.

Difficulty

The algebra of the appendix is short once the first-order condition (9) holds at $\rho^C$ . The substance is getting there. Coordination is defined by optimality of $\rho^C$ for the retailer's profit, and that profit involves the expectation $E\{[T - X(\rho)]^+\}$ , which is piecewise in $\rho$ : it equals $T^2\rho/4\beta$ only while $T \le 2\beta/\rho$ , and $T - \beta/\rho$ beyond. Deriving (9) requires showing that $\rho^C$ is an interior maximizer, that the expectation is differentiable there with the closed-form derivative, and that the side condition $T < 2\beta/\rho^C$ keeps $\rho^C$ in the closed-form region. The converse direction of (10), that the formula for $T$ produces a coordinating contract, needs concavity of the piecewise profit on all of $\rho \ge 1$ , which is where Proposition 1 enters.

Replacing the expectation by the global formula $T^2\rho/4\beta$ is the tempting shortcut and it changes the problem: for $\rho > 2\beta/T$ the formula exceeds the true expectation, and the retailer's maximizer, hence the meaning of "coordinates", changes with it.

Formalization scope

All parameters are real numbers, bundled in a structure Params; $M_m$ and $R_r$ are Params.Mm and Params.Rr. Effort ranges over $\rho \ge 1$ (Set.Ici 1); statements the paper makes for every positive effort (concavity of $\Pi$ , the closed form (8)) are stated on $\rho > 0$ . Cube roots are Real.rpow with exponent $1/3$ on positive bases. The uniform law is Lebesgue measure conditioned on $[0, 2\beta/\rho]$ , and the expectation is the Bochner integral against it. Coordination is IsMaxOn of the retailer's profit on Set.Ici 1 at $\rho^C$ .

Three conventions differ from the printed text, each recorded in the item's formalization note:

The interesting case is printed as $(m + r)\beta > a$ ; the condition equivalent to the stated consequence $\rho^C > 1$ , which the proof uses, is $(M_m + R_r)\beta > a$ . The formalization uses the latter.
The printed evaluation $E_X\{[T - X(\rho)]^+\} = u\int_0^T (T - x)(\rho/2\beta)\,dx$ carries a stray factor $u$ ; the expectation is $T^2\rho/4\beta$ .
Proposition 1 is stated for an arbitrary family of probability laws on $[0,\infty)$ whose distribution functions are $C^2$ in $\rho$ with nonpositive second derivative for $x \in [0,T]$ ; the paper's further assumptions on $F$ (differentiable, strictly increasing in $x$ , mean $\beta/\rho$ ) are not imposed.

The side condition $T < 2\beta/\rho^C$ of §3.1 is a hypothesis of the goal and of the appendix milestones; without it a coordinating contract with $u = M_m$ exists and the "if" direction fails. The unused page assertion $\delta_r < \delta_m < 1$ is not imposed.

The goal is not trivialized by its coordination hypothesis: coordination is the retailer's optimization over the true profit, and milestone (10) shows that coordinating contracts with $T < 2\beta/\rho^C$ exist for every $u > M_m$ , so the hypotheses are satisfiable (Example 1 of the paper, p. 384, is an instance). The retailer half of the goal is comparatively short under this definition of coordination; that is a property of the paper's theorem, not of the encoding. The manufacturer half needs (8), (9) and (25).

The development needs only Mathlib: real calculus (derivatives, concavity, Real.rpow) and Lebesgue integration against a conditioned Lebesgue measure. The model definitions (effort-dependent profits, coordination as the retailer's optimization) are reusable for the paper's other effort-inducing contracts. Contributions welcome: proofs of any milestone, and reusable lemmas on expectations of $[T - X]^+$ under uniform laws.

Selected references

M. Ferguson, V. D. R. Guide Jr., G. C. Souza, Supply Chain Coordination for False Failure Returns, Manufacturing & Service Operations Management 8(4):376–393, 2006. https://doi.org/10.1287/msom.1060.0112
G. P. Cachon, Supply Chain Coordination with Contracts, in Handbooks in Operations Research and Management Science, Vol. 11: Supply Chain Management, Elsevier, 2003. https://doi.org/10.1016/S0927-0507(03)11006-7
T. A. Taylor, Supply Chain Coordination Under Channel Rebates with Sales Effort Effects, Management Science 48(8):992–1007, 2002. https://doi.org/10.1287/mnsc.48.8.992.168

16 thms2 active usersReviewed

Algorithmic Game Theory Operations Research Optimization·Captain: mikedeng1

Strategic Inventory and Supplier Encroachment: For Any Positive Holding Cost the Buyer Withholds Strategic Inventory When the Direct Selling Cost Is Just Below 5/6, at Total Holding Cost Below 11/72Research Paper

Motivation

Two strategic levers shape the balance of power between a manufacturer and the retailer that resells its product. The first is strategic inventory: a buyer that orders more than it sells today, and carries the surplus into the next period, weakens the supplier's leverage over tomorrow's wholesale price. Anand, Anupindi and Bassok (Management Science 2008) showed that in a two-period channel the buyer withholds inventory exactly when its unit holding cost is below $\alpha/4$ . The second is supplier encroachment: a supplier that can sell directly to consumers competes with its own buyer. Arya, Mittendorf and Sappington (Marketing Science 2007) showed that the threat of encroachment can lower wholesale prices and benefit both parties.

Guan, Gurnani, Geng and Luo, Strategic Inventory and Supplier Encroachment (MSOM 2019), combine the two levers in one game. Their headline qualitative finding is Proposition 4.2. When the supplier's direct channel is costly, but not quite too costly to use, the buyer keeps withholding inventory at every finite holding cost. This contrasts with the $\alpha/4$ cutoff of Anand et al. This mission formalizes that proposition, together with the equilibrium characterizations of Appendix A on which it rests.

Setting

There is one supplier and one buyer, two periods, deterministic demand and complete information. In each period the market price is $p = \alpha - q$ , where $q$ is the total quantity sold in that period and $\alpha > 0$ is the demand intercept. The buyer pays a per-unit holding cost $h \ge 0$ on inventory carried into period 2. The supplier pays a per-unit direct selling cost $s \ge 0$ . All other costs and the salvage value are zero. The moves are:

The supplier quotes a wholesale price $w_1 \ge 0$ .
The buyer orders $Q_1$ and sells $q_1$ , with $0 \le q_1 \le Q_1$ . It carries the inventory $I = Q_1 - q_1$ into period 2.
The supplier quotes $w_2 \ge 0$ .
The buyer orders $Q_2 \ge 0$ and sells $q_2$ , with $0 \le q_2 \le I + Q_2$ .
Having observed everything, the supplier sells $q_s \ge 0$ directly. The period-2 price is $\alpha - q_2 - q_s$ .

The total profits are

\Pi_b = (\alpha - q_1)q_1 - w_1 Q_1 - hI + (\alpha - q_2 - q_s)q_2 - w_2 Q_2, \qquad \Pi_s = w_1 Q_1 + w_2 Q_2 + (\alpha - q_2 - q_s - s)q_s .

A strategy profile assigns an action to every history at which a player moves. It is a subgame perfect equilibrium (SPE) if, at every feasible history, the mover's prescribed action is feasible and no feasible alternative, followed by the profile afterwards, raises the mover's total profit. The equilibrium path is the outcome the profile generates; the equilibrium inventory is $I$ on that path. Following the paper (§4), the goal theorem sets $\alpha = 1$ .

Formalization targets

Goal: Proposition 4.2

With $\alpha = 1$ ,

\forall h > 0\ \ \exists \epsilon > 0\ \ \forall s \in \big(\tfrac56 - \epsilon, \tfrac56\big):\quad \text{an SPE exists, and every SPE has } I > 0 \text{ and } hI < \tfrac{11}{72}.

Here $\epsilon$ may depend on $h$ , and the bound $11/72$ applies at the same $(h, s)$ .

Milestones, in attack order

Stage-3 best response (§3.1.1): in every SPE, the supplier sells $q_s = (\alpha - q_2 - s)^+/2$ at every history.
Eq. (1) (§3.1.1): with no inventory, the buyer's period-2 quantity is the four-branch function $q_b(w)$ of the period-2 wholesale price $w$ .
Proposition 4.1, existence half: an SPE exists for every $h \ge 0$ and $s \ge 0$ .
Region 8 (Tables A.1 and A.4): for $h < h_{11}$ with $s_3 \le s < 5\alpha/6$ , or for $h < \alpha/4$ with $5\alpha/6 \le s < \alpha$ , every SPE has $I = 5(\alpha - 4h)/34$ and the path of Table A.4.
Region 7, second part (Tables A.1 and A.3): for $h_{11} < h < h_{10}$ and $s_3 \le s < 5\alpha/6$ , every SPE has $I = I^* = (2\alpha - 3s + x)/2$ and the path of Table A.3.
Region 10, second part (Tables A.1 and A.4): for $h > h_7$ and $2\alpha/3 < s < 5\alpha/6$ , every SPE has $I = 0$ .

The thresholds $x$ , $s_3$ , $h_7$ , $h_{10}$ , $h_{11}$ are explicit algebraic functions of $s$ , given in Appendix A.

Significance

Proposition 4.2 separates the combined model from the two models it merges. Without a direct channel, inventory disappears once $h \ge \alpha/4$ . With a direct channel, a threat of encroachment that is only barely credible keeps inventory alive at every holding cost. The total holding cost nevertheless stays below a constant, because the inventory shrinks as $h$ grows. Milestone 6 shows the flip side: for a fixed $s < 5\alpha/6$ , a large enough $h$ removes the inventory. This is why the window $\epsilon$ must depend on $h$ .

The paper's proofs are in an online appendix that is not reproduced in the article. The article itself gives the equilibrium only as tables. A formal development would supply a checked backward-induction proof of those tables in the regions near $s = 5\alpha/6$ . It would also give a machine-checked SPE framework for multi-stage pricing-and-quantity games in supply chains, which none of the following exists for: Stackelberg pricing, sequential quantity competition, or dual-channel encroachment. No part of this paper has been formalized before.

Difficulty

The equilibrium is found by backward induction through five stages. Each stage's value function is only piecewise smooth, because the supplier's direct-channel response $(\cdot)^+$ switches on and off. As a result the buyer's period-2 profit has kinks, the supplier's period-2 profit as a function of $I$ has several local maxima, and the period-1 problems must compare branches whose boundaries are the irrational thresholds of Appendix A. The obvious approach, solving the first-order conditions stage by stage, fails at the kinks. At some region boundaries it also misses that the supplier is indifferent between two first-period prices, which makes the equilibrium path change discontinuously. Proposition 4.2 then needs uniform control of $h_7$ , $h_{10}$ and $h_{11}$ as $s \uparrow 5/6$ , where the denominator $3s - 2 - x$ of $h_7$ tends to $0$ .

Formalization scope

Representation. Strategies are functions of the full history, not Markov rules in $I$ . IsSPE imposes optimality at every feasible history, including off-path ones. All actions are real numbers; wholesale prices and quantities are nonnegative, with $q_1 \le Q_1$ and $q_2 \le I + Q_2$ .
Normalization. The goal instantiates $\alpha = 1$ as the paper does from §4 on. The milestones keep a general $\alpha > 0$ .
Uniqueness is not stated. Proposition 4.1's uniqueness claim is false for strategy profiles: after the off-path price $w_2 = 0$ , every order $Q_2 \ge q_2 - I$ is optimal. The goal and the region milestones therefore quantify over every SPE and carry existence as a separate conjunct.
Corrected hypotheses.
- The printed $s_3 = (\sqrt{(37 - 3\sqrt{65})/34} + 4/6)\alpha \approx 1.28\alpha$ is replaced by $(\sqrt{37 - 3\sqrt{65}}/34 + 4/6)\alpha \approx 0.772\alpha$ , which matches the paper's "≈0.77".
- Eq. (1) excludes the corner $w = 0$ , $s < \alpha/3$ , where its second branch is wrong.
- Region 8 drops its boundary $h = h_{11}$ and Region 7 drops $h = h_{10}$ , because the equilibrium path switches there and need not be unique.
Ruled-out trivialization. The inventory in the goal is the inventory on the path of an SPE of the game above. It is not the closed form $5(1 - 4h)/34$ or $I^*$ from the tables, and the regional characterization is not a hypothesis. Otherwise the goal would reduce to algebra about the thresholds.
Infrastructure and contributions. The definitions Game, IsSPE and Thresholds are shared by every statement. Welcome contributions include:
- lemmas on maximizing concave piecewise-quadratic functions on half-lines;
- a reusable backward-induction lemma for finite-stage games with real action sets;
- interval-arithmetic facts about $x$ , $h_7$ , $h_{10}$ and $h_{11}$ near $s = 5/6$ ;
- proofs of the paper's other regions.

Selected references

T. Guan, H. Gurnani, X. Geng, Y. Luo, Strategic Inventory and Supplier Encroachment, Manufacturing & Service Operations Management 21(3):536–555, 2019. https://doi.org/10.1287/msom.2018.0705
K. Anand, R. Anupindi, Y. Bassok, Strategic Inventories in Vertical Contracts, Management Science 54(10):1792–1804, 2008. https://doi.org/10.1287/mnsc.1080.0894
A. Arya, B. Mittendorf, D. Sappington, The Bright Side of Supplier Encroachment, Marketing Science 26(5):651–659, 2007. https://doi.org/10.1287/mksc.1070.0280

10 thms2 active usersReviewed

Completed

Algorithmic Game Theory Operations Research Optimization+1·Captain: mikedeng1

Information Sharing in a Supply Chain with a Common Retailer 1: Under Production Diseconomy the Retailer Earns More from Sequential Information Contracting and the Manufacturers from ConcurrentResearch Paper

Motivation

Retailers hold point-of-sale data that their suppliers cannot observe, and large retailers sell access to it through data-sharing programs (Costco's CRX, Walmart's Retail Link and similar programs). When one retailer carries the substitutable products of two competing manufacturers, sharing its demand information is a strategic decision: a manufacturer who knows the demand signal sets his wholesale price in response to it, which changes the retailer's margin and the rival manufacturer's order uncertainty. Whether the retailer should sell the information, to how many manufacturers, and by which protocol, is the question of Shang, Ha and Tong (Management Science 62(1):245–263, 2016).

The paper belongs to the information-sharing literature of Li (2002), Li and Zhang (2008) and Ha, Tong and Zhang (2011), which studies competing supply chains or a single chain. The common-retailer structure differs: the retailer can price-discriminate between the manufacturers through the order in which she offers the information.

Setting

Two manufacturers $i \in \{1, 2\}$ sell substitutable products through one retailer. The demand for product $i$ is

q_i = a + \theta - (1+\phi)p_i + \phi p_j,

where $p_i$ is the retail price, $\phi > 0$ measures competition, and $\theta$ is a random shock with mean $0$ and variance $\sigma^2 > 0$ . The retailer observes a demand signal $Y$ that is unbiased, $E[Y \mid \theta] = \theta$ , and has linear expectation: $E[\theta \mid Y] = \beta Y$ for a weight $\beta$ (in the paper $\beta = t\sigma^2/(1+t\sigma^2)$ , with $t$ the signal accuracy). The retailing cost is zero, and manufacturer $i$ produces $q$ units at cost $bq + c_d q^2$ with $b, c_d > 0$ : a production diseconomy.

The game has four stages.

The retailer and the manufacturers contract on information sharing, which fixes each manufacturer's status $X_i \in \{I, U\}$ (informed or uninformed).
The retailer observes $Y$ and discloses it truthfully to the informed manufacturers.
The manufacturers set wholesale prices $w_i$ simultaneously, an informed one as a function of $Y$ . The retailer then sets retail prices.
Demand realizes and payoffs are received.

The pricing stage is a Bayesian game. Its equilibrium ex ante profits are $\pi_M(n)$ , $\pi_M^I(1)$ , $\pi_M^U(1)$ for the manufacturers and $\pi_R(n)$ for the retailer, where $n$ is the number of informed manufacturers. They define a payoff table for the contracting stage.

Two contracting protocols are compared.

Concurrent contracting: the retailer offers both manufacturers the same payment $T$ , and they accept or reject simultaneously; a Pareto-optimal pure equilibrium is the outcome, and the retailer chooses $T$ .
Sequential contracting: the retailer offers one manufacturer $T_f$ , he accepts or rejects, then the retailer offers the other $T_s$ , and he decides having observed the first decision. The retailer cannot commit to $T_s = T_f$ , and the solution is subgame perfect equilibrium.

Formalization targets

Goal: Proposition 4(d)

For every $\phi > 0$ , $c_d > 0$ and every signal model, the pricing stage has an equilibrium; for every pricing equilibrium, both contracting games have equilibria; and for every concurrent outcome and every sequential subgame-perfect equilibrium (either first mover),

\Pi_R^{C} \le \Pi_R^{S}, \qquad \Pi_M^{S} \le \Pi_M^{C},

with both inequalities strict when $c_d > (\sqrt2 - 1)/(1+\phi)$ . Here $\Pi_R$ is the retailer's profit after side payments and $\Pi_M$ the manufacturers' total profit net of them. The paper's word "higher" is read as $\ge$ because for small $c_d$ neither protocol sells information and all profits coincide.

Milestones

§4.1, Eq. (1): the retailer's best response $\hat p_i = \frac12(a + \beta Y + w_i)$ and the resulting demand.
Lemma 1: the pricing equilibrium exists, is unique, and is linear in $Y$ .
§4.2: the closed forms of the seven ex ante profits.
Lemma 3: $\pi_M(2) > \pi_M^I(1) > \pi_M(0) > \pi_M^U(1)$ , $\pi_R(0) > \pi_R(1) > \pi_R(2)$ , $\pi_R(1) - \pi_R(2) > \pi_R(0) - \pi_R(1)$ .
Proposition 1(b): without contracting, no information is shared.
Propositions 2 and 3: thresholds $c_d^C$ and $c_d^{S1}, c_d^{S2}$ , depending only on $\phi$ , at which the number of informed manufacturers changes under each protocol.
Proposition 4(a): $c_d^{S1} < c_d^C < c_d^{S2}$ .

Significance

The result. Proposition 4(d) says that the order of the offers transfers surplus: selling information one manufacturer at a time lets the retailer exploit the manufacturers' fear of being the only uninformed firm, which raises her profit and lowers theirs. Propositions 2 and 3 show that concurrent contracting shares with both manufacturers or with neither, while sequential contracting can end with only one informed manufacturer. Together they give a complete map of the equilibrium sharing decisions in $(c_d, \phi)$ (Figure 1 of the paper).

Formalizing it. The results are proved in the paper, partly by "it can be shown" and "straightforward" steps: Lemma 3's proof is omitted, and so is the convexity of the function whose root is $c_d^{S2}$ . No part of the paper has a machine-checked proof. A complete formalization would check every such step and make the equilibrium notions precise, in particular the Pareto selection and the tie-breaking at the thresholds, where the retailer is exactly indifferent.

Difficulty

Most of the work is in the contracting stage, not the algebra. The pricing stage must be solved over all square-integrable strategies measurable in the signal. Uniqueness is then almost sure and rests on the linear-expectation identities $E[\theta Y] = \sigma^2$ and $E[Y^2] = \sigma^2/\beta$ . The concurrent game has multiple equilibria for intermediate payments, and the retailer's optimum lies at a payment where two equilibria coexist. The sequential game is a three-stage game with a continuum of offers: at each threshold the retailer is indifferent, and an SPE exists only if acceptance at indifference is chosen correctly. The threshold $c_d^{S2}$ has no closed form; it is the root of a convex rational function of $c_d$ .

Formalization scope

The Lean development lives in the namespace InfoSharing.Diseconomy. Conventions:

The probability space carries $\theta$ and $Y$ in $L^2$ , with the two conditional-expectation identities holding almost everywhere. $\beta$ is a parameter fixed by $E[\theta \mid Y] = \beta Y$ ; Ericson's formula for $\beta$ is not formalized.
Wholesale strategies are measurable, square-integrable functions of the signal value, and constants for an uninformed manufacturer. A pricing equilibrium is ex ante optimality over such strategies, which is equivalent to the paper's conditional optimization. The retailer's rule must be a best response at every wholesale-price pair.
The payoff table is produced by an arbitrary pricing-equilibrium family, not by the §4.2 closed forms. A formalization that takes the closed forms as the definition of the profits would reduce the goal to algebra and a $2 \times 2$ game, and is ruled out.
Payments are nonnegative, only pure strategies are used in the contracting games, and the concurrent outcome selects, among Pareto-optimal equilibria, the one best for the retailer.
Threshold statements use two clauses: the printed value is attained on the closed region, and it is the only value on the region's interior. The thresholds depend only on $\phi$ .
Demands may be negative (θ is unbounded), as in the paper's formulas.

A complete development needs:

the conditional-expectation algebra behind Lemma 1 and §4.2;
rational-function inequalities for Lemma 3;
a case analysis of the two contracting games.

The model layer is shared with the companion mission on production economy.

Selected references

G. Shang, A. Y. Ha, S. Tong, Information Sharing in a Supply Chain with a Common Retailer, Management Science 62(1):245–263, 2016. https://doi.org/10.1287/mnsc.2014.2127
W. A. Ericson, A note on the posterior mean of a population mean, Journal of the Royal Statistical Society B 31(2):332–334, 1969.
L. Li, Information sharing in a supply chain with horizontal competition, Management Science 48(9):1196–1212, 2002. https://doi.org/10.1287/mnsc.48.9.1196.177
L. Li, H. Zhang, Confidentiality and information sharing in supply chain coordination, Management Science 54(8):1467–1481, 2008. https://doi.org/10.1287/mnsc.1070.0851
A. Y. Ha, S. Tong, H. Zhang, Sharing imperfect demand information in competing supply chains with production diseconomies, Management Science 57(3):566–581, 2011. https://doi.org/10.1287/mnsc.1100.1295
X. Vives, Oligopoly Pricing: Old Ideas and New Tools, MIT Press, 1999.

17 thms2 active usersReviewed

Completed

Dynamic Programming Operations Research Probability+1·Captain: mikedeng1

Computing Optimal (s, S) Inventory Policies I: The Renewal Closed Form for the Discounted Cost of a Stationary (s, S) PolicyResearch Paper

Motivation

The periodic-review inventory problem with a fixed ordering cost is one of the basic models of operations research. A firm reviews its stock once per period, may order at a cost $K$ per order plus a unit cost, and then faces a random demand; unmet demand is backlogged. Scarf (1960) and Iglehart (1963) showed that for this model an $(s, S)$ policy is optimal: order up to $S$ whenever the stock falls below $s$ , and otherwise do nothing. That result tells a manager what shape a good policy has, but not which pair $(s, S)$ to use.

Veinott and Wagner, Computing Optimal (s, S) Inventory Policies (Management Science 11 (1965) 525–552), gave the first practical algorithm for computing an optimal pair when demand is discrete. The algorithm rests on a closed form, their Eq. (11), for the discounted cost of an arbitrary stationary $(s, S)$ policy, obtained by a renewal argument in their Section 3. The same closed form, in the undiscounted limit, is the classical expression of the long-run average cost of an $(s, S)$ policy used throughout inventory theory textbooks.

Timeline:

1958: Arrow, Karlin and Scarf collect the early dynamic inventory models.
1960: Scarf proves optimality of $(s, S)$ policies in the finite-horizon model via $K$ -convexity.
1963: Iglehart extends optimality to the infinite-horizon model.
1965: Veinott and Wagner derive the renewal closed form (10)–(11) and the bounds and search procedure built on it.

Setting

Demands $\xi_1, \xi_2, \dots$ are independent random variables on $\{0, 1, 2, \dots\}$ with common distribution $\varphi$ , $\varphi(k) = \Pr(\xi_t = k)$ . Write $\varphi^i$ for the $i$ -fold convolution of $\varphi$ ( $\varphi^0$ is the point mass at $0$ ) and $\Phi^i(k) = \sum_{t=0}^{k}\varphi^i(t)$ for its distribution function, so $\Phi^0 \equiv 1$ .

In period $t$ the stock before ordering is $X_t \in \mathbb Z$ and the stock after ordering is $Y_t \ge X_t$ ; then $X_{t+1} = Y_t - \xi_t$ . With the unit purchase cost eliminated as in the paper's Eq. (2), the cost of period $t$ is $K\delta(Y_t - X_t) + G_\alpha(Y_t)$ , where $K \ge 0$ is the set-up cost, $\delta(0) = 0$ , $\delta(z) = 1$ for $z > 0$ , and $G_\alpha : \mathbb Z \to \mathbb R$ is the one-period cost. Period $t$ is discounted by $\alpha^{t-1}$ with $0 \le \alpha < 1$ .

A stationary $(s, S)$ policy, for integers $s \le S$ , sets $Y_t = S$ if $X_t < s$ and $Y_t = X_t$ otherwise. Its total expected discounted cost from $X_1 = x$ is

f(x \mid s, S) = \sum_{t=1}^{\infty} \alpha^{t-1} E\bigl[K\delta(Y_t - X_t) + G_\alpha(Y_t)\bigr],

and its equivalent cost per period is $a_\alpha(x \mid s, S) = (1 - \alpha) f(x \mid s, S)$ .

The renewal quantities are

m_\alpha(k) = \sum_{i=1}^{\infty}\alpha^i\varphi^i(k), \qquad M_\alpha(k) = \sum_{i=1}^{\infty}\alpha^i\Phi^i(k),

the latter being the discount renewal function,

L_\alpha(x, d) = G_\alpha(x) + \sum_{i=1}^{\infty}\sum_{k=0}^{d}\alpha^i G_\alpha(x - k)\varphi^i(k), \qquad r_\alpha(d) = \sum_{i=1}^{\infty}\alpha^i\bigl[\Phi^{i-1}(d) - \Phi^i(d)\bigr].

If $T(d)$ is the first period in which cumulative demand exceeds $d$ , then $L_\alpha(x, d)$ is the expected discounted one-period cost over periods $1, \dots, T(d)$ from stock $x$ without ordering, and $r_\alpha(d) = E[\alpha^{T(d)}]$ .

Formalization targets

Goal: Eq. (11)

With $D = S - s$ ,

a_\alpha(x \mid s, S) = \begin{cases} \dfrac{L_\alpha(S, D) + K}{1 + M_\alpha(D)} & x < s, \\[2ex] (1 - \alpha)L_\alpha(x, x - s) + \dfrac{L_\alpha(S, D) + K}{1 + M_\alpha(D)}\, r_\alpha(x - s) & x \ge s. \end{cases}

Milestones

Appendix §1: $M_\alpha(k) < \infty$ for $0 \le \alpha \le 1$ with $\alpha\varphi(0) < 1$ .
Eq. (8): $L_\alpha(x, d) = G_\alpha(x) + \sum_{j=0}^{d} G_\alpha(x - j)m_\alpha(j)$ .
Eq. (9): $r_\alpha(d) = \alpha - (1 - \alpha)M_\alpha(d)$ .
The renewal equation $f(S) = L_\alpha(S, D) + Kr_\alpha(D) + f(S)r_\alpha(D)$ .
$f(x) = K + f(S)$ for $x < s$ .
$f(x) = L_\alpha(x, x - s) + Kr_\alpha(x - s) + f(S)r_\alpha(x - s)$ for $x \ge s$ .
Eq. (10): the closed form of $f$ with denominator $1 - r_\alpha(D)$ .

Significance

Eq. (11) turns the cost of an $(s, S)$ policy, an infinite series over the trajectories of a controlled Markov chain, into a finite expression in $G_\alpha$ , $K$ and the renewal sequence $m_\alpha$ , which the paper computes by a one-line recursion. Everything in the paper's Section 4 builds on it: the search for an optimal pair minimizes $a_\alpha(\cdot \mid s, S)$ over a finite box, and the undiscounted limit $\alpha \to 1$ gives the long-run average cost $(L_1(S, D) + K)/(1 + M_1(D))$ .

The result is classical and proved in the paper. What this mission adds is a machine-checked derivation from the definition of the policy's expected cost, including the renewal step, which the paper states in one sentence ("a renewal of the process takes place"). It also produces a reusable Lean layer: discrete convolution powers, the discount renewal function, and the law of an $(s, S)$ -controlled inventory chain. To the best of our knowledge none of these is formalized in Mathlib or on the platform.

Difficulty

The paper's argument conditions on the random time $T(D)$ at which the process renews and uses the strong Markov property at that time. In the formalization, $f$ is defined as a sum over periods of expectations under the law of $X_t$ . Relating that sum to one that splits at the random time $T(D)$ requires either a stopping-time decomposition of the chain or an explicit accounting of the law of $X_t$ before and after the first order. Neither is a direct computation. A second difficulty is the interchange of the infinite sum over periods with the sum over states $y \in \mathbb Z$ , which has infinitely many states reachable (demand is unbounded below). The renewal equation (milestone 4) alone does not determine $f(S)$ without the fact that $r_\alpha(D) < 1$ for $\alpha < 1$ , which comes from (9).

Formalization scope

Namespace VeinottWagnerSS.RenewalCost. Stock levels are integers, demands natural numbers; $x - s$ and $D = S - s$ enter $L_\alpha$ , $M_\alpha$ , $r_\alpha$ through Int.toNat, which is exact because the statements assume $s \le x$ or $s \le S$ .
Reduced model. The primitives are $G_\alpha$ , $K$ , $\alpha$ and $\varphi$ , as in the paper's Eq. (2): the unit purchase cost is set to $0$ and the holding–penalty cost is replaced by $G_\alpha$ .
Demand is a real function $\varphi : \mathbb N \to \mathbb R$ , non-negative and summing to $1$ .
The cost $f$ is the expected discounted cost of the controlled chain: the law of $X_t$ is built recursively from $X_1 = x$ and the transition $\Pr(X_{t+1} = z \mid X_t = y) = \varphi(Y(y) - z)$ . It is not defined by (10) or by the renewal equations, and not as the solution of a fixed-point equation. A formalization in which any of milestones 4–7 or the goal holds by definition is ruled out.
Series are real tsums. $L_\alpha$ is defined by the series (7) and $r_\alpha$ by the first line of (9), i.e. through the law $\Pr[T(d) = i] = \Phi^{i-1}(d) - \Phi^i(d)$ ; the paper's derivations of these series from $T(d)$ are not formalized. For $\alpha < 1$ all series converge for every $G_\alpha$ , because after period $1$ the stock after ordering lies in the finite set $\{S\} \cup [s, \max(x, S)]$ .
Hypotheses. Milestones 1–3 assume $0 \le \alpha \le 1$ and $\alpha\varphi(0) < 1$ , the paper's standing assumption on p. 533. Milestones 4–7 and the goal assume $0 \le \alpha < 1$ , $K \ge 0$ and $s \le S$ . The paper's standing assumptions that $G_\alpha$ is convex and tends to $+\infty$ as $|y| \to \infty$ are not imposed: the statements hold for every $G_\alpha$ when $\alpha < 1$ , and the paper's derivation does not use them. This is a disclosed generalization.
Printed slips. None found in the formalized statements.
Not formalized: the recursion (A1) for $m_\alpha$ , the limit (12) as $\alpha \to 1$ , and the stationary analysis (13)–(20).

Contributions welcome: proofs of the milestones, general lemmas on discrete renewal sequences and convolution powers, and a first-passage decomposition for integer-valued Markov chains, which is reusable beyond this mission.

Selected references

A. F. Veinott Jr. and H. M. Wagner, Computing Optimal (s, S) Inventory Policies, Management Science 11(5), 525–552, 1965. https://doi.org/10.1287/mnsc.11.5.525
H. Scarf, The Optimality of (S, s) Policies in the Dynamic Inventory Problem, in Mathematical Methods in the Social Sciences, Stanford University Press, 1960.
D. L. Iglehart, Optimality of (s, S) Policies in the Infinite Horizon Dynamic Inventory Problem, Management Science 9(2), 259–267, 1963. https://doi.org/10.1287/mnsc.9.2.259
K. J. Arrow, S. Karlin and H. Scarf, Studies in the Mathematical Theory of Inventory and Production, Stanford University Press, 1958.

11 thms2 active usersReviewed

Dynamic Programming Operations Research Stochastic Systems·Captain: mikedeng1

Computing Optimal (s, S) Inventory Policies II: Bounds on the Optimal s and S of the n-Period Model from the One-Period CostResearch Paper

Motivation

The $(s, S)$ policy is the standard ordering rule for a single stocked item with a fixed charge per order: when the stock position falls below a reorder point $s$ , order up to a level $S$ ; otherwise order nothing. Scarf (1960) proved that when the expected one-period cost is convex, some $(s, S)$ policy is optimal in every period of a finite-horizon model with set-up cost. Iglehart (1963) extended this to the infinite horizon. These results establish existence only. They give no procedure for finding the optimal pair.

Veinott and Wagner (1965) gave such a procedure. Its first step is to bound the optimal $s$ and $S$ by four integers $\underline{s} \le \bar{s} \le \underline{S} \le \bar{S}$ computed from the one-period cost alone. This reduces the search for an optimal policy to a finite box. Their Theorem 4(a) proves that the bounds hold for the first-period parameters of an optimal $(s, S)$ policy in every $n$ -period model. This mission formalizes that theorem and the four comparison lemmas (Lemmas 2–5 of the paper's Appendix §2) from which the paper derives it.

Setting

Demands $\xi_1, \xi_2, \dots$ in periods $1, 2, \dots$ are independent, non-negative integer random variables with common distribution $\varphi(k) = \Pr(\xi_t = k)$ and finite mean. Unfilled demand is backlogged, so stock levels are arbitrary integers. In period $t$ , $X_t$ is the stock on hand plus on order before ordering and $Y_t \ge X_t$ the level after ordering. Then $X_1 = x$ and $X_{t+1} = Y_t - \xi_t$ .

A policy chooses $Y_t$ as any integer function of the information available at the start of period $t$ . Given $X_1 = x$ , that information is determined by $x$ and $\xi_1, \dots, \xi_{t-1}$ . Policies may therefore depend on the whole history; they are not required to be Markov.

Costs are summarized by a set-up cost $K \ge 0$ , a discount factor $0 \le \alpha \le 1$ and a one-period cost $G_\alpha : \mathbb Z \to \mathbb R$ . The paper reduces the model with purchase cost $c$ , lead time $\lambda$ and holding–penalty cost $L$ to these data by its Eq. (2), with $G_\alpha(y) = (1 - \alpha) c y + L(y)$ . The $n$ -period cost of a policy $Y$ from $X_1 = x$ is

f_n(x \mid Y) = \sum_{t=1}^{n} \alpha^{t-1}\bigl[K\,E\,\delta(Y_t - X_t) + E\,G_\alpha(Y_t)\bigr],

where $\delta(0) = 0$ and $\delta(z) = 1$ for $z > 0$ . A policy is optimal if it minimizes $f_n(x \mid \cdot)$ for every $x$ simultaneously. The standing assumptions are that $G_\alpha$ is convex on the integers (non-decreasing forward differences) and $G_\alpha(y) \to \infty$ as $|y| \to \infty$ .

The bounds (p. 537) are defined as follows. $\underline{S}$ is the smallest minimizer of $G_\alpha$ . $\bar S$ is the smallest integer $\ge \underline{S}$ with $G_\alpha(\bar S + 1) \ge G_\alpha(\underline S) + \alpha K$ (21). $\underline s$ is the smallest integer with $G_\alpha(\underline s) \le G_\alpha(\underline S) + K$ (22). $\bar s$ is the smallest integer with $G_\alpha(\bar s) \le G_\alpha(\underline S) + (1 - \alpha)K$ (23).

Formalization targets

Goal: Theorem 4(a)

For every $n \ge 2$ there is an optimal $(s, S)$ policy for the $n$ -period model whose first-period rule $(s_n, S_n)$ satisfies

\underline{s} \le s_n \le \bar{s} \le \underline{S} \le S_n \le \bar{S}.

Optimality is against all history-dependent policies and for every starting level. The existence of an optimal $(s, S)$ policy is part of the conclusion.

Milestones

The characterization of $\underline S$ by $\Delta G_\alpha(\underline S - 1) < 0 \le \Delta G_\alpha(\underline S)$ , and the existence of the parameters of (21)–(23).
Lemma 2: $\underline{S} \le S_n$ for any optimal policy using $(s_n, S_n)$ in period 1.
Lemma 3: if $\bar s < s_n$ , some policy using $(\bar s, S_n)$ in period 1 costs no more, from every $x$ .
Lemma 4: if $\bar S < S_n$ (and $s_n \le \bar s$ ), some policy using $(s_n, \underline S)$ in period 1 costs no more, from every $x$ .
Lemma 5: $\underline{s} \le s_n$ for any optimal policy using $(s_n, S_n)$ in period 1.

Significance

The theorem turns the optimization over $(s, S)$ policies into a search over a finite box that depends only on $G_\alpha$ , $K$ and $\alpha$ . The paper's Section 4 procedure for the infinite-horizon problem (Theorem 4(b), Step i) is built on this box, and the bounds also give an interpretation of $s$ and $S$ : $\underline S$ is the single-period optimum, and $\bar s$ , $\underline s$ , $\bar S$ mark where the one-period cost exceeds that optimum by the fractions $(1 - \alpha)K$ , $K$ and $\alpha K$ of the set-up cost.

The results are proved in the paper. None of them has a machine-checked proof as far as is known; no discrete-state finite-horizon inventory model with set-up cost is on the platform. A formal proof would provide a reusable finite-horizon dynamic-programming model with history-dependent policies and extended-real expected costs, and a machine-checked version of the existence of optimal $(s, S)$ policies in the discrete setting, which Theorem 4(a) contains.

Difficulty

The four lemmas compare an optimal policy with an explicit modification of it. The modification in Lemmas 2 and 5 raises the stock in period 1 and then orders $\max(X'_t, Y^n_t)$ , where $Y^n_t$ is the original policy's decision along the original demand path. This comparison policy is history-dependent even when the original policy is not, so the argument cannot be carried out inside the class of Markov or $(s, S)$ policies. Expectations must be handled over finite demand histories, and costs can be infinite for general policies.

The goal also contains the existence of an optimal $(s, S)$ policy for the $n$ -period model. The paper cites this from Scarf and Zabel rather than proving it. Applying Lemma 3 or 4 yields an optimal policy whose later periods are no longer of $(s, S)$ form. Restoring the $(s, S)$ form requires the dynamic-programming principle of optimality together with the $K$ -convexity argument.

Formalization scope

The Lean model (VeinottWagnerSS.Bounds.Model) uses the reduced model of Eq. (2): G : ℤ → ℝ is a primitive, and $c$ , $\lambda$ and $L$ do not appear. Stock levels are integers and demands are natural numbers; the demand law is a PMF ℕ with finite mean. A policy is Y : (t : ℕ) → ℤ → (Fin t → ℕ) → ℤ: period $t + 1$ 's level as a function of $x$ and the first $t$ demands, so it cannot see current or future demand. Periods are numbered from $0$ in Lean. Expectations are sums over demand histories weighted by $\prod_i \varphi(\xi_i)$ . $E\,G_\alpha(Y_t)$ is the difference of the expectations of the positive and negative parts, and $f_n$ is valued in EReal. Under the standing assumptions $G_\alpha$ is bounded below, so the negative part is finite and no $\infty - \infty$ arises. Both $\alpha = 1$ and $\alpha = 0$ are allowed.

The bounds SLow, SHigh, sLow, sHigh are infima of the sets in (21)–(23); a milestone proves they are the least elements. A trivializing formalization is ruled out as follows. Optimality is over all admissible policies and for every $x$ . The bounds are the least integers of (21)–(23). The goal requires an optimal policy, not only a bounded pair. Existence of an optimal policy is proved, not assumed.

Printed statements corrected. Lemma 4 as printed has no hypothesis on $s_n$ . Its proof begins "By lemma 3 we may assume that $s_n \le \bar s$ ", and without that assumption $(s_n, \underline S)$ need not be an $(s, S)$ rule. The Lean statement adds $s_n \le \bar s$ . The last display of the proof of Lemma 5 reads $G_\alpha(\underline s + 1)$ where $G_\alpha(\underline s - 1)$ is meant; this affects only the proof. The milestone texts are verbatim.

Useful contributions include lemmas on convex functions on $\mathbb Z$ (monotonicity on either side of a minimizer), expectation lemmas for sums over Fin t → ℕ, and the finite-horizon principle of optimality for this model.

Selected references

A. F. Veinott, Jr. and H. M. Wagner, Computing Optimal (s, S) Inventory Policies, Management Science 11(5), 525–552, 1965. https://doi.org/10.1287/mnsc.11.5.525
H. Scarf, The Optimality of (S, s) Policies in the Dynamic Inventory Problem, in Mathematical Methods in the Social Sciences, Stanford University Press, 1960.
E. Zabel, A Note on the Optimality of (S, s) Policies in Inventory Theory, Management Science 9(1), 123–125, 1962. https://doi.org/10.1287/mnsc.9.1.123
D. L. Iglehart, Optimality of (s, S) Policies in the Infinite Horizon Dynamic Inventory Problem, Management Science 9(2), 259–267, 1963. https://doi.org/10.1287/mnsc.9.2.259

9 thms3 active usersReviewed

Dynamic Programming Markov Chain Operations Research+1·Captain: mikedeng1

Computing Optimal (s, S) Inventory Policies III: Selecting an (s, S) Policy That Is Optimal for Every Starting StockResearch Paper

Motivation

The periodic-review inventory model with a fixed ordering cost is one of the basic models of operations research. When every order incurs a set-up cost $K$ in addition to holding and shortage costs, the optimal replenishment rule over an infinite horizon is, under standard convexity assumptions, a stationary $(s, S)$ policy: whenever the stock falls below the reorder point $s$ , order up to the level $S$ . Existence of such an optimal policy goes back to Scarf (1960) and Iglehart (1963). Knowing that an optimal $(s, S)$ policy exists does not say how to find one, and the average cost of an $(s, S)$ policy is neither convex nor unimodal in $(s, S)$ .

Veinott and Wagner (Management Science 11 (1965) 525–552) gave an exact algorithm. It proceeds in three steps: (i) compute integers $\underline{s} \le \bar{s} \le \underline{S} \le \bar{S}$ bounding an optimal policy; (ii) find the set $\mathcal S$ of all policies within those bounds that minimize the cost for starting stocks below $\underline{s}$ ; (iii) choose from $\mathcal S$ a policy that is optimal for every starting stock. This mission formalizes the theory behind Step iii. It is the third mission of a series on the paper: mission I treats the renewal closed form of the discounted cost, mission II the bounds of Step i.

Setting

Demands $\xi_1, \xi_2, \dots$ are independent non-negative integer random variables with common distribution $\varphi$ and finite mean. Following the paper's Eq. (2), the unit purchase cost and the holding and penalty costs are combined into a single function $G_\alpha : \mathbb Z \to \mathbb R$ , assumed convex with $G_\alpha(y) \to \infty$ as $|y| \to \infty$ ; the set-up cost is $K \ge 0$ and $\alpha$ is the discount factor.

A stationary $(s, S)$ policy, with integers $s \le S$ , sets the stock after ordering to

Y_t = S \text{ if } X_t < s, \qquad Y_t = X_t \text{ if } X_t \ge s,

and the stock evolves as $X_{t+1} = Y_t - \xi_t$ from $X_1 = x$ . Its discounted cost is

f(x \mid s, S) = \sum_{t \ge 1} \alpha^{t-1} E\bigl[K\delta(Y_t - X_t) + G_\alpha(Y_t)\bigr],

where $\delta(z) = 1$ for $z > 0$ and $\delta(0) = 0$ , and its equivalent average cost is $a_\alpha(x \mid s, S) = (1-\alpha) f(x \mid s, S)$ .

A policy $(s', S')$ is optimal for a set $\mathfrak X$ of integers if, for each $x \in \mathfrak X$ , it minimizes $a_\alpha(x \mid s, S)$ over all $(s, S)$ policies; it is optimal if it is optimal for every integer $x$ . Under a fixed policy, $x'$ is accessible from $X_1 = x$ if $\Pr(X_t = x' \mid X_1 = x) > 0$ for some $t > 1$ .

Below the reorder point the cost does not depend on the starting stock; its value is written $\mathcal L_\alpha(S, D)$ with $D = S - s$ . The bounds are: $\underline{S}$ the smallest minimizer of $G_\alpha$ ; $\bar{S}$ the smallest integer $\ge \underline{S}$ with $G_\alpha(\bar{S}+1) \ge G_\alpha(\underline{S}) + \alpha K$ (21); $\underline{s}$ the smallest integer with $G_\alpha(\underline{s}) \le G_\alpha(\underline{S}) + K$ (22); $\bar{s}$ the smallest integer with $G_\alpha(\bar{s}) \le G_\alpha(\underline{S}) + (1-\alpha)K$ (23). The candidate set $\mathcal S$ consists of the policies with $\underline{s} \le s \le \bar{s}$ , $\underline{S} \le S \le \bar{S}$ that minimize $\mathcal L_\alpha(S, S-s)$ among such policies.

Formalization targets

Goal: Theorem 2 (p. 543)

For $0 < \alpha < 1$ and $(s^i, S^i), (s^j, S^j) \in \mathcal S$ : if $(s^i, S^i)$ is optimal and every $x'$ with

\min(s^i, s^j) \le x' < \max(s^i, s^j)

is accessible from $S^j$ under $(s^j, S^j)$ , then $(s^j, S^j)$ is optimal.

Milestones

§3, p. 533. For $x < s$ , $f(x \mid s, S) = K + f(S \mid s, S)$ .
Theorem 1, p. 542. For $0 \le \alpha < 1$ and $s \le s'$ : if $a_\alpha(x \mid s, S) = a_\alpha(x \mid s', S')$ for all $x < s'$ , then equality holds for all $x$ .
Lemma 1, p. 543. For $0 < \alpha < 1$ : if $(s, S)$ is optimal for $X_1 = x$ , it is optimal for every $x'$ accessible from $x$ .

Significance

Theorem 2 turns the final selection step of the algorithm into a reachability check on the demand distribution: a policy of $\mathcal S$ is certified optimal without comparing average costs at every starting stock. Its corollaries give checkable sufficient conditions; for example (Corollary 2.2) if $\varphi(k) > 0$ for $k = 1, \dots, s^n - s^1$ , the policy of $\mathcal S$ with the largest reorder point is optimal, which covers Poisson and negative binomial demand. Theorem 1 separately reduces the comparison of two policies to finitely many starting stocks.

The results are proved in the paper (Section 4 and Appendix §3). No machine-checked version is known: the platform has no discrete $(s, S)$ inventory chain, no discounted cost of a stationary policy on $\mathbb Z$ , and no accessibility notion for such a chain. The mission produces these objects together with the paper's selection theory on top of them.

Difficulty

Theorem 1 needs a renewal decomposition at the first passage of the stock below $s'$ , carried out for expectations over an unbounded integer state space with a discounted infinite sum. Lemma 1 is the delicate step. The paper's argument compares the $(s, S)$ policy with a hybrid policy that follows $(s, S)$ until the stock first reaches $x'$ and then switches to an optimal policy; the inequality "the hybrid cannot be better than the optimal policy" requires that some stationary $(s, S)$ policy is optimal among all ordering policies, including non-stationary ones. That existence result is cited by the paper (Section 2), not proved there. A proof of Lemma 1 within the class of $(s, S)$ policies alone does not go through, because the hybrid policy is not an $(s, S)$ policy.

Formalization scope

All objects live in the namespace VeinottWagnerSS.Selection. The model is the structure Model: the demand distribution φ : PMF ℕ with finite mean, K ≥ 0, and G : ℤ → ℝ convex (non-decreasing forward differences) and tending to $+\infty$ at both ends. The unit cost $c$ , the function $L$ and the lead time $\lambda$ do not appear (the paper's own reduction, Eq. (2), p. 529). Stock levels are integers. stateLaw is the law of $X_{t+1}$ , obtained by iterated PMF.bind; fCost is the expected discounted cost of that chain as a real series, which converges absolutely for $0 \le \alpha < 1$ because every $Y_t$ lies in $[s, \max(x, S)]$ . aCost is $(1-\alpha)$ times fCost. Accessible uses the law of $X_t$ with $t > 1$ strictly. Optimality is among $(s, S)$ policies (p. 536); the class of general ordering policies is not formalized.

The bounds $\underline{s}, \bar{s}, \underline{S}, \bar{S}$ are infima of sets of integers; under the standing assumptions and $\alpha < 1$ these sets are nonempty and bounded below, so each bound is the least integer the paper describes. $\mathcal L_\alpha(S, D)$ is defined as $a_\alpha(S - D - 1 \mid S - D, S)$ , the cost at the starting stock just below $s$ ; that this is the common value for every $x < s$ is milestone 1.

The standing assumptions are kept in every statement, including Theorem 1 and milestone 1, which do not need them; Lemma 1 and Theorem 2 are true only because of them. No printed slip was found in the three results.

Trivializing formalizations are excluded: $f$ is the expected cost of the stock process, not a closed formula or a fixed point of a recursion, so milestone 1 is not definitional; the bounds are the least integers of (21)–(23), not arbitrary integers, so $\mathcal S$ is determined by the data; the goal does not assume that $(s^j, S^j)$ is optimal below $\max(s^i, s^j)$ , and Lemma 1 assumes optimality only at the single starting stock $x$ .

Useful contributions beyond the milestones: summability lemmas for fCost, the Markov (one-step) equation for fCost, the first-passage decomposition, and, for Lemma 1, a formalization of general ordering policies with the existence of an optimal stationary $(s, S)$ policy. The chain and cost definitions are reusable for other $(s, S)$ results of the paper (Theorem 3, Corollaries 2.1 and 2.2).

Selected references

A. F. Veinott, Jr. and H. M. Wagner, Computing Optimal (s, S) Inventory Policies, Management Science 11(5), 525–552, 1965. https://doi.org/10.1287/mnsc.11.5.525
H. Scarf, The Optimality of (S, s) Policies in the Dynamic Inventory Problem, in Mathematical Methods in the Social Sciences, Stanford University Press, 1960.
D. L. Iglehart, Optimality of (s, S) Policies in the Infinite Horizon Dynamic Inventory Problem, Management Science 9(2), 259–267, 1963. https://doi.org/10.1287/mnsc.9.2.259

6 thms2 active usersReviewed

Algorithmic Game Theory Operations Research Optimization+1·Captain: mikedeng1

Information Sharing in a Supply Chain with a Common Retailer 2: Under Production Economy the Retailer Earns Weakly More from Sequential Information Contracting and the Manufacturers from ConcurrentResearch Paper

Motivation

Large retailers hold point-of-sale and loyalty-card data that their suppliers cannot observe, and many of them sell access to it through data-sharing programs; others share the same data for free, or with only some suppliers (Shang, Ha & Tong 2016, §1). When two competing manufacturers sell through one common retailer, sharing a demand signal with a manufacturer changes how he sets his wholesale price, which in turn changes the retailer's margins and the rival's demand. Whether the retailer wants to share, with how many manufacturers, and at what price, is therefore a question about a multistage game with incomplete information.

Shang, Ha and Tong answer it for linear demand, a linear-expectation signal and quadratic production costs, under two contracting protocols. This mission covers the production economy case (marginal cost decreasing in volume, §6 of the paper), in which the retailer may have an incentive to share information even without payment. A companion mission covers production diseconomy (§5).

Setting

Two manufacturers $i \in \{0,1\}$ sell substitutable products through a common retailer. Demand for product $i$ is

q_i = a + \theta - (1+\phi)p_i + \phi p_j ,

where $p_i$ is the retail price, $\phi > 0$ measures competition intensity and $\theta$ is a demand shock with mean $0$ and variance $\sigma^2 > 0$ . The retailer observes a demand signal $Y$ with $E[Y \mid \theta] = \theta$ and a linear-expectation structure $E[\theta \mid Y] = \beta Y$ , where $\beta = \beta(t,\sigma)$ is the signal weight. Producing $q$ units costs $bq - c_e q^2$ with $c_e > 0$ ; the paper writes $c = -c_e$ and assumes $c_e < 2/(1+\phi)$ (the Assumption, p. 251). Retailing is costless.

The game has three stages.

Information contracting. Under concurrent contracting the retailer offers both manufacturers the same payment $T \ge 0$ for the signal; they decide simultaneously and play a Pareto-optimal pure equilibrium. Under sequential contracting she offers a payment $T_f$ to a first manufacturer $k$ and, after his decision, a payment $T_s$ to the other; the outcome is a subgame-perfect equilibrium (SPE). The retailer commits not to share for free after a rejection (§6.2).
Pricing. Given the information statuses $X_i \in \{I, U\}$ , each manufacturer sets a wholesale price $w_i$ (a function of $Y$ if informed, a constant otherwise), then the retailer sets retail prices; the solution concept is Bayesian Nash equilibrium.
Demand realizes and profits are collected.

The ex ante profits of the pricing equilibrium are denoted $\pi_M(0)$ , $\pi_M^U(1)$ , $\pi_M^I(1)$ , $\pi_M(2)$ for a manufacturer and $\pi_R(n)$ for the retailer, $n$ the number of informed manufacturers. $n_e^N$ , $n_e^C$ , $n_e^S$ denote the equilibrium number of informed manufacturers without contracting, under concurrent and under sequential contracting.

Formalization targets

Goal: Proposition 8(d)

For every $\phi > 0$ and $0 < c_e < 2/(1+\phi)$ , pricing equilibria exist, concurrent outcomes and sequential SPEs exist, and for every concurrent outcome and every SPE (either first mover)

\Pi_R^C \le \Pi_R^S, \qquad \Pi_M^S \le \Pi_M^C ,

where $\Pi_R$ is the retailer's profit after side payments and $\Pi_M$ the manufacturers' total profit net of them. The second inequality is asserted for all $c_e$ except at most two values depending only on $\phi$ . The comparisons about every pricing equilibrium family exclude the single value $c_e^* = (2+3\phi)/[(1+2\phi)(1+\phi)]$ (see Formalization scope). The paper says "higher"; the inequalities are weak because both sides coincide on intervals of positive length.

Milestones

Lemma 1: the pricing equilibrium exists and, for $c_e \ne c_e^*$ , is unique and linear in $Y$ with explicit coefficients.
§4.2: the ex ante profits $\pi_M(\cdot)$ and $\pi_R(\cdot)$ in closed form.
Lemma 5(a)–(c) and Lemma 5(d): sign comparisons of these profits in $c_e$ , with thresholds $1/(1+\phi)$ , $(4+5\phi)/[(2+3\phi)(1+\phi)]$ , $c_e^a$ and $c_e^N$ .
Proposition 7: thresholds $c_e^C$ , $c_e^S$ such that

n_e^Z = 0 \text{ for } c_e < \tfrac{1}{1+\phi}, \quad n_e^Z = 2 \text{ for } \tfrac{1}{1+\phi} \le c_e < c_e^Z, \quad n_e^Z = 1 \text{ for } c_e^Z \le c_e < \tfrac{2}{1+\phi}.

Proposition 6(b): the same structure for $n_e^N$ with a threshold $c_e^N$ .
Proposition 8(a): $c_e^N < c_e^S \le c_e^C$ .

Significance

Proposition 8(d) says that a common retailer who sells information prefers to sell it sequentially, and that the manufacturers bear the cost: sequential offers let her extract a larger payment from the first manufacturer, because his outside option depends on what she will do with the second. Together with Propositions 6 and 7 it explains why retailers under production economy share with only a subset of suppliers once economies of scale or competition are strong, and why a retailer may share data for free, a practice the diseconomy model cannot produce.

The results are proved in the paper, partly by "it is straightforward" arguments (the proofs of Lemmas 2–5 are omitted). No part of the paper is formalized. A formalization adds a machine-checked account of the equilibrium selection at the boundary payments, where the paper's case analysis is informal, and of the points at which the retailer is indifferent between outcomes.

Difficulty

The pricing stage is a Bayesian game with a continuum of strategies: an informed manufacturer's strategy is an arbitrary square-integrable function of the signal. Lemma 1's uniqueness needs the Assumption (without it the manufacturer's problem is not concave) and a conditional-expectation argument, not a finite-dimensional computation. The comparisons of Lemma 5 are sign conditions on rational functions of $(c_e, \phi)$ whose thresholds $c_e^a$ , $c_e^N$ are implicit roots. The contracting stage is where the naive argument fails: at the boundary payments several equilibria give the retailer the same payoff but the manufacturers different payoffs, so "the" outcome is not well defined there, and a direct comparison of closed-form profits at the paper's selected equilibria does not cover every equilibrium.

Formalization scope

Lean represents manufacturers by Fin 2, statuses by an inductive type with informed and uninformed, and a pricing strategy by a function of the signal value. The committed conventions are these.

Admissible strategies are measurable with square-integrable $w_i(Y)$ , and constant for an uninformed manufacturer; ex ante optimality over them is the Bayesian equilibrium condition.
The retailer's rule is a best response for every wholesale price pair and signal value, off path included.
The production cost is the uncapped quadratic $bq - c_e q^2$ . The paper caps the quantity at $\bar q = b/(2c_e)$ but assumes the cap is reached with negligible probability (footnote 11, p. 251) and computes every result of §4.2 and §6 without it. The condition $b < a$ of that footnote is not imposed.
Contracting uses pure strategies, nonnegative payments, and no free-sharing move after a rejection.
A concurrent outcome is a payment and a pure equilibrium whose retailer payoff equals the supremum of her payoffs over Pareto-optimal equilibria. The supremum is not always attained: for large $c_e$ the paper's optimal payment $\pi_M^I(1) - \pi_M(0)$ makes $(U,U)$ an equilibrium that Pareto-dominates the one-informed outcome it selects.
Threshold statements take the two-clause form: the stated value of $n$ is attained on each region with its printed endpoints, and is the only value on the region's interior. Thresholds depend only on $\phi$ and are quantified before all other parameters.
The manufacturers' comparison in the goal excludes at most two values of $c_e$ . At the thresholds $c_e^C$ , $c_e^S$ outcomes with different manufacturer totals coexist, and the universal comparison fails.
A correction of the paper. At $c_e^* = (2+3\phi)/[(1+2\phi)(1+\phi)]$ , which lies in $(1/(1+\phi), 2/(1+\phi))$ , the slope of the best-response wholesale price (2) is exactly $-1$ . The equations $w_i = \hat w_i(w_j)$ are then singular, and every status profile has a continuum of pricing equilibria (for $n = 0$ , $w_{1,2} = \bar w \pm t$ for every $t$ ) whose ex ante profits differ. Lemma 1's uniqueness claim fails there, so do the §4.2 identities for every equilibrium family, and so does every statement built on them. Each statement that quantifies over all pricing equilibria therefore assumes $c_e \ne c_e^*$ ; existence is still asserted at $c_e^*$ .

The ex ante profits in every statement are those of an equilibrium of the pricing game on the signal model, not the §4.2 closed forms; a formalization that defined them by the closed forms would reduce the goal to algebra and a $2 \times 2$ game, and is ruled out. The model layer (signal model, pricing equilibrium, payoff table, both contracting games) is shared, name for name, with the production diseconomy mission. Contributions are welcome on each milestone, and on reusable pieces: linear-expectation signals, and pointwise optimization under conditional expectation.

Selected references

Shang W., Ha A. Y., Tong S., Information Sharing in a Supply Chain with a Common Retailer, Management Science 62(1):245–263, 2016. https://doi.org/10.1287/mnsc.2014.2127
Ericson W. A., A note on the posterior mean of a population mean, Journal of the Royal Statistical Society B 31(2):332–334, 1969 (cited for the formula of $\beta(t,\sigma)$ , which this mission does not use).
Vives X., Oligopoly Pricing: Old Ideas and New Tools, MIT Press, 1999, §2.7.2.
Li L., Information sharing in a supply chain with horizontal competition, Management Science 48(9):1196–1212, 2002. https://doi.org/10.1287/mnsc.48.9.1196.177

19 thms3 active usersReviewed

Completed

Dynamic Programming Operations Research Optimization·Captain: mikedeng1

Analysis and Algorithms for Service Parts Supply Chains I: Optimality of Order-Up-To Policies by Dynamic ProgrammingTextbook

Motivation

A stocking point that reviews its inventory once per period and must decide how much to order is the basic unit of every service parts supply chain: each warehouse, each repair depot and each forward location in the networks studied later in Muckstadt's Analysis and Algorithms for Service Parts Supply Chains (Springer 2005, DOI 10.1007/b138879) faces this decision for thousands of items. The practical rule used everywhere is the order-up-to (base-stock) rule: bring the inventory position up to a fixed target level whenever it falls below it, and order nothing otherwise. Chapter 2 of the book justifies this rule for a single item with linear costs, following the dynamic-programming argument of Karlin and Scarf, and the rest of the book takes the rule as given.

Timeline. Arrow, Harris and Marschak posed the periodic-review inventory problem as a dynamic program in 1951 (Econometrica). Bellman, Glicksberg and Gross showed in 1955 that with linear ordering cost and convex expected holding and shortage costs the optimal policy has a critical-number form (Management Science). Karlin and Scarf (1958) extended the analysis to a positive lead time, the setting of the book's Theorems 1–3. Veinott (1965) gave conditions under which a base-stock policy is optimal in multi-product, nonstationary models (Management Science).

Setting

One item is stocked at one location. At the start of each period the inventory position $y$ is observed and a quantity $u \ge 0$ is ordered; with lead time one period it arrives at the start of the next period. Demand in each period is independent of other periods and has a density $g$ on $(0,\infty)$ that is positive and continuous. Unmet demand is backordered. Costs are linear: $c$ per unit ordered, $h$ per unit on hand at the end of a period, $b$ per unit backordered at the end of a period, and future costs are discounted by $\alpha \in (0,1)$ . The one-period cost is

L(y) = \begin{cases} h\displaystyle\int_0^y (y-x)g(x)\,dx + b\int_y^\infty (x-y)g(x)\,dx, & y > 0,\\[1mm] b\displaystyle\int_0^\infty (x-y)g(x)\,dx, & y \le 0. \end{cases}

The book assumes throughout that $b > \frac{1-\alpha}{\alpha}\,c$ : the backorder cost outweighs the saving from deferring a purchase.

The $n$ -period value functions are $f_1 = L$ and, for $n \ge 2$ ,

f_n(y) = \min_{u \ge 0}\Big\{ c\,u + L(y) + \alpha\int_0^\infty f_{n-1}(y+u-x)\,g(x)\,dx \Big\}.

An order $u$ is optimal at $y$ if it attains this minimum over all $u \ge 0$ . The order-up-to rule with level $s$ orders $u(y) = \max\{0, s-y\}$ . The marginal function of eq. (2.8) is $F_n(w) = c + \alpha\int_0^\infty f_n'(w-x)\,g(x)\,dx$ . In Lean these are Model, Model.L, Model.f, Model.IsOptimalOrder, Model.IsOrderUpToOptimal and Model.F in the namespace ServiceParts.BaseStock.

Formalization targets

Goal: Theorem 2 (p. 18) in its $n$ -period form

For every horizon $n \ge 2$ , either there is a real level $s_n^*$ with

u_n^*(y) = \max\{0,\ s_n^* - y\} \ \text{optimal for every } y,

or ordering nothing is optimal for every $y$ (level $-\infty$ ); and there is $N \ge 2$ such that the level is real for all $n \ge N$ . No value of $s_n^*$ is fixed: the goal asserts the shape of the optimal policy only.

Milestones, in attack order

$L$ is convex (p. 21).
Every $f_n$ , $n \ge 1$ , is convex (p. 19, property (c)).
Every $f_n$ is differentiable with $-(c+b) \le f_n' \le h/(1-\alpha)$ (p. 20).
Property (b): given an optimal real level $s$ for horizon $n \ge 2$ , $f_n' = -c + L'$ below $s$ and $f_n' = L' + \alpha\int_0^\infty f_{n-1}'(\cdot - x)g(x)\,dx$ from $s$ on (p. 19).
Given such a level, $F_n(w) \to (1-\alpha)c - b\alpha < 0$ as $w \to -\infty$ (p. 19).
Property (a): optimal real levels are nondecreasing in the horizon, $s_n^* \le s_{n+1}^*$ (p. 18).

Significance

The theorem reduces an infinite-dimensional control problem, a choice of order quantity for every possible inventory position, to one number per period. Every later chapter of the book (Palm's theorem for $(s-1,s)$ policies, METRIC-type stock level optimization, allocation in multi-echelon systems) parameterizes policies by such stock levels; this is where the book justifies that parameterization.

The result is classical and proved in many texts. On Prove2Me the mission produces a machine-checked finite-horizon version with a continuous demand density, including the calculus the proof needs: convexity of an expected cost defined by integrals against a density, differentiation under the integral sign in the recursion, and the one-sided behaviour of the value function at the order-up-to level. Existing platform results on base-stock optimality (Veinott's multi-product model, advance demand information) use different models and different arguments; none covers this recursion.

Difficulty

The argument is an induction on $n$ whose hypothesis carries convexity, the derivative formula (b), and bounds on $f_n'$ . The delicate step is the existence of a finite root of $F_n$ : its limit at $-\infty$ depends on whether the previous level was finite. For $n = 1$ nothing is ordered and the limit is $c - b\alpha$ , which the assumption $b > \frac{1-\alpha}{\alpha}c$ does not make negative. The book's base case ("left to the reader") therefore fails when $c > \alpha b$ : with $\alpha = \tfrac12$ , $c = 1$ , $b = \tfrac32$ the two-period problem never orders. The goal is corrected accordingly.

Two properties the book's induction also carries are not usable as printed. Property (d), $f_n' \le f_{n-1}'$ , is false: for large $y$ , $f_n'(y)$ approaches $h(1 + \alpha + \dots + \alpha^{n-1})$ , which increases with $n$ . The second-derivative clause of property (c) fails at $y = 0$ whenever $g(0^+) > 0$ . A solver cannot follow the printed induction step for step; property (a), which the book derives from (d), is true and is a milestone in its own right.

Formalization scope

Horizon. The book states Theorem 2 for "the optimal policy" without a horizon. Its proof is an induction on a finite horizon, and the passage $n \to \infty$ is left as a conjecture (p. 21). The goal is the finite-horizon theorem; no infinite-horizon value function is constructed.
Lead time. The proof sets $\tau = 1$ "to simplify notation"; so does the formalization. Theorem 1 (dependence on the inventory position only) and Theorem 3 (general $\tau$ , whose level equation is the conjectured infinite-horizon one) are not stated.
Level $-\infty$ . The goal allows "never order" as the order-up-to rule with level $-\infty$ and adds eventual finiteness; see Difficulty.
Added hypotheses. $c \ge 0$ , $h > 0$ (the book uses $\lim_{w\to\infty} f_n'(w - x) > 0$ ), $0 < \alpha$ (the book divides by $\alpha$ ), and a finite mean $\int_0^\infty x\,g(x)\,dx < \infty$ (without it $L$ is infinite). All are fields of Model, together with positivity and continuity of $g$ on $(0,\infty)$ , $\int_0^\infty g = 1$ , and $b > \frac{1-\alpha}{\alpha}c$ .
Minimum and derivatives. $f_n$ is defined with the infimum over $u \ge 0$ of a nonnegative quantity; optimality is always against every $u' \ge 0$ . Statements about $f_n'$ assert differentiability (Differentiable, HasDerivAt) and do not read deriv as evidence of it.
Levels. The book's $s_n^*$ is "the unique solution of (2.6)"; milestones take any real level at which the order-up-to rule is optimal.

A recursion in which ordering is restricted to order-up-to rules, or in which $f_n$ is defined through $s_n^*$ , would make the goal a tautology; here $f_n$ is defined by minimization over all $u \ge 0$ and optimality is checked against all orders.

Needed infrastructure: convexity and differentiation of parametric integrals against a density on $(0,\infty)$ , and minimization of a differentiable convex function over a half-line. Both are reusable for the other stochastic inventory missions on the platform. Proofs of individual milestones are welcome independently of the goal.

Selected references

J. A. Muckstadt, Analysis and Algorithms for Service Parts Supply Chains, Springer Series in Operations Research and Financial Engineering, 2005, Chapter 2, Section 2.1. https://doi.org/10.1007/b138879
S. Karlin and H. Scarf, Inventory models of the Arrow–Harris–Marschak type with time lag, in K. J. Arrow, S. Karlin and H. Scarf (eds.), Studies in the Mathematical Theory of Inventory and Production, Stanford University Press, 1958 (no DOI).
K. J. Arrow, T. Harris and J. Marschak, Optimal inventory policy, Econometrica 19(3), 1951, 250–272. https://doi.org/10.2307/1906814
R. Bellman, I. Glicksberg and O. Gross, On the optimal inventory equation, Management Science 2(1), 1955, 83–104. https://doi.org/10.1287/mnsc.2.1.83
A. F. Veinott Jr., Optimal policy for a multi-product, dynamic, nonstationary inventory problem, Management Science 12(3), 1965, 206–222. https://doi.org/10.1287/mnsc.12.3.206

9 thms3 active usersReviewed

Inventory and Supply Chain

Missions

On Properties of Stochastic Inventory Systems I: Using the EOQ Order Quantity in the Stochastic (Q, r) Model Raises Costs by at Most 1/8Research Paper

Motivation

Setting

Formalization targets

Goal: Theorem 5

Milestones

Significance

Difficulty

Formalization scope

Selected references

On Properties of Stochastic Inventory Systems II: The Optimal Order Quantity of the Stochastic (Q, r) Model Exceeds the EOQ by a Bounded GapResearch Paper

Motivation

Setting

Formalization targets

Goal: Theorem 2 (p. 96)

Milestones

Significance

Difficulty

Formalization scope

Selected references

On Properties of Stochastic Inventory Systems III: Bounds between the Optimal Costs of the Stochastic (Q, r) Model and the EOQ ModelResearch Paper

Motivation

Setting

Formalization targets

Goal: Theorem 3 (p. 97)

Milestones

Significance

Difficulty

Formalization scope

Selected references

On Properties of Stochastic Inventory Systems IV: The (Q, r) Cost Is Flatter in the Order Quantity than the EOQ CostResearch Paper

Motivation

Setting

Formalization targets

Goal: Theorem 4

Milestones

Significance

Difficulty

Formalization scope

Selected references

Single-Period Multiproduct Inventory Models with Substitution: No Order for a Product Stocked Above Its Base-Stock LevelResearch Paper

Motivation

Setting

Formalization targets

Goal: Theorem 2

Milestones

Significance

Difficulty

Formalization scope

Selected references

Integrating Replenishment Decisions with Advance Demand Information II: With Zero Set-up Cost the Myopic Base-Stock Policy Is Optimal When Myopic Levels Are NondecreasingResearch Paper

Motivation

Setting

Formalization targets

Goal: Theorem 5 (p. 1352)

Milestones: Theorem 4 (p. 1351)

Significance

Difficulty

Formalization scope

Selected references

A Supply Chain Theory of Factoring and Reverse Factoring 1: The Supplier's Equilibrium Choice Among Recourse, Non-Recourse and Reverse FactoringResearch Paper

Motivation

Setting

Formalization targets

Goal: Proposition 5

Milestones

Significance

Difficulty

Formalization scope

Selected references

A Supply Chain Theory of Factoring and Reverse Factoring 2: The Retailer's Optimal Reverse Factoring Payment ExtensionResearch Paper

Motivation

Setting

Formalization targets

Goal: Proposition 6

Milestones, in attack order

Significance

Difficulty