Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3.1 — dual balancing is a 2-approximation for lost sales

Proved
LostSalesBalancing.DualBalancing.theorem_3_1

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

approximation-algorithminventorylost-salesp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Consider a finite-horizon lost-sales inventory system with nonnegative, finite-mean demands, a positive integer lead time, nonnegative initial stock and pipeline orders, time-dependent nonnegative holding rates, and nonnegative ordering and lost-sales penalty rates that are non-increasing over time. Assume the demands are independent: for every period jjj, the information Fj\mathcal F_jFj​ available at the beginning of period jjj is independent of the future demands (Dj,…,DT)(D_j,\ldots,D_T)(Dj​,…,DT​). If BBB is a feasible dual-balancing policy and PPP is any feasible nonanticipatory policy, then

E[C(B)]≤2E[C(P)].E[C(B)]\le 2E[C(P)].E[C(B)]≤2E[C(P)].

In particular, if an optimal policy exists, the dual-balancing policy's expected cost is at most twice its expected cost.

Formalization Note The paper states the ratio relative to OPT; quantifying over every feasible PPP gives the same guarantee without assuming an optimum is attained. The paper assumes independent demands but permits beginning-of-period information beyond past demands, so each information σ\sigmaσ-algebra is required independent of its future demand vector. The dual-balancing predicate requires integrable marginal costs, preventing default-valued conditional expectations. Expected costs are lower Lebesgue integrals in [0,∞][0,\infty][0,∞]; the cost CCC omits policy-independent initial costs. Holding rates are allowed to be zero, a strengthening of the stationary h>0h>0h>0 presentation; no proof step divides by hhh.

Preamble
import Mathlib
import Definitions.Def_LostSalesBalancing_DualBalancing_Model
Formal statement
namespace LostSalesBalancing.DualBalancing

open MeasureTheory ProbabilityTheory
open LeviBalancing.DualBalancing
open scoped ENNReal

/-- Theorem 3.1: the dual-balancing policy costs at most twice every feasible
nonanticipatory policy, including any optimum when one exists. -/
theorem theorem_3_1 {Ω : Type*} [m : MeasurableSpace Ω]
    (ℱ : Filtration ℤ m) (μ : Measure Ω) [IsProbabilityMeasure μ]
    (I : LSInstance) (DP : DemandProcess ℱ μ I.T)
    (hD : IndependentDemands I ℱ μ DP) (B P : ℤ → Ω → ℝ)
    (hB : IsDualBalancingLS I ℱ μ DP.D B)
    (hP : IsFeasiblePolicy I.toInstance ℱ P) :
    expectedCostLS I μ DP.D B ≤ 2 * expectedCostLS I μ DP.D P := by sorry

end LostSalesBalancing.DualBalancing
Source
Levi, Janakiraman, Nagarajan, A 2-Approximation Algorithm for Stochastic Inventory Control Models with Lost Sales, Math. Oper. Res. 33(2) (2008), accepted manuscript p. 16, §3.2, Theorem 3.1; cost generality pp. 5, 11, 14
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