Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 1(1), p. 16 — HO1^11 (one re-solve at T−T5/6T - T^{5/6}T−T5/6) loses O(Te−κT1/6)O(T e^{-\kappa T^{1/6}})O(Te−κT1/6) against the hindsight optimum

Proved
ResolvingNRM.IRT.prop1_part1_ho_one_resolve

by tianyipeng · Nov 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

network-revenue-managementre-solvingregret

Consider the network revenue-management model with nnn customer classes arriving as independent Poisson processes of rates λj>0\lambda_j > 0λj​>0, revenues rj≥0r_j \ge 0rj​≥0 and a nonnegative bill-of-materials matrix AAA. Let HO1\mathrm{HO}^1HO1 be the policy that, over [0,t1∗)[0, t^*_1)[0,t1∗​) with t1∗=T−T5/6t^*_1 = T - T^{5/6}t1∗​=T−T5/6, accepts class-jjj customers (when capacity allows) with the thresholded probabilities of Algorithm 3 computed from the DLP solution x∗=sel(C/T)x^* = \mathrm{sel}(C/T)x∗=sel(C/T), namely 000 if xj∗<λjT−1/4x^*_j < \lambda_j T^{-1/4}xj∗​<λj​T−1/4, 111 if xj∗>λj(1−T−1/4)x^*_j > \lambda_j(1 - T^{-1/4})xj∗​>λj​(1−T−1/4) and xj∗/λjx^*_j/\lambda_jxj∗​/λj​ otherwise, and then from t1∗t^*_1t1∗​ on follows the hindsight optimum of the remaining horizon T5/6T^{5/6}T5/6 with the remaining capacity.

Part 1 of Proposition 1. There are constants κ>0\kappa > 0κ>0 and MMM, depending only on (λ,r,A)(\lambda, r, A)(λ,r,A), such that for every choice of optimal DLP solutions (selector), every T≥1T \ge 1T≥1 and every capacity vector C≥0C \ge 0C≥0,

vHO(T,C)−vHO1(T,C)≤M T e−κT1/6.v^{\mathrm{HO}}(T, C) - v^{\mathrm{HO}^1}(T, C) \le M\, T\, e^{-\kappa T^{1/6}} .vHO(T,C)−vHO1(T,C)≤MTe−κT1/6.

In the paper κ=λmin⁡/(27(α∣Jλ∣+1)2)\kappa = \lambda_{\min}/(27(\alpha|J_\lambda| + 1)^2)κ=λmin​/(27(α∣Jλ​∣+1)2), where Jλ={j:xj∗=λj}J_\lambda = \{j : x^*_j = \lambda_j\}Jλ​={j:xj∗​=λj​} and α\alphaα depends only on AAA; since ∣Jλ∣≤n|J_\lambda| \le n∣Jλ​∣≤n the constant can be taken uniform over the DLP solution, which is why κ\kappaκ is quantified before the selector, TTT and CCC. 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 P(Ec)\mathbb P(E^c)P(Ec)). The second item of Proposition 1 follows from this one together with Proposition 5, as in Eqs. (19)-(20).

Preamble
import Mathlib
import Definitions.Def_RLPBidPrice_Unbiased_Model
import Definitions.Def_ResolvingNRM_IRT_Model

open RLPBidPrice.Unbiased Matrix
Formal statement
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
Source
Bumpensanti, Wang, A Re-solving Heuristic with Uniformly Bounded Loss for Network Revenue Management, arXiv:1802.06192v3, Proposition 1 item 1, p. 16; proof in Appendix B.2, pp. 30-32, Eqs. (14)-(23)

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me