Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 5, p. 27 — static probabilistic allocation loses O(T)O(\sqrt T)O(T​) against the DLP, uniformly in CCC

Proved
ResolvingNRM.IRT.spa_dlp_gap_sqrt

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

linear-programmingnetwork-revenue-managementp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1poisson

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. The static probabilistic allocation (SPA) heuristic (Algorithm 1) solves the DLP once at b=C/Tb = C/Tb=C/T, obtaining an optimal x∗x^*x∗, and accepts each class-jjj arrival with probability xj∗/λjx^*_j/\lambda_jxj∗​/λj​ whenever capacity allows. Let vSPA(T,C)v^{\mathrm{SPA}}(T, C)vSPA(T,C) be its expected revenue.

There is a constant MMM, depending only on (λ,r,A)(\lambda, r, A)(λ,r,A), such that for every choice of optimal DLP solutions, every horizon T>0T > 0T>0 and every capacity C≥0C \ge 0C≥0,

vDLP(T,C)−vSPA(T,C)≤MT.v^{\mathrm{DLP}}(T, C) - v^{\mathrm{SPA}}(T, C) \le M\sqrt{T}.vDLP(T,C)−vSPA(T,C)≤MT​.

The bound holds uniformly in the capacity, with no scaling assumption linking CCC and TTT; 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 IRT0\mathrm{IRT}^0IRT0 of the IRT family (one epoch, plain probabilities from sel(C/T)\mathrm{sel}(C/T)sel(C/T)). MMM is chosen before the selector, TTT and CCC: the paper's constant ∑lrmax⁡l∑jalj2λj\sum_l r^l_{\max}\sqrt{\sum_j a_{lj}^2\lambda_j}∑l​rmaxl​∑j​alj2​λj​​ does not depend on which optimal solution the LP returns. The horizon TTT is a positive real, because the proof of Theorem 1 applies the result on the sub-horizon τK=T(5/6)K\tau_K = T^{(5/6)^K}τK​=T(5/6)K (eq. (11)). 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, left implicit on the page.

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 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
Source
Bumpensanti, Wang, A Re-solving Heuristic with Uniformly Bounded Loss for Network Revenue Management, arXiv:1802.06192v3, Proposition 5, p. 27 (Appendix A.2); Algorithm 1, p. 10
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