Proposition 5, p. 27 — static probabilistic allocation loses against the DLP, uniformly in
ProvedResolvingNRM.IRT.spa_dlp_gap_sqrtFix the data of the network revenue-management model: Poisson rates , revenues and a nonnegative bill-of-materials matrix . The static probabilistic allocation (SPA) heuristic (Algorithm 1) solves the DLP once at , obtaining an optimal , and accepts each class- arrival with probability whenever capacity allows. Let be its expected revenue.
There is a constant , depending only on , such that for every choice of optimal DLP solutions, every horizon and every capacity ,
The bound holds uniformly in the capacity, with no scaling assumption linking and ; this is what lets the proof of Theorem 1 apply it to the last epoch of IRT, whose starting capacity is random.
Formalization Note SPA is the member of the IRT family (one epoch, plain probabilities from ). is chosen before the selector, and : the paper's constant does not depend on which optimal solution the LP returns. The horizon is a positive real, because the proof of Theorem 1 applies the result on the sub-horizon (eq. (11)). The standing assumptions , , , are those of Sec. 2, p. 7, left implicit on the page.
import Mathlib import Definitions.Def_RLPBidPrice_Unbiased_Model import Definitions.Def_ResolvingNRM_IRT_Model open RLPBidPrice.Unbiased Matrix
namespace ResolvingNRM.IRT
theorem spa_dlp_gap_sqrt {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) :
∃ M : ℝ, ∀ sel : (Fin m → ℝ) → (Fin n → ℝ), IsDLPSelector A r lam sel →
∀ T : ℝ, 0 < T → ∀ C : Fin m → ℝ, 0 ≤ C →
dlpValue A r lam T C - irtValue A r lam sel 0 T C ≤ M * Real.sqrt T := by sorry
end ResolvingNRM.IRT
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.