p. 36 — v^DLP − v^FR ≤ Σ_l r^l_max K_l (2√T + √2) + n r_max (log T + 1) + n r_max λ_max
ProvedResolvingNRM.FRUpper.fr_dlp_gap_explicitConsider the network revenue management model with Poisson rates , revenues , nonnegative consumption matrix , initial capacity , and an integer horizon . Let be the DLP value and the expected revenue of the FR policy (Algorithm 2) with any optimal-solution selector. With , , and ,
This is the explicit form of Proposition 3: every constant depends on , and only, and none on the capacity .
Formalization Note. The bound is the last display of the proof of Proposition 3 (p. 36) with the constant of Lemma 8 corrected from to (see the Lemma 8 item; the printed constant is false). The printed sum over is read as . is the natural logarithm. , , , 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
/-- The explicit bound at the end of the proof of Proposition 3, App. C.2, p. 36, with the
corrected Lemma 8 constant `K_l = √(∑_j a_lj² λ_j)`:
`v^DLP − v^FR ≤ ∑_l r^l_max K_l (2√T + √2) + n r_max (log T + 1) + n r_max λ_max`. -/
theorem fr_dlp_gap_explicit {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 : ℕ) (hT : 1 ≤ T) (C : Fin m → ℝ) (hC : 0 ≤ C) :
ResolvingNRM.IRT.dlpValue A r lam T C - frValue A r lam sel T C
≤ (∑ l, rmaxRes A r l * Kres A lam l) * (2 * Real.sqrt T + Real.sqrt 2)
+ n * rMax r * (Real.log T + 1) + n * rMax r * lamMax lam := by sorry
end ResolvingNRM.FRUpper
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.