Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5(e) — every limit point (r∗(i),S∗(i))(r^*(i),S^*(i))(r∗(i),S∗(i)) of the nnn-stage parameters gives an optimal world-dependent (r,S)(r,S)(r,S) policy

Open
SongZipkinFluct.FixedCost.theorem5e

by tianyipeng · Nov 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

inventorymarkov-decision-processss-policy

Fixed-cost model of §3.2: standing hypotheses, Assumption 1 (αcˉ<p\alpha\bar c < pαcˉ<p), Kˉ>0\bar K>0Kˉ>0 so that K=KˉF~L(α)>0K = \bar K\tilde F_L(\alpha) > 0K=KˉF~L​(α)>0, and terminal cost W0=W∞W_0 = W_\inftyW0​=W∞​ of the linear model. For n≥1n\ge1n≥1 let Sn∗(i)S^*_n(i)Sn∗​(i) be the smallest minimizer of Gn(i,⋅)G_n(i,\cdot)Gn​(i,⋅) and rn∗(i)r^*_n(i)rn∗​(i) the largest y<Sn∗(i)y < S^*_n(i)y<Sn∗​(i) with Gn(i,y)>K+Gn(i,Sn∗(i))G_n(i,y) > K + G_n(i,S^*_n(i))Gn​(i,y)>K+Gn​(i,Sn∗​(i)) (Theorem 3(b)).

Claim (Theorem 5(e)). Let r∗,S∗:I→Zr^*,S^* : I\to\mathbb Zr∗,S∗:I→Z be such that for every iii the pair (r∗(i),S∗(i))(r^*(i),S^*(i))(r∗(i),S∗(i)) is a limit point of {(rn∗(i),Sn∗(i))}n\{(r^*_n(i),S^*_n(i))\}_n{(rn∗​(i),Sn∗​(i))}n​, i.e. it equals (rn∗(i),Sn∗(i))(r^*_n(i),S^*_n(i))(rn∗​(i),Sn∗​(i)) for infinitely many nnn. Then the stationary world-dependent (r,S)(r,S)(r,S) policy — when the world is in state iii and the inventory position is xxx, order up to S∗(i)S^*(i)S∗(i) if x≤r∗(i)x\le r^*(i)x≤r∗(i) and do not order otherwise — is optimal for the infinite-horizon discounted problem (1) with fixed cost KKK: it is feasible, and from every initial state (i,x)(i,x)(i,x) its expected total discounted cost is at most that of any feasible deterministic history-dependent policy.

Policies are deterministic and may depend on the whole history; costs take values in [0,∞][0,\infty][0,∞] and the infinite-horizon cost is the supremum of the NNN-epoch costs.

Preamble
import Mathlib
import Definitions.Def_SongZipkinFluct_FixedCost_Bounds
import Definitions.Def_SongZipkinFluct_FixedCost_Policy

open Filter
Formal statement
namespace SongZipkinFluct.FixedCost

open Model

/-- Theorem 5(e) (p. 359) of Song and Zipkin (1993). Fixed-cost model of §3.2
(`K = K̄F̃_L(α) > 0`, `W₀ = W_∞` of the linear model). Let `S*_n(i)`, `r*_n(i)` (`n ≥ 1`) be the
parameters of Theorem 3(b). If, for every `i`, `(r*(i), S*(i))` is a limit point of
`n ↦ (r*_n(i), S*_n(i))` (a pair taken for infinitely many `n`), then the world-dependent
`(r, S)` policy with parameters `{(r*(i), S*(i))}` is optimal for the infinite-horizon
problem (1) with fixed cost `K`, among all feasible deterministic history-dependent policies and
from every initial state. -/
theorem theorem5e {I : Type*} [Countable I] [Nonempty I] [DecidableEq I] (M : Model I)
    (hM : M.Standing) (hA1 : M.α * M.cbar < M.p) (hK : 0 < M.Kbar)
    (rs Ss : ℕ → I → ℤ) (hrs : IsStageParams M rs Ss) (rstar Sstar : I → ℤ)
    (hlim : ∀ i, ∃ᶠ n in atTop, rs n i = rstar i ∧ Ss n i = Sstar i) :
    IsOptimal M M.K (rSPolicy rstar Sstar) := 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. 359, Theorem 5(e)

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