Proposition 3 — v^DLP − v^FR = O(√T), uniformly in the capacities
ProvedResolvingNRM.FRUpper.fr_dlp_gap_sqrtConsider the network revenue management model with customer classes and resources: Poisson arrival rates , revenues , and a nonnegative bill-of-materials matrix . For an integer horizon and initial capacity , let be the value of the deterministic LP (2), and the expected revenue of the Frequent Re-solving policy (Algorithm 2), which re-solves the LP at every integer time and uses any optimal solution. There is a constant , depending only on , and , such that for every optimal-solution selector, every and every ,
Since upper-bounds the expected revenue of every admissible policy, the revenue loss of FR is without any nondegeneracy assumption on the DLP. The paper combines this with Proposition 2, an lower bound on a degenerate instance, to conclude there.
Formalization Note. "" is formalized with the constant chosen after and before the selector, and ; this is the paper's statement that the constant "does not depend on the starting capacity ". The paper's threshold in the definition of (p. 7) is dropped: the bound is stated for all , which is equivalent because and , so the gap is bounded on any finite range of uniformly in . , , , 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
/-- Proposition 3, p. 19: `v^DLP − v^FR = O(√T)`, with a constant that depends on `λ`, `r` and `A`
but not on the starting capacity `C` (nor on the optimal LP solutions chosen). -/
theorem fr_dlp_gap_sqrt {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) :
∃ M : ℝ, ∀ sel : (Fin m → ℝ) → (Fin n → ℝ), ResolvingNRM.IRT.IsDLPSelector A r lam sel →
∀ T : ℕ, 1 ≤ T → ∀ C : Fin m → ℝ, 0 ≤ C →
ResolvingNRM.IRT.dlpValue A r lam T C - frValue A r lam sel T C ≤ M * Real.sqrt T := by sorry
end ResolvingNRM.FRUpper
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.