Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 2 for arbitrary (s,S)(s,S)(s,S) choices: C(πFIFO)≤c(fL0;K0+Kmax⁡,s0,S0)+∑i(c(Fi;Ki,si,Si)+mirrorAvgi)C(\pi_{\rm FIFO})\le c(f_{L_0};K_0+K_{\max},s_0,S_0)+\sum_i\bigl(c(F_i;K_i,s_i,S_i)+\mathrm{mirrorAvg}_i\bigr)C(πFIFO​)≤c(fL0​​;K0​+Kmax​,s0​,S0​)+∑i​(c(Fi​;Ki​,si​,Si​)+mirrorAvgi​)

Proved
OWMR.fifo_upper_gen

by Ming Hu · Nov 17, 2026 · Mathlib 0df444a (Lean v4.33.1)

approximation-algorithmsinventoryinventory-theoryoperations-researchrenewal-theorystochastic-control

Fix a network NNN with n≥1n\ge1n≥1 retailers under the standing assumptions, a valid initial state xxx, and FIFO choices c=(si,Si,ai,s0,S0)c=(s_i,S_i,a_i,s_0,S_0)c=(si​,Si​,ai​,s0​,S0​) with si≤Sis_i\le S_isi​≤Si​ for every iii and s0≤S0s_0\le S_0s0​≤S0​; no optimality of the choices is assumed. Then the deterministic FIFO policy of Definition 1, with the initialization of Appendix B, satisfies

C(πFIFO)≤c(fL0;K0+Kmax⁡,s0,S0)+∑i(c(Fi;Ki,si,Si)+mirrorAvgi(si,Si,ai)),C(\pi_{\rm FIFO})\le c\bigl(f_{L_0};K_0+K_{\max},s_0,S_0\bigr)+\sum_i\Bigl(c\bigl(F_i;K_i,s_i,S_i\bigr)+\mathrm{mirrorAvg}_i(s_i,S_i,a_i)\Bigr),C(πFIFO​)≤c(fL0​​;K0​+Kmax​,s0​,S0​)+i∑​(c(Fi​;Ki​,si​,Si​)+mirrorAvgi​(si​,Si​,ai​)),

where c(f;K,s,S)c(f;K,s,S)c(f;K,s,S) (ssAvgCost) is the long-run average cost of the (s,S)(s,S)(s,S) policy with setup cost KKK per order and cost fff of the post-order position, fL0(y)=E ϕ(y−D(L0))f_{L_0}(y)=\mathbb E\,\phi(y-D^{(L_0)})fL0​​(y)=Eϕ(y−D(L0​)) is the supplier's lead-time loss on aggregate demand, and mirrorAvgi\mathrm{mirrorAvg}_imirrorAvgi​ is retailer iii's long-run average mirror loss ϕ(ai−P^i,t)\phi(a_i-\widehat P_{i,t})ϕ(ai​−Pi,t​).

This is Proposition 2 for general retailer and supplier (s,S)(s,S)(s,S) choices, as used for πDFR(θ)\pi_{\rm DFR}(\theta)πDFR​(θ) in Step 4 of the proof of Theorem D.1.

Preamble
import Definitions.Def_owmr_fifo_policy

open scoped ENNReal
Formal statement
namespace OWMR
theorem fifo_upper_gen {n : ℕ} (hn : 0 < n) (N : Network n) (hN : N.Standing)
    (x : InitState n) (hx : x.Valid) (c : FIFOChoice n) (hsS : ∀ i, c.s i ≤ c.S i)
    (hs0 : c.s0 ≤ c.S0) :
    (fifoPolicy N x c).avgCost N x ≤ ssAvgCost N.aggregate N.fL0 (N.K0 + N.Kmax) c.s0 c.S0
      + ∑ i, (ssAvgCost (N.marginal i) (N.F i) (N.K i) (c.s i) (c.S i)
        + mirrorAvg (N.marginal i) N.h N.p (c.s i) (c.S i) (c.a i)) := by sorry
end OWMR
Source
M. Hu, "A 5/2 Guarantee for Echelon Stock (s,S) Policies in One-Warehouse Multi-Retailer Systems", working paper (manuscript of November 2026), Section 5, Proposition 2 (Physical Upper Bound), proved in Appendix B, as applied in Step 4 of the proof of Theorem D.1, p. E.27 ("the proof of Proposition 2 ... applies to these policies and centers").

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