Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§1, Eq. (7), p. 151 — accepting a fare-class-i request at stage n is optimal iff the state is below the booking limit b_in

Proved
AirlineYieldMgmt.BookingLimits.booking_limit_policy_optimal

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

booking-limitsdynamic-programmingp2o-batch-rm-cafterp2o-gran-per-chapterp2o-plan-paperp2o-v1revenue-managementyield-management

In Model 1 under its standing assumptions, fix a stage 1≤n≤N1 \le n \le N1≤n≤N, a fare class iii and a reachable state 0≤x≤N−n0 \le x \le N - n0≤x≤N−n. Let

bin  =  min⁡{x:Un−1(x)−Un−1(x+1)>rin}(bin=∞ if there is no such x)b_{in} \;=\; \min\{x : U_{n-1}(x) - U_{n-1}(x+1) > r_{in}\}\qquad(b_{in} = \infty \text{ if there is no such } x)bin​=min{x:Un−1​(x)−Un−1​(x+1)>rin​}(bin​=∞ if there is no such x)

be the booking limit of Eq. (7). Then accepting a class-iii request attains the maximum in the recursion (2), i.e.

rin+Un−1(x+1)  ≥  Un−1(x),r_{in} + U_{n-1}(x+1) \;\ge\; U_{n-1}(x),rin​+Un−1​(x+1)≥Un−1​(x),

if and only if x<binx < b_{in}x<bin​. So an optimal policy accepts a fare-class-iii request in state xxx at stage nnn exactly when 0≤x<bin0 \le x < b_{in}0≤x<bin​: optimal control is by booking limits that depend on the stage and the fare class. This is the paper's headline structural result.

Formalization Note. "An optimal policy accepts" is read as "the accept branch attains the maximum max⁡{rin+Un−1(x+1),Un−1(x)}\max\{r_{in} + U_{n-1}(x+1), U_{n-1}(x)\}max{rin​+Un−1​(x+1),Un−1​(x)} in (2)"; UnU_nUn​ is the function defined by the recursion, and no separate dynamic-programming optimality principle is stated. Ties are accepted (≥\ge≥), matching the strict inequality in (7). The minimum in (7) ranges over the reachable states 0≤x≤N−n0 \le x \le N - n0≤x≤N−n and is computed in WithTop ℕ, with ⊤ = ∞\infty∞; binb_{in}bin​ is defined independently of the acceptance rule, so the content of the theorem is that the set of states where rejection is strictly better is an upper segment of the range. The standing assumptions include qn(0)=0q_n(0) = 0qn​(0)=0 and non-negativity of p0n(x)p_{0n}(x)p0n​(x) on the reachable states only (see Model).

Preamble
import Mathlib
import Definitions.Def_AirlineYieldMgmt_BookingLimits_Model
Formal statement
namespace AirlineYieldMgmt.BookingLimits

/-- §1, Eq. (7) and the display after it, p. 151: under the standing assumptions of Model 1, at
every stage `1 ≤ n ≤ N`, for every fare class `i` and every reachable state `0 ≤ x ≤ N - n`,
accepting a class-`i` request attains the maximum in the recursion (2), i.e.
`r_{in} + U_{n-1}(x+1) ≥ U_{n-1}(x)`, if and only if `x < b_{in}`, where `b_{in}` is the booking
limit of Eq. (7). -/
theorem booking_limit_policy_optimal {m : ℕ} (M : Model m) (hM : M.Standing)
    (n : ℕ) (hn1 : 1 ≤ n) (hnN : n ≤ M.N) (i : Fin m) (x : ℕ) (hx : x ≤ M.N - n) :
    M.U (n - 1) x ≤ M.r n i + M.U (n - 1) (x + 1) ↔
      (x : WithTop ℕ) < M.bookingLimit n i := by sorry

end AirlineYieldMgmt.BookingLimits
Source
Subramanian, Stidham, Lautenbacher, Airline Yield Management with Overbooking, Cancellations, and No-Shows, Transp. Sci. 33(2), 1999, p. 151, §1, Eq. (7) and the display after it
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Fix a natural number mmm (the number of indices iii ranges over) and a structure MMM of type Model m. This declaration does not show how Model or its components are defined; they come from the imported file Def_AirlineYieldMgmt_BookingLimits_Model. From how the statement uses MMM, it has at least these components:

  • a natural number N=M.NN = M.NN=M.N;
  • a family of values Uk(y)U_{k}(y)Uk​(y) for k,y∈Nk, y \in \mathbb{N}k,y∈N (M.U k y), taking values in some ordered type that has addition;
  • values rn,ir_{n,i}rn,i​ (M.r n i) for n∈Nn \in \mathbb{N}n∈N and i∈{0,…,m−1}i \in \{0, \dots, m-1\}i∈{0,…,m−1}, in the same type as UUU;
  • values bn,ib_{n,i}bn,i​ (M.bookingLimit n i), each either a natural number or the extra top element ∞\infty∞ (the type N∪{∞}\mathbb{N} \cup \{\infty\}N∪{∞}).

The theorem also assumes a hypothesis Standing(M)\mathrm{Standing}(M)Standing(M), a property of MMM defined in the imported file, which cannot be expanded from this code. The doc comment attached to the theorem is not part of the formal claim and is not paraphrased here.

Statement. Assume Standing(M)\mathrm{Standing}(M)Standing(M). Then for every n∈Nn \in \mathbb{N}n∈N with 1≤n≤N1 \le n \le N1≤n≤N, every index i∈{0,…,m−1}i \in \{0, \dots, m-1\}i∈{0,…,m−1}, and every x∈Nx \in \mathbb{N}x∈N with x≤N−nx \le N - nx≤N−n:

Un−1(x)  ≤  rn,i+Un−1(x+1)⟺x<bn,i,U_{n-1}(x) \;\le\; r_{n,i} + U_{n-1}(x+1) \quad\Longleftrightarrow\quad x < b_{n,i},Un−1​(x)≤rn,i​+Un−1​(x+1)⟺x<bn,i​,

where on the right xxx is treated as an element of N∪{∞}\mathbb{N} \cup \{\infty\}N∪{∞}. The inequality on the left is non-strict (≤\le≤), the one on the right is strict (<<<), and the connective is a two-way "if and only if".

Degenerate cases.

  • m=0m = 0m=0: there is no index iii, so the statement holds vacuously.
  • N=0N = 0N=0: no nnn satisfies 1≤n≤01 \le n \le 01≤n≤0, so the statement is again vacuous. More generally, the claim covers only stages n=1,…,Nn = 1, \dots, Nn=1,…,N.
  • Subtraction in ℕ: because n≥1n \ge 1n≥1, the index n−1n - 1n−1 never truncates. Because n≤Nn \le Nn≤N, the bound N−nN - nN−n is the ordinary difference, so xxx ranges exactly over 0,1,…,N−n0, 1, \dots, N - n0,1,…,N−n. At n=Nn = Nn=N the only allowed value is x=0x = 0x=0. The value x+1x + 1x+1 is at most N−n+1N - n + 1N−n+1.
  • Infinite booking limit: when bn,i=∞b_{n,i} = \inftybn,i​=∞, the right-hand side x<∞x < \inftyx<∞ always holds. In that case the theorem asserts Un−1(x)≤rn,i+Un−1(x+1)U_{n-1}(x) \le r_{n,i} + U_{n-1}(x+1)Un−1​(x)≤rn,i​+Un−1​(x+1) outright for all allowed xxx.
  • Booking limit 000: when bn,i=0b_{n,i} = 0bn,i​=0, the right-hand side is always false. The theorem then asserts Un−1(x)>rn,i+Un−1(x+1)U_{n-1}(x) > r_{n,i} + U_{n-1}(x+1)Un−1​(x)>rn,i​+Un−1​(x+1) for all allowed xxx, assuming the value type is linearly ordered. That cannot be confirmed from this code.
  • Unsatisfiable assumption: if Standing(M)\mathrm{Standing}(M)Standing(M) cannot be satisfied by any model, the theorem is vacuous. This code cannot rule that out.
  • Default values: no division, integral, supremum or other total-function default appears in the statement itself. Any such defaults would sit inside the imported definitions of UUU, rrr or bbb, which are not visible here.
Human review
  • Endorsed by Shuze Chen · Oct 21, 2026

    Confirmed by the moderator at approval.

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