Proposition 1(1), p. 16 — HO (one re-solve at ) loses against the hindsight optimum
ProvedResolvingNRM.IRT.prop1_part1_ho_one_resolveConsider the network revenue-management model with customer classes arriving as independent Poisson processes of rates , revenues and a nonnegative bill-of-materials matrix . Let be the policy that, over with , accepts class- customers (when capacity allows) with the thresholded probabilities of Algorithm 3 computed from the DLP solution , namely if , if and otherwise, and then from on follows the hindsight optimum of the remaining horizon with the remaining capacity.
Part 1 of Proposition 1. There are constants and , depending only on , such that for every choice of optimal DLP solutions (selector), every and every capacity vector ,
In the paper , where and depends only on ; since the constant can be taken uniform over the DLP solution, which is why is quantified before the selector, and . This is the first item of Proposition 1 (p. 16), proved in Appendix B.2, Eqs. (14)-(23), using Lemma 5 (stability of the hindsight LP, Reiman and Wang 2008, Thm 4.2) and Lemma 6 (the bound on ). The second item of Proposition 1 follows from this one together with Proposition 5, as in Eqs. (19)-(20).
import Mathlib import Definitions.Def_RLPBidPrice_Unbiased_Model import Definitions.Def_ResolvingNRM_IRT_Model open RLPBidPrice.Unbiased Matrix
namespace ResolvingNRM.IRT
theorem prop1_part1_ho_one_resolve {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (r lam : Fin n → ℝ)
(hlam : ∀ j, 0 < lam j) (hr : ∀ j, 0 ≤ r j) (hA : ∀ l j, 0 ≤ A l j) :
∃ κ : ℝ, 0 < κ ∧ ∃ M : ℝ, ∀ sel : (Fin m → ℝ) → (Fin n → ℝ), IsDLPSelector A r lam sel →
∀ T : ℝ, 1 ≤ T → ∀ C : Fin m → ℝ, 0 ≤ C →
hindsightValue A r lam T C - hoValue A r lam sel 1 T C ≤
M * T * Real.exp (-κ * T ^ (1 / 6 : ℝ)) := by sorry
end ResolvingNRM.IRT