Lemma 8 (corrected) — E[(b_l − b_l(t))⁺] ≤ K_l √(Σ_{i<t} 1/(T−i−1)²) with K_l = √(Σ_j a_lj² λ_j)
ProvedResolvingNRM.FRUpper.lemma8_bound_on_bConsider the network revenue management model with Poisson rates , revenues , nonnegative consumption matrix , initial capacity and an integer horizon . Run the FR policy with any optimal-solution selector, and let and , where is the remaining capacity at the start of period . Then for every resource and every period with ,
The lemma says the average remaining capacity of FR drifts below its initial value by at most in expectation; summed over through eq. (33), it gives the term of Proposition 3.
Formalization Note. The printed lemma has , which is false: in the proof, eq. (69)–(70) uses where the conditional variance of the Poisson() increment is . Counterexample to the printed form: one class, one resource, , , , , ; an exact computation gives , above the printed bound (the corrected bound is ). The statement uses the corrected . The range is where is defined; it keeps every . , , , are the model's standing assumptions (p. 7).
import Mathlib import Definitions.Def_RLPBidPrice_Unbiased_Model import Definitions.Def_ResolvingNRM_FRUpper_Model open RLPBidPrice.Unbiased Matrix
namespace ResolvingNRM.FRUpper
/-- Lemma 8 (Bound on `b_l`), p. 43, with the corrected constant `K_l = √(∑_j a_lj² λ_j)`:
`E[(b_l − b_l(t))⁺] ≤ K_l √(∑_{i=0}^{t-1} 1 / (T − i − 1)²)` for every period `t ≤ T − 1`, where
`b_l = C_l / T` and `b_l(t) = C_l(t) / (T − t)` along FR. -/
theorem lemma8_bound_on_b {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (r lam : Fin n → ℝ)
(hlam : ∀ j, 0 < lam j) (hr : 0 ≤ r) (hA : ∀ l j, 0 ≤ A l j)
(sel : (Fin m → ℝ) → (Fin n → ℝ)) (hsel : ResolvingNRM.IRT.IsDLPSelector A r lam sel)
(T t : ℕ) (ht : t + 1 ≤ T) (C : Fin m → ℝ) (hC : 0 ≤ C) (l : Fin m) :
frStateExp A r lam sel T t (fun c => max (C l / T - c l / ((T : ℝ) - t)) 0) C
≤ Kres A lam l *
Real.sqrt (∑ i ∈ Finset.range t, 1 / ((T : ℝ) - i - 1) ^ 2) := by sorry
end ResolvingNRM.FRUpper
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.