§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
ProvedAirlineYieldMgmt.BookingLimits.booking_limit_policy_optimalIn Model 1 under its standing assumptions, fix a stage , a fare class and a reachable state . Let
be the booking limit of Eq. (7). Then accepting a class- request attains the maximum in the recursion (2), i.e.
if and only if . So an optimal policy accepts a fare-class- request in state at stage exactly when : 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 in (2)"; is the function defined by the recursion, and no separate dynamic-programming optimality principle is stated. Ties are accepted (), matching the strict inequality in (7). The minimum in (7) ranges over the reachable states and is computed in WithTop ℕ, with ⊤ = ; 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 and non-negativity of on the reachable states only (see Model).
import Mathlib import Definitions.Def_AirlineYieldMgmt_BookingLimits_Model
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
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Fix a natural number (the number of indices ranges over) and a structure 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 , it has at least these components:
- a natural number ;
- a family of values for (
M.U k y), taking values in some ordered type that has addition; - values (
M.r n i) for and , in the same type as ; - values (
M.bookingLimit n i), each either a natural number or the extra top element (the type ).
The theorem also assumes a hypothesis , a property of 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 . Then for every with , every index , and every with :
where on the right is treated as an element of . The inequality on the left is non-strict (), the one on the right is strict (), and the connective is a two-way "if and only if".
Degenerate cases.
- : there is no index , so the statement holds vacuously.
- : no satisfies , so the statement is again vacuous. More generally, the claim covers only stages .
- Subtraction in ℕ: because , the index never truncates. Because , the bound is the ordinary difference, so ranges exactly over . At the only allowed value is . The value is at most .
- Infinite booking limit: when , the right-hand side always holds. In that case the theorem asserts outright for all allowed .
- Booking limit : when , the right-hand side is always false. The theorem then asserts for all allowed , assuming the value type is linearly ordered. That cannot be confirmed from this code.
- Unsatisfiable assumption: if 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 , or , which are not visible here.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.