Theorem 2 — AIM's average expected cost is within (γ+1/γ)ȳ max{b,h}/√T (perishable) and C/√T (non-perishable) of Q(y^NV)
ProvedAIMInventory.Known.theorem_2Let demands be i.i.d. with finite positive mean, let , and let with newsvendor quantity
the distribution function of . Under Assumption 1 the manager knows with . Run the AIM algorithm with scale and any starting level , and let be its order-up-to levels. Then:
- Perishable inventory. For every ,
- Non-perishable inventory. Suppose moreover that (the second half of Assumption 1), and . Then there is a constant such that for every ,
The algorithm sees only censored sales and does not know the demand distribution, yet its long-run average cost approaches the newsvendor cost, which is the optimal cost of a manager who knows the distribution, at rate .
The constant may depend on everything except . The paper's explicit formula (9) for rests on Proposition 4 (i), which is false as printed; with the corrected Proposition 4 (i) the same proof gives
This formula is not part of the statement.
Formalization Note The AIM run is defined from the demand path, and the expectation is the integral over the i.i.d. path law; the integrand is bounded on the run (all levels lie in ), so the integral is a genuine expectation. are implicit in the paper (they appear in denominators), and the positive mean of is part of the reused demand-law structure (in the non-perishable case it already follows from ). In the non-perishable case the constant is chosen after and all other data, before .
import Mathlib import Definitions.Def_AIMInventory_Known_AIM open MeasureTheory open scoped NNReal
namespace AIMInventory.Known
/-- Theorem 2, p. 7: under Assumption 1 (`y^NV ≤ ȳ`), the AIM run satisfies, for every `T ≥ 1`,
`E[(1/T) Σ_{t=1}^T Q(y_t)] − Q(y^NV) ≤ (γ + 1/γ) ȳ max{b, h} / √T` in the perishable case; and
in the non-perishable case, if moreover `0 < ρ < E[D_1]`, `E[D_1^6] < ∞` and
`γ ≤ ρ max{b, h}/(hȳ)`, there is a constant `C` with
`E[(1/T) Σ_{t=1}^T Q(y_t)] − Q(y^NV) ≤ C / √T` for every `T ≥ 1`. -/
theorem theorem_2 (P : CappedBaseStock.DemandLaw) (h b γ ybar yhat1 : ℝ)
(hh : 0 < h) (hb : 0 < b) (hγ : 0 < γ) (hybar : 0 < ybar)
(hyhat1 : yhat1 ∈ Set.Icc 0 ybar)
(hNV : ((LostSalesOrderUpTo.Asymptotic.newsvendorLevel P.law h b : ℝ≥0) : ℝ) ≤ ybar) :
(∀ T : ℕ, 1 ≤ T →
avgExpectedCost P .perishable ybar γ b h yhat1 T
- Q P h b (LostSalesOrderUpTo.Asymptotic.newsvendorLevel P.law h b : ℝ)
≤ (γ + 1 / γ) * (ybar * max b h / Real.sqrt T)) ∧
(∀ ρ : ℝ, 0 < ρ → ρ < CappedBaseStock.mean P →
Integrable (fun x : ℝ≥0 => (x : ℝ) ^ 6) P.law →
γ ≤ ρ * max b h / (h * ybar) →
∃ C : ℝ, ∀ T : ℕ, 1 ≤ T →
avgExpectedCost P .nonPerishable ybar γ b h yhat1 T
- Q P h b (LostSalesOrderUpTo.Asymptotic.newsvendorLevel P.law h b : ℝ)
≤ C / Real.sqrt T) := by sorry
end AIMInventory.Known
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.