Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§1, p. 151 — every value function Uₙ is nonincreasing and concave on the reachable states 0 ≤ x ≤ N − n

Proved
AirlineYieldMgmt.BookingLimits.value_concave_nonincreasing

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

concavitydynamic-programmingp2o-batch-rm-cafterp2o-gran-per-chapterp2o-plan-paperp2o-v1yield-management

In Model 1 under its standing assumptions, for every stage 0≤n≤N0 \le n \le N0≤n≤N the value function UnU_nUn​ of recursion (2)–(3) is nonincreasing and concave on the reachable states {0,1,…,N−n}\{0, 1, \dots, N-n\}{0,1,…,N−n}:

Un(x+1)≤Un(x)whenever x+1≤N−n,U_n(x+1) \le U_n(x)\quad\text{whenever } x + 1 \le N - n,Un​(x+1)≤Un​(x)whenever x+1≤N−n, Un(x)−Un(x+1)  ≤  Un(x+1)−Un(x+2)whenever x+2≤N−n.U_n(x) - U_n(x+1) \;\le\; U_n(x+1) - U_n(x+2)\quad\text{whenever } x + 2 \le N - n.Un​(x)−Un​(x+1)≤Un​(x+1)−Un​(x+2)whenever x+2≤N−n.

Equivalently, the opportunity cost Un(x)−Un(x+1)U_n(x) - U_n(x+1)Un​(x)−Un​(x+1) of accepting a booking is non-negative and nondecreasing in x=0,1,…,N−n−1x = 0, 1, \dots, N - n - 1x=0,1,…,N−n−1. 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: qn(0)=0q_n(0) = 0qn​(0)=0, and non-negativity of the null-event probability p0n(x)=1−∑ipin−qn(x)p_{0n}(x) = 1 - \sum_i p_{in} - q_n(x)p0n​(x)=1−∑i​pin​−qn​(x) only for 1≤n≤N1 \le n \le N1≤n≤N and 0≤x≤N−n0 \le x \le N - n0≤x≤N−n. Both claims are restricted to the reachable range, where the paper states them; UnU_nUn​ is defined on all of N\mathbb NN but no claim is made outside the range. Concavity and monotonicity are discrete (differences on N\mathbb NN).

Preamble
import Mathlib
import Definitions.Def_AirlineYieldMgmt_BookingLimits_Model
Formal statement
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
Source
Subramanian, Stidham, Lautenbacher, Airline Yield Management with Overbooking, Cancellations, and No-Shows, Transp. Sci. 33(2), 1999, p. 151, §1, right column, second sentence after Lemma 1 (cf. Lippman and Stidham 1977, Theorem 1)
Read-back

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

The model. Let m∈Nm \in \mathbb{N}m∈N and let MMM be a model with mmm classes. It consists of naturals N,CN, CN,C; real functions pn,ip_{n,i}pn,i​, qn(x)q_n(x)qn​(x), rn,ir_{n,i}rn,i​ (n,x∈Nn, x \in \mathbb{N}n,x∈N, iii a class); a real β\betaβ; and π:R→R\pi:\mathbb{R}\to\mathbb{R}π:R→R. Write pn0(x)=1−∑ipn,i−qn(x)p^0_n(x) = 1 - \sum_i p_{n,i} - q_n(x)pn0​(x)=1−∑i​pn,i​−qn​(x).

The value functions are defined by

U0(x)=∑k=0x(xk)(1−β)kβx−k(−π(k)),U_0(x) = \sum_{k=0}^{x}\binom{x}{k}(1-\beta)^k\beta^{x-k}\bigl(-\pi(k)\bigr),U0​(x)=k=0∑x​(kx​)(1−β)kβx−k(−π(k)), Un+1(x)=∑ipn+1,imax⁡{rn+1,i+Un(x+1), Un(x)}+qn+1(x) Un(x−˙1)+pn+10(x) Un(x).U_{n+1}(x) = \sum_{i} p_{n+1,i}\max\{r_{n+1,i} + U_n(x+1),\,U_n(x)\} + q_{n+1}(x)\,U_n(x \mathbin{\dot-} 1) + p^0_{n+1}(x)\,U_n(x).Un+1​(x)=i∑​pn+1,i​max{rn+1,i​+Un​(x+1),Un​(x)}+qn+1​(x)Un​(x−˙​1)+pn+10​(x)Un​(x).

Here x−˙1x \mathbin{\dot-} 1x−˙​1 is x−1x-1x−1 for x≥1x \ge 1x≥1 and 000 for x=0x = 0x=0.

Hypotheses. Assume MMM satisfies all of the following standing assumptions:

  1. pn,i≥0p_{n,i} \ge 0pn,i​≥0 for all n,in, in,i.
  2. rn,i≥0r_{n,i} \ge 0rn,i​≥0 for all n,in, in,i.
  3. qn(x)≥0q_n(x) \ge 0qn​(x)≥0 for all n,xn, xn,x.
  4. Each qnq_nqn​ is nondecreasing on N\mathbb{N}N.
  5. qn(x+2)−qn(x+1)≤qn(x+1)−qn(x)q_n(x+2) - q_n(x+1) \le q_n(x+1) - q_n(x)qn​(x+2)−qn​(x+1)≤qn​(x+1)−qn​(x) for all n,xn, xn,x.
  6. qn(0)=0q_n(0) = 0qn​(0)=0 for all nnn.
  7. pn0(x)≥0p^0_n(x) \ge 0pn0​(x)≥0 whenever 1≤n≤N1 \le n \le N1≤n≤N and x≤N−nx \le N - nx≤N−n.
  8. 0≤β≤10 \le \beta \le 10≤β≤1.
  9. π(y)≥0\pi(y) \ge 0π(y)≥0 for y≥0y \ge 0y≥0.
  10. π\piπ is convex on [0,∞)[0,\infty)[0,∞).
  11. π\piπ is nondecreasing on [0,∞)[0,\infty)[0,∞).
  12. π(y)=0\pi(y) = 0π(y)=0 for every real y≤Cy \le Cy≤C.

These assumptions are satisfiable, for example with p,q,r,πp, q, r, \pip,q,r,π identically zero and β=0\beta = 0β=0. Finally, let n∈Nn \in \mathbb{N}n∈N with n≤Nn \le Nn≤N.

Conclusion. The statement asserts both of the following:

  1. For every x∈Nx \in \mathbb{N}x∈N with x+1≤N−nx + 1 \le N - nx+1≤N−n:
Un(x+1)≤Un(x).U_n(x+1) \le U_n(x).Un​(x+1)≤Un​(x).
  1. For every x∈Nx \in \mathbb{N}x∈N with x+2≤N−nx + 2 \le N - nx+2≤N−n:
Un(x)−Un(x+1)  ≤  Un(x+1)−Un(x+2).U_n(x) - U_n(x+1) \;\le\; U_n(x+1) - U_n(x+2).Un​(x)−Un​(x+1)≤Un​(x+1)−Un​(x+2).

So UnU_nUn​ is nonincreasing, with nondecreasing decrements, but only on the states 0,1,…,N−n0,1,\dots,N-n0,1,…,N−n. Nothing is asserted about UnU_nUn​ at states above N−nN-nN−n, or about stages n>Nn > Nn>N.

Degenerate cases. Since n≤Nn \le Nn≤N, the difference N−nN - nN−n is an ordinary nonnegative integer.

  • n=Nn = Nn=N: N−n=0N - n = 0N−n=0, so both conclusions are vacuous.
  • n=N−1n = N-1n=N−1 (when N≥1N \ge 1N≥1): part 1 says only Un(1)≤Un(0)U_n(1) \le U_n(0)Un​(1)≤Un​(0), and part 2 is vacuous.
  • N=0N = 0N=0: the only permitted stage is n=0n = 0n=0, and the whole statement is vacuous.
  • N−n=1N - n = 1N−n=1: in general, part 2 needs N−n≥2N - n \ge 2N−n≥2 to say anything.
  • m=0m = 0m=0: the class sums are empty, pn0(x)=1−qn(x)p^0_n(x) = 1 - q_n(x)pn0​(x)=1−qn​(x), and the recursion reduces to Un+1(x)=qn+1(x) Un(x−˙1)+(1−qn+1(x)) Un(x)U_{n+1}(x) = q_{n+1}(x)\,U_n(x \mathbin{\dot-} 1) + (1 - q_{n+1}(x))\,U_n(x)Un+1​(x)=qn+1​(x)Un​(x−˙​1)+(1−qn+1​(x))Un​(x).
  • x=0x = 0x=0 in the recursion: the middle term is qn+1(0) Un(0)q_{n+1}(0)\,U_n(0)qn+1​(0)Un​(0), which is 000 by assumption 6.
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