Proposition 1, p. 16 — one re-solve at : regret of HO is , of IRT is
ProvedResolvingNRM.IRT.prop1_one_resolveFix the data of the network revenue-management model: Poisson rates , revenues and a nonnegative bill-of-materials matrix . Consider policies that re-solve the DLP once, at :
- uses thresholded acceptance probabilities from the DLP solution on (probability if , else if , else ), re-solves at with the remaining capacity over the remaining time , and uses plain probabilities on ;
- follows on and then earns the hindsight optimum of the remaining problem on .
There are constants and , depending only on , such that for every choice of optimal DLP solutions, every and every capacity :
- ;
- .
The first part is the induction step of the proof of Theorem 1 (applied on each sub-horizon ); the second shows that a single well-timed re-solve with thresholds already improves SPA's to .
Formalization Note The paper gives with and a constant of the matrix . Here is an existential positive constant chosen before the selector, and : depends on , so a constant uniform in must cover , and the printed value of is derived through Lemma 5, which is false as printed (see the mission description). The standing assumptions , , , are those of Sec. 2, p. 7. The horizon is a real , because the proof of Theorem 1 applies part 1 on the non-integral sub-horizons (eq. (10)).
import Mathlib import Definitions.Def_RLPBidPrice_Unbiased_Model import Definitions.Def_ResolvingNRM_IRT_Model open RLPBidPrice.Unbiased Matrix
namespace ResolvingNRM.IRT
theorem prop1_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 : ℝ)) ∧
hindsightValue A r lam T C - irtValue A r lam sel 1 T C ≤
M * T * Real.exp (-κ * T ^ (1 / 6 : ℝ)) + M * T ^ (5 / 12 : ℝ) := by sorry
end ResolvingNRM.IRT
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.