§1, p. 151 — every value function Uₙ is nonincreasing and concave on the reachable states 0 ≤ x ≤ N − n
ProvedAirlineYieldMgmt.BookingLimits.value_concave_nonincreasingIn Model 1 under its standing assumptions, for every stage the value function of recursion (2)–(3) is nonincreasing and concave on the reachable states :
Equivalently, the opportunity cost of accepting a booking is non-negative and nondecreasing in . This is the structural property from which the optimality of booking limits follows.
Formalization Note. The standing assumptions are those of Model.Standing, including the two conventions the page leaves implicit: , and non-negativity of the null-event probability only for and . Both claims are restricted to the reachable range, where the paper states them; is defined on all of but no claim is made outside the range. Concavity and monotonicity are discrete (differences on ).
import Mathlib import Definitions.Def_AirlineYieldMgmt_BookingLimits_Model
namespace AirlineYieldMgmt.BookingLimits
/-- §1, p. 151 (cf. Lippman–Stidham 1977, Theorem 1): under the standing assumptions of Model 1,
for every stage `0 ≤ n ≤ N`, `U_n(·)` is nonincreasing and concave on the reachable states
`0 ≤ x ≤ N - n`, so that `U_n(x) - U_n(x+1)` is nondecreasing in `x = 0, 1, …, N - n - 1`. -/
theorem value_concave_nonincreasing {m : ℕ} (M : Model m) (hM : M.Standing)
(n : ℕ) (hn : n ≤ M.N) :
(∀ x : ℕ, x + 1 ≤ M.N - n → M.U n (x + 1) ≤ M.U n x) ∧
(∀ x : ℕ, x + 2 ≤ M.N - n →
M.U n x - M.U n (x + 1) ≤ M.U n (x + 1) - M.U n (x + 2)) := by sorry
end AirlineYieldMgmt.BookingLimits
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
The model. Let and let be a model with classes. It consists of naturals ; real functions , , (, a class); a real ; and . Write .
The value functions are defined by
Here is for and for .
Hypotheses. Assume satisfies all of the following standing assumptions:
- for all .
- for all .
- for all .
- Each is nondecreasing on .
- for all .
- for all .
- whenever and .
- .
- for .
- is convex on .
- is nondecreasing on .
- for every real .
These assumptions are satisfiable, for example with identically zero and . Finally, let with .
Conclusion. The statement asserts both of the following:
- For every with :
- For every with :
So is nonincreasing, with nondecreasing decrements, but only on the states . Nothing is asserted about at states above , or about stages .
Degenerate cases. Since , the difference is an ordinary nonnegative integer.
- : , so both conclusions are vacuous.
- (when ): part 1 says only , and part 2 is vacuous.
- : the only permitted stage is , and the whole statement is vacuous.
- : in general, part 2 needs to say anything.
- : the class sums are empty, , and the recursion reduces to .
- in the recursion: the middle term is , which is by assumption 6.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.