Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1, p. 765 — under A1, A2 (windowed) and A3, θ^n_i → θ*_i a.s., p_i(θ*) = θ*_i, and E|θ^n_i − θ*_i|² ≤ Cγ_n^{β/2^{i−1}}

Disproved
AdaptiveProtection.Convergence.theorem1_convergence

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

almost-sure-convergencep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1protection-levelsrevenue-managementstochastic-approximation

Consider a single flight leg with k+1k + 1k+1 fare classes, fares f1>f2>⋯>fk+1>0f_1 > f_2 > \cdots > f_{k+1} > 0f1​>f2​>⋯>fk+1​>0 and discount ratios ri+1=fi+1/f1r_{i+1} = f_{i+1}/f_1ri+1​=fi+1​/f1​. The class demands X1,…,Xk+1X_1, \dots, X_{k+1}X1​,…,Xk+1​ of a flight are independent, nonnegative, and have continuous distributions; successive flights are independent and identically distributed. Let θ∗\theta^*θ∗ satisfy the optimality condition (3), P(Ai(θ∗,X))=ri+1P(A_i(\theta^*, X)) = r_{i+1}P(Ai​(θ∗,X))=ri+1​ for i=1,…,ki = 1, \dots, ki=1,…,k, where AiA_iAi​ is the fill event (2). Let θn\theta^nθn be generated by the recursion (4),

θn+1=θn−γnH(θn,Xn),Hi(θ,X)=ri+1−1(Ai(θ,X)),\theta^{n+1} = \theta^n - \gamma_n H(\theta^n, X^n), \qquad H_i(\theta, X) = r_{i+1} - \mathbf 1(A_i(\theta, X)),θn+1=θn−γn​H(θn,Xn),Hi​(θ,X)=ri+1​−1(Ai​(θ,X)),

from an arbitrary initial vector θ1\theta^1θ1, with step sizes γn=A/(n+B)\gamma_n = A/(n + B)γn​=A/(n+B), A>0A > 0A>0, B≥0B \ge 0B≥0. Assume

  1. A1 each XiX_iXi​ has bounded support: P(Xi<C)=1P(X_i < C) = 1P(Xi​<C)=1 for some constant CCC;
  2. A2 (windowed) for every R>0R > 0R>0 there is δR>0\delta_R > 0δR​>0 such that, for i=1,…,ki = 1, \dots, ki=1,…,k and every θi\theta_iθi​ with ∣θi−θi∗∣≤R|\theta_i - \theta^*_i| \le R∣θi​−θi∗​∣≤R,
(θi−θi∗) hi(θi,θi−1∗,…,θ1∗)≥δR∣θi−θi∗∣2,(\theta_i - \theta^*_i)\, h_i(\theta_i, \theta^*_{i-1}, \dots, \theta^*_1) \ge \delta_R |\theta_i - \theta^*_i|^2,(θi​−θi∗​)hi​(θi​,θi−1∗​,…,θ1∗​)≥δR​∣θi​−θi∗​∣2,

where hi(θ)=ri+1−P(Ai(θ,X))h_i(\theta) = r_{i+1} - P(A_i(\theta, X))hi​(θ)=ri+1​−P(Ai​(θ,X)); 3. A3 the distributions of the partial sums are Lipschitz: for some LLL, all i=1,…,ki = 1, \dots, ki=1,…,k and all x,yx, yx,y, ∣P(X1+⋯+Xi<x)−P(X1+⋯+Xi<y)∣≤L∣x−y∣|P(X_1 + \cdots + X_i < x) - P(X_1 + \cdots + X_i < y)| \le L|x - y|∣P(X1​+⋯+Xi​<x)−P(X1​+⋯+Xi​<y)∣≤L∣x−y∣.

Then for i=1,…,ki = 1, \dots, ki=1,…,k,

θin→θi∗ (a.s.)(8)\theta^n_i \to \theta^*_i \ \text{(a.s.)} \tag{8}θin​→θi∗​ (a.s.)(8) pi(θ∗)=θi∗,(9)p_i(\theta^*) = \theta^*_i, \tag{9}pi​(θ∗)=θi∗​,(9)

where pi(θ)=max⁡{θj:1≤j≤i}p_i(\theta) = \max\{\theta_j : 1 \le j \le i\}pi​(θ)=max{θj​:1≤j≤i}; and there are β>0\beta > 0β>0 and CCC such that for i=1,…,ki = 1, \dots, ki=1,…,k and all n≥1n \ge 1n≥1, ∣θin−θi∗∣2|\theta^n_i - \theta^*_i|^2∣θin​−θi∗​∣2 is integrable and

E∣θin−θi∗∣2≤Cγnβ/2i−1.(10)E|\theta^n_i - \theta^*_i|^2 \le C\gamma_n^{\beta/2^{i-1}}. \tag{10}E∣θin​−θi∗​∣2≤Cγnβ/2i−1​.(10)

The theorem says that updating the protection levels from fill events alone, with no demand forecast and no optimization, recovers the optimal nested protection levels, which are moreover ordered.

Formalization Note As printed, A2 asks for one δ\deltaδ valid for all θi\theta_iθi​; since ∣hi∣≤1|h_i| \le 1∣hi​∣≤1 this cannot hold for ∣θi−θi∗∣>1/δ|\theta_i - \theta^*_i| > 1/\delta∣θi​−θi∗​∣>1/δ, so no instance satisfies it and the printed theorem is vacuous. A2 is pinned to bounded windows with a δ\deltaδ per window, which is what the proof uses (the iterates stay bounded by Lemma 3) and what the paper's sufficient condition (a density bounded below near θ∗\theta^*θ∗) gives. Continuity of the demand laws is stated as "every singleton is null". Lean's iterate … n is the paper's θn+1\theta^{n+1}θn+1, so (10) pairs it with stepSize A B (n + 1), i.e. γn+1\gamma_{n+1}γn+1​. Integrability is part of the conclusion, so the bound cannot hold through Lean's convention that a non-integrable function has integral 000.

Preamble
import Mathlib
import Definitions.Def_NestedSeatAlloc_ProbCond_Model
import Definitions.Def_AdaptiveProtection_Convergence_Setting

open MeasureTheory Filter Topology
Formal statement
namespace AdaptiveProtection.Convergence

/-- Theorem 1 (van Ryzin–McGill 2000, p. 765), with Assumption A2 pinned to bounded windows
(as printed, A2 is unsatisfiable). Lean's `iterate … n` is the paper's `θ^{n+1}`, so the rate (10)
pairs it with `stepSize A B (n + 1) = γ_{n+1}`. -/
theorem theorem1_convergence
    (k : ℕ) (f : ℕ → ℝ) (hf : ∀ i, 1 ≤ i → i ≤ k → f (i + 1) < f i) (hfpos : 0 < f (k + 1))
    (ν : ℕ → Measure ℝ) [∀ i, IsProbabilityMeasure (ν i)]
    (hnonneg : ∀ i, 1 ≤ i → i ≤ k + 1 → ∀ᵐ t ∂(ν i), 0 ≤ t)
    (hcont : ∀ i, 1 ≤ i → i ≤ k + 1 → NullSingletonClass (ν i))
    (A B : ℝ) (hA : 0 < A) (hB : 0 ≤ B)
    (θ₁ θstar : ℕ → ℝ)
    (hopt : ∀ i, 1 ≤ i → i ≤ k → (flightLaw ν).real (fillEvent θstar i) = ratio f (i + 1))
    (hA1 : ∃ Cb : ℝ, ∀ i, 1 ≤ i → i ≤ k + 1 → ∀ᵐ t ∂(ν i), t < Cb)
    (hA2 : ∀ R > 0, ∃ δ > 0, ∀ i, 1 ≤ i → i ≤ k → ∀ t : ℝ, |t - θstar i| ≤ R →
      δ * (t - θstar i) ^ 2 ≤ (t - θstar i) * meanAdj f ν (Function.update θstar i t) i)
    (hA3 : ∃ L : ℝ, ∀ i, 1 ≤ i → i ≤ k → ∀ x y : ℝ,
      |(flightLaw ν).real {z | partialSum z i < x} - (flightLaw ν).real {z | partialSum z i < y}|
        ≤ L * |x - y|) :
    (∀ i, 1 ≤ i → i ≤ k → ∀ᵐ ω ∂(pathLaw ν),
        Tendsto (fun n => iterate f k (stepSize A B) θ₁ ω n i) atTop (𝓝 (θstar i))) ∧
    (∀ i, 1 ≤ i → i ≤ k → interim θstar i = θstar i) ∧
    (∃ β > 0, ∃ C : ℝ, ∀ i, 1 ≤ i → i ≤ k → ∀ n : ℕ,
        Integrable (fun ω => (iterate f k (stepSize A B) θ₁ ω n i - θstar i) ^ 2) (pathLaw ν) ∧
        ∫ ω, (iterate f k (stepSize A B) θ₁ ω n i - θstar i) ^ 2 ∂(pathLaw ν)
          ≤ C * stepSize A B (n + 1) ^ (β / 2 ^ (i - 1))) := by sorry

end AdaptiveProtection.Convergence
Source
van Ryzin & McGill, Management Science 46(6), 2000, p. 765, Theorem 1; proof pp. 765–766
Human review
  • Endorsed by Shuze Chen · Oct 7, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 7, 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