Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 6 — ΔW_n ≤ ΔW₀, ΔG_n ≤ ΔG₀, and ΔG_n ≤ ΔG⁺ below y⁺_min

Proved
SongZipkinFluct.FixedCost.lemma6

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

inventoryp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1ss-policyvalue-iteration

In the fixed-cost model (standing hypotheses, αcˉ<p\alpha\bar c < pαcˉ<p, K>0K > 0K>0, W0=W∞W_0 = W_\inftyW0​=W∞​ and G0=G∞G_0 = G_\inftyG0​=G∞​ of the linear model), for every world state iii, every integer xxx and every n≥1n \ge 1n≥1:

  1. ΔWn(i,x)≤ΔW0(i,x)\Delta W_n(i, x) \le \Delta W_0(i, x)ΔWn​(i,x)≤ΔW0​(i,x);
  2. ΔGn(i,x)≤ΔG0(i,x)\Delta G_n(i, x) \le \Delta G_0(i, x)ΔGn​(i,x)≤ΔG0​(i,x);
  3. ΔGn(i,x)≤ΔG+(i,x)\Delta G_n(i, x) \le \Delta G^+(i, x)ΔGn​(i,x)≤ΔG+(i,x) whenever x<ymin⁡+x < y^+_{\min}x<ymin+​,

where Δf(i,x)=f(i,x+1)−f(i,x)\Delta f(i, x) = f(i, x+1) - f(i, x)Δf(i,x)=f(i,x+1)−f(i,x), y+(i)y^+(i)y+(i) is the smallest minimizer of G+(i,⋅)G^+(i, \cdot)G+(i,⋅) and ymin⁡+=min⁡iy+(i)y^+_{\min} = \min_i y^+(i)ymin+​=mini​y+(i).

This comparison of differences between the fixed-cost and the linear-cost iterates is what makes the lower bounds of Theorem 4 possible; it depends on the choice of W0W_0W0​ as the linear model's optimal cost.

Preamble
import Mathlib
import Definitions.Def_SongZipkinFluct_FixedCost_Bounds

open Filter Topology
Formal statement
namespace SongZipkinFluct.FixedCost

open Model

/-- Lemma 6 (p. 358; proof pp. 367–368) of Song and Zipkin (1993). Fixed-cost model of §3.2
(`K = K̄F̃_L(α) > 0`, `W₀ = W_∞` and `G₀ = G_∞` of the linear model). For any fixed `x` and
all `n ≥ 1`:

* (a) `ΔW_n(i, x) ≤ ΔW₀(i, x)`;
* (b) `ΔG_n(i, x) ≤ ΔG₀(i, x)`;
* (c) `ΔG_n(i, x) ≤ ΔG⁺(i, x)` for `x < y⁺_min`, where `y⁺(i)` is the smallest minimizer of
  `G⁺(i, ·)` and `y⁺_min = min_i y⁺(i)`.

Formalization Note: `Δf(i, x) = f(i, x + 1) − f(i, x)` (p. 354); `i` is universally
quantified. In (c), `y⁺` and `y⁺_min` are taken through their defining properties. -/
theorem lemma6 {I : Type*} [Countable I] [Nonempty I] [DecidableEq I] (M : Model I)
    (hM : M.Standing) (hA1 : M.α * M.cbar < M.p) (hK : 0 < M.Kbar) :
    ∀ n : ℕ, 1 ≤ n → ∀ (i : I) (x : ℤ),
      diff (Wfix M n) i x ≤ diff (Wlin M) i x ∧
      diff (Gfix M n) i x ≤ diff (Glin M) i x ∧
      ∀ (yplus : I → ℤ) (ymin : ℤ), IsYPlus M yplus → IsYPlusMin yplus ymin → x < ymin →
        diff (Gfix M n) i x ≤ diff M.Gplus i x := by sorry

end SongZipkinFluct.FixedCost
Source
Song and Zipkin, Inventory Control in a Fluctuating Demand Environment, Oper. Res. 41(2):351–370 (1993), DOI 10.1287/opre.41.2.351, p. 358, Lemma 6 (proof pp. 367–368)
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me