Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

(27), p. 132 — δER₁[s; p; X] = [f₁Pr[X₁ > s], f₁Pr[X₁ ≥ s]], and ER₁ is CLBI for integer demand

Proved
NestedSeatAlloc.IntPolicy.eq27_er1_clbi

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

airline-revenue-managementconcavityexpected-revenueone-sided-derivativep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1

Work in the seat model: independent nonnegative demands X1,X2,…X_1, X_2, \dotsX1​,X2​,… on a probability space (Ω,F,P)(\Omega, \mathcal F, P)(Ω,F,P) and strictly decreasing fares f1>f2>⋯f_1 > f_2 > \cdotsf1​>f2​>⋯. Assume the demands are integer valued and f1≥0f_1 \ge 0f1​≥0. Let ER1[s;p;X]=f1 E[min⁡(s,X1)]ER_1[s; p; X] = f_1\,E[\min(s, X_1)]ER1​[s;p;X]=f1​E[min(s,X1​)] be the expected revenue of the highest fare class with sss seats available (it does not depend on the policy ppp). Then:

  1. ER1[ ⋅ ;p;X]ER_1[\,\cdot\,; p; X]ER1​[⋅;p;X] is CLBI: concave on s≥0s \ge 0s≥0 and linear on every interval [m,m+1][m, m+1][m,m+1], m=0,1,2,…m = 0, 1, 2, \dotsm=0,1,2,…;
  2. for every s≥0s \ge 0s≥0 its right derivative is
δ+ER1[s;p;X]=f1Pr⁡[X1>s];\delta_+ ER_1[s; p; X] = f_1 \Pr[X_1 > s];δ+​ER1​[s;p;X]=f1​Pr[X1​>s];
  1. for every s>0s > 0s>0 its left derivative is
δ−ER1[s;p;X]=f1Pr⁡[X1≥s].\delta_- ER_1[s; p; X] = f_1 \Pr[X_1 \ge s].δ−​ER1​[s;p;X]=f1​Pr[X1​≥s].

Items 2 and 3 are equation (27), δER1[s;p;X]=[f1Pr⁡[X1>s],f1Pr⁡[X1≥s]]\delta ER_1[s; p; X] = [f_1 \Pr[X_1 > s], f_1 \Pr[X_1 \ge s]]δER1​[s;p;X]=[f1​Pr[X1​>s],f1​Pr[X1​≥s]]. This is the base case of the induction that proves Theorem 2.

Formalization Note The hypothesis f1≥0f_1 \ge 0f1​≥0 is added: if f1<0f_1 < 0f1​<0 and X1X_1X1​ is not almost surely 000, then f1E[min⁡(s,X1)]f_1 E[\min(s, X_1)]f1​E[min(s,X1​)] is convex and not concave, so the CLBI claim fails. The paper's fares are average revenues per booking, hence positive. At s=0s = 0s=0 the left derivative is the convention +∞+\infty+∞ and is not stated.

Preamble
import Mathlib
import Definitions.Def_NestedSeatAlloc_IntPolicy_Model
import Definitions.Def_NestedSeatAlloc_IntPolicy_CLBI
Formal statement
namespace NestedSeatAlloc.IntPolicy

open MeasureTheory ProbabilityTheory

/-- (27), p. 132, and "ER₁ is CLBI": with integer-valued demand and a nonnegative top fare, `ER_1[s; p; X]`
is CLBI on `s ≥ 0`, its right derivative at `s ≥ 0` is `f₁ Pr[X₁ > s]`, and its left derivative at `s > 0` is
`f₁ Pr[X₁ ≥ s]`. -/
theorem eq27_er1_clbi {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) (X : ℕ → Ω → ℝ) (f p : ℕ → ℝ)
    (hM : IsSeatModel P X f) (hint : ∀ k ω, ∃ n : ℕ, X k ω = n) (hf1 : 0 ≤ f 1) :
    IsCLBI (expRevenue P X f p 1) ∧
      (∀ s, 0 ≤ s →
        HasDerivWithinAt (expRevenue P X f p 1) (f 1 * P.real {ω | s < X 1 ω}) (Set.Ici s) s) ∧
      (∀ s, 0 < s →
        HasDerivWithinAt (expRevenue P X f p 1) (f 1 * P.real {ω | s ≤ X 1 ω}) (Set.Iic s) s) := by sorry

end NestedSeatAlloc.IntPolicy
Source
Brumelle & McGill (1993), Operations Research 41(1), (27) and the sentence following it, proof of Theorem 2, p. 132
Human review
  • Endorsed by Shuze Chen · Oct 5, 2026

    Confirmed by the moderator at approval.

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