Theorem 3.1 — dual balancing is a 2-approximation for lost sales
ProvedLostSalesBalancing.DualBalancing.theorem_3_1Consider 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 , the information available at the beginning of period is independent of the future demands . If is a feasible dual-balancing policy and is any feasible nonanticipatory policy, then
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 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 -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 ; the cost omits policy-independent initial costs. Holding rates are allowed to be zero, a strengthening of the stationary presentation; no proof step divides by .
import Mathlib import Definitions.Def_LostSalesBalancing_DualBalancing_Model
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.