Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§1, p. 151 — the terminal value U₀(x) = E[−π(Y(x))] is concave and nonincreasing

Proved
AirlineYieldMgmt.BookingLimits.terminal_value_concave

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

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

In Model 1, let 0≤β≤10 \le \beta \le 10≤β≤1 and let the overbooking penalty π(y)\pi(y)π(y) be convex and nondecreasing in y≥0y \ge 0y≥0. Then the terminal value

U0(x)  =  E[−π(Y(x))],Y(x)∼Bin(x,1−β),U_0(x) \;=\; \mathrm{E}\big[-\pi(Y(x))\big],\qquad Y(x) \sim \mathrm{Bin}(x, 1-\beta),U0​(x)=E[−π(Y(x))],Y(x)∼Bin(x,1−β),

is nonincreasing and concave in x∈{0,1,2,… }x \in \{0,1,2,\dots\}x∈{0,1,2,…}:

U0(x+1)≤U0(x)andU0(x+2)−U0(x+1)  ≤  U0(x+1)−U0(x)for all x≥0.U_0(x+1) \le U_0(x) \quad\text{and}\quad U_0(x+2) - U_0(x+1) \;\le\; U_0(x+1) - U_0(x)\qquad\text{for all } x \ge 0.U0​(x+1)≤U0​(x)andU0​(x+2)−U0​(x+1)≤U0​(x+1)−U0​(x)for all x≥0.

This is the base case of the induction showing that every UnU_nUn​ is concave and nonincreasing.

Formalization Note. Only the two hypotheses the sentence on the page invokes are assumed (π\piπ convex and nondecreasing on y≥0y \ge 0y≥0), plus 0≤β≤10 \le \beta \le 10≤β≤1; the other standing assumptions on π\piπ (non-negativity, π(y)=0\pi(y) = 0π(y)=0 for y≤Cy \le Cy≤C) are not needed and are dropped, which makes the statement more general. The paper's Lemma 1 requires 0<γ<10 < \gamma < 10<γ<1; here γ=1−β\gamma = 1 - \betaγ=1−β may also be 000 or 111 (the boundary cases U0≡−π(0)U_0 \equiv -\pi(0)U0​≡−π(0) and U0(x)=−π(x)U_0(x) = -\pi(x)U0​(x)=−π(x)). The conclusion is stated on all of N\mathbb NN, which contains the range 0≤x≤N0 \le x \le N0≤x≤N of Eq. (3).

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

/-- §1, p. 151, first sentence after Lemma 1: because `π` is convex and nondecreasing, the terminal
value `U_0(x) = E[-π(Y(x))]`, `Y(x) ∼ Bin(x, 1 - β)`, is nonincreasing and (discretely) concave
in `x`. -/
theorem terminal_value_concave {m : ℕ} (M : Model m)
    (hβ0 : 0 ≤ M.β) (hβ1 : M.β ≤ 1)
    (hπ_convex : ConvexOn ℝ (Set.Ici 0) M.π) (hπ_mono : MonotoneOn M.π (Set.Ici 0)) :
    Antitone (M.U 0) ∧
      ∀ x : ℕ, M.U 0 (x + 2) - M.U 0 (x + 1) ≤ M.U 0 (x + 1) - M.U 0 x := 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, first sentence after Lemma 1 (with Eq. (3), p. 150, and Eq. (6), p. 151)
Read-back

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

Hypotheses. Let m∈Nm \in \mathbb{N}m∈N and let MMM be any model with mmm classes. The model consists of naturals N,CN, CN,C; real functions pn,i,qn(x),rn,ip_{n,i}, q_n(x), r_{n,i}pn,i​,qn​(x),rn,i​; a real β\betaβ; and π:R→R\pi : \mathbb{R}\to\mathbb{R}π:R→R. Assume:

  • 0≤β≤10 \le \beta \le 10≤β≤1;
  • π\piπ is convex on [0,∞)[0,\infty)[0,∞);
  • π\piπ is nondecreasing on [0,∞)[0,\infty)[0,∞).

Nothing else is assumed. In particular, there is no nonnegativity of π\piπ, no condition π=0\pi = 0π=0 below CCC, and no conditions on N,C,p,q,rN, C, p, q, rN,C,p,q,r. None of those enter the conclusion anyway.

The function studied. The terminal value function is, for x∈Nx \in \mathbb{N}x∈N,

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)).

Conclusion. The statement asserts both of the following:

  1. U0U_0U0​ is nonincreasing on all of N\mathbb{N}N:   x≤x′⇒U0(x′)≤U0(x)\;x \le x' \Rightarrow U_0(x') \le U_0(x)x≤x′⇒U0​(x′)≤U0​(x).
  2. For every x∈Nx \in \mathbb{N}x∈N,
U0(x+2)−U0(x+1)  ≤  U0(x+1)−U0(x).U_0(x+2) - U_0(x+1) \;\le\; U_0(x+1) - U_0(x).U0​(x+2)−U0​(x+1)≤U0​(x+1)−U0​(x).

That is, the forward differences are nonincreasing (discrete concavity).

Degenerate cases. The endpoints β=0\beta = 0β=0 and β=1\beta = 1β=1 are permitted, and 00=10^0 = 100=1 is used:

  • β=0\beta = 0β=0: only the k=xk = xk=x term survives, so U0(x)=−π(x)U_0(x) = -\pi(x)U0​(x)=−π(x).
  • β=1\beta = 1β=1: only the k=0k = 0k=0 term survives, so U0(x)=−π(0)U_0(x) = -\pi(0)U0​(x)=−π(0) for every xxx. The function is constant, and both claims hold with equality.

At x=0x = 0x=0, U0(0)=−π(0)U_0(0) = -\pi(0)U0​(0)=−π(0) for every β\betaβ. Only the values of π\piπ at nonnegative integers matter. The claims hold for every mmm, including m=0m=0m=0, and every N,CN, CN,C.

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