Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 1, p. 16 — one re-solve at T−T5/6T - T^{5/6}T−T5/6: regret of HO1^11 is O(Te−κT1/6)O(Te^{-\kappa T^{1/6}})O(Te−κT1/6), of IRT1^11 is O(Te−κT1/6)+O(T5/12)O(Te^{-\kappa T^{1/6}}) + O(T^{5/12})O(Te−κT1/6)+O(T5/12)

Proved
ResolvingNRM.IRT.prop1_one_resolve

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

network-revenue-managementp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1poissonre-solving

Fix the data of the network revenue-management model: Poisson rates λj>0\lambda_j > 0λj​>0, revenues rj≥0r_j \ge 0rj​≥0 and a nonnegative bill-of-materials matrix AAA. Consider policies that re-solve the DLP once, at t1∗=T−T5/6t^*_1 = T - T^{5/6}t1∗​=T−T5/6:

  • IRT1\mathrm{IRT}^1IRT1 uses thresholded acceptance probabilities from the DLP solution x0=sel(C/T)x^0 = \mathrm{sel}(C/T)x0=sel(C/T) on [0,t1∗)[0, t^*_1)[0,t1∗​) (probability 000 if xj0<λjT−1/4x^0_j < \lambda_j T^{-1/4}xj0​<λj​T−1/4, else 111 if xj0>λj(1−T−1/4)x^0_j > \lambda_j(1 - T^{-1/4})xj0​>λj​(1−T−1/4), else xj0/λjx^0_j/\lambda_jxj0​/λj​), re-solves at t1∗t^*_1t1∗​ with the remaining capacity C(t1∗)C(t^*_1)C(t1∗​) over the remaining time T5/6T^{5/6}T5/6, and uses plain probabilities xj1/λjx^1_j/\lambda_jxj1​/λj​ on [t1∗,T][t^*_1, T][t1∗​,T];
  • HO1\mathrm{HO}^1HO1 follows IRT1\mathrm{IRT}^1IRT1 on [0,t1∗)[0, t^*_1)[0,t1∗​) and then earns the hindsight optimum of the remaining problem on [t1∗,T][t^*_1, T][t1∗​,T].

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, every T≥1T \ge 1T≥1 and every capacity C≥0C \ge 0C≥0:

  1. vHO(T,C)−vHO1(T,C)≤M T e−κT1/6v^{\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;
  2. vHO(T,C)−vIRT1(T,C)≤M T e−κT1/6+M T5/12v^{\mathrm{HO}}(T, C) - v^{\mathrm{IRT}^1}(T, C) \le M\,T\,e^{-\kappa T^{1/6}} + M\,T^{5/12}vHO(T,C)−vIRT1(T,C)≤MTe−κT1/6+MT5/12.

The first part is the induction step of the proof of Theorem 1 (applied on each sub-horizon τu\tau_uτu​); the second shows that a single well-timed re-solve with thresholds already improves SPA's O(T)O(\sqrt T)O(T​) to O(T5/12)O(T^{5/12})O(T5/12).

Formalization Note The paper gives κ=λmin⁡/(27(α∣Jλ∣+1)2)\kappa = \lambda_{\min}/(27(\alpha|J_\lambda|+1)^2)κ=λmin​/(27(α∣Jλ​∣+1)2) with Jλ={j:xj∗=λj}J_\lambda = \{j : x^*_j = \lambda_j\}Jλ​={j:xj∗​=λj​} and a constant α\alphaα of the matrix AAA. Here κ\kappaκ is an existential positive constant chosen before the selector, TTT and CCC: JλJ_\lambdaJλ​ depends on C/TC/TC/T, so a constant uniform in CCC must cover ∣Jλ∣≤n|J_\lambda| \le n∣Jλ​∣≤n, and the printed value of κ\kappaκ is derived through Lemma 5, which is false as printed (see the mission description). The standing assumptions λ>0\lambda > 0λ>0, r≥0r \ge 0r≥0, A≥0A \ge 0A≥0, C≥0C \ge 0C≥0 are those of Sec. 2, p. 7. The horizon is a real T≥1T \ge 1T≥1, because the proof of Theorem 1 applies part 1 on the non-integral sub-horizons T(5/6)uT^{(5/6)^u}T(5/6)u (eq. (10)).

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_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
Source
Bumpensanti, Wang, A Re-solving Heuristic with Uniformly Bounded Loss for Network Revenue Management, arXiv:1802.06192v3, Proposition 1, p. 16 (proof in Appendix B.2, pp. 30–32)
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

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