Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Coupling bound (14): J^H_θk(θx) ≥ Σ E(R − μ*A^j)⁺ + Σ P(R > μ*A^j)μ*A^j − C Σ_i E(Nⁱ − θxⁱ)⁺

Proved
BidPriceControl.Asymptotic.coupling_bound

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

p2o-batch-rm-cafterp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilityrevenue-management

Assume the standing assumptions of §1 and Rtj≤CR_t^j \le CRtj​≤C almost surely. Let μ∗\mu^*μ∗ be an optimal solution of (9) for (x,k)(x, k)(x,k) and let θ≥1\theta \ge 1θ≥1 be an integer. The fixed-bid-price heuristic with bid prices μ∗\mu^*μ∗ in the θ\thetaθ-scaled problem earns

JθkH(θx)≥∑t=1θk∑j=1nE (Rtj(θ)−μ∗Aj)++∑t=1θk∑j=1nP(Rtj(θ)>μ∗Aj) μ∗Aj−C∑i=1mE (Ni−θxi)+,J^H_{\theta k}(\theta x) \ge \sum_{t=1}^{\theta k}\sum_{j=1}^n \mathbb{E}\,(R_t^j(\theta) - \mu^* A^j)^+ + \sum_{t=1}^{\theta k}\sum_{j=1}^n P(R_t^j(\theta) > \mu^* A^j)\,\mu^* A^j - C\sum_{i=1}^m \mathbb{E}\,(N^i - \theta x^i)^+,JθkH​(θx)≥t=1∑θk​j=1∑n​E(Rtj​(θ)−μ∗Aj)++t=1∑θk​j=1∑n​P(Rtj​(θ)>μ∗Aj)μ∗Aj−Ci=1∑m​E(Ni−θxi)+,

where Ni=∑t=1θk∑j=1n1{Rtj(θ)>μ∗Aj} aijN^i = \sum_{t=1}^{\theta k}\sum_{j=1}^n \mathbf{1}\{R_t^j(\theta) > \mu^* A^j\}\,a_{ij}Ni=∑t=1θk​∑j=1n​1{Rtj​(θ)>μ∗Aj}aij​. The first two terms are the revenue of an alternate system that accepts every request above its bid price and ignores capacity. The last term charges CCC for each seat that system sells beyond a leg's capacity.

Formalization Note. As on the page, the bid prices are an optimal solution μ∗\mu^*μ∗ of (9) (a predicate, IsRelaxedMinimizer, so every minimizer is covered). The page calls NiN^iNi "the number of leg iii seats sold under the bid-price heuristic", but its displayed formula counts every request above the threshold, which is the alternate system's seat count. The displayed formula is formalized (seatsCounted), as a random variable on the path space of the θk\theta kθk periods.

Preamble
import Mathlib
import Definitions.Def_BidPriceControl_Asymptotic_Model
Formal statement
namespace BidPriceControl.Asymptotic

open MeasureTheory ProbabilityTheory

/-- The coupling bound (14) of the proof of Theorem 1 (p. 1585): if the revenues are bounded by `C`
(a.s.) and `μ*` is an optimal solution of (9) for `(x, k)`, the expected revenue of the
fixed-bid-price heuristic with bid prices `μ*` in the `θ`-scaled problem satisfies
`J^H_{θk}(θx) ≥ ∑_{t=1}^{θk} ∑_j E(R_t^j(θ) − μ*A^j)^+ + ∑_{t=1}^{θk} ∑_j P(R_t^j(θ) > μ*A^j) μ*A^j
 − C ∑_i E(N^i − θx^i)^+`,
where `N^i = ∑_{t=1}^{θk} ∑_j 1{R_t^j(θ) > μ*A^j} a_ij` counts the leg-`i` seats of the uncapacitated
alternate system. -/
theorem coupling_bound {m n : ℕ} (A : Fin m → Fin n → ℕ) (F : ℕ → Measure (Fin n → ℝ))
    (k : ℕ) (x : Fin m → ℕ) (hF : ∀ t ∈ Finset.Icc 1 k, IsRequestLaw (F t))
    (C : ℝ) (hC : ∀ t ∈ Finset.Icc 1 k, ∀ᵐ r ∂(F t), ∀ j, r j ≤ C)
    (μstar : Fin m → ℝ) (hmin : IsRelaxedMinimizer A F k x μstar) (θ : ℕ) (hθ : 1 ≤ θ) :
    (∑ t ∈ Finset.Icc 1 (θ * k), ∑ j, ∫ r, max (r j - bidSum A μstar j) 0 ∂(scaledLaw F θ t))
      + (∑ t ∈ Finset.Icc 1 (θ * k), ∑ j, exceedProb A (scaledLaw F θ) μstar t j * bidSum A μstar j)
      - C * ∑ i, ∫ ω, max (seatsCounted A μstar i ω - (θ : ℝ) * (x i : ℝ)) 0
          ∂(pathMeasure (scaledLaw F θ) (θ * k))
      ≤ heuristicValue A (scaledLaw F θ) (θ * k) (θ • x) μstar := by sorry

end BidPriceControl.Asymptotic
Source
Talluri, van Ryzin, An Analysis of Bid-Price Controls for Network Revenue Management, Management Sci. 44(11), 1998, p. 1585, eq. (14)
Read-back

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

Opaque definitions. This statement uses several definitions from the imported module Definitions.Def_BidPriceControl_Asymptotic_Model. Their bodies are not part of the code I was given. The read-back therefore treats them as opaque and names them by their role in the statement only:

  • IsRequestLaw(⋅)\mathrm{IsRequestLaw}(\cdot)IsRequestLaw(⋅) is a property of a measure.
  • IsRelaxedMinimizer(⋅)\mathrm{IsRelaxedMinimizer}(\cdot)IsRelaxedMinimizer(⋅) is a property of the data and a vector.
  • βj:=bidSum(A,μ∗,j)∈R\beta_j := \mathrm{bidSum}(A,\mu^*,j)\in\mathbb Rβj​:=bidSum(A,μ∗,j)∈R.
  • Ft(θ):=scaledLaw(F,θ,t)F^{(\theta)}_t := \mathrm{scaledLaw}(F,\theta,t)Ft(θ)​:=scaledLaw(F,θ,t) is a measure on Rn\mathbb R^nRn.
  • pt,j(G):=exceedProb(A,G,μ∗,t,j)∈Rp_{t,j}(G) := \mathrm{exceedProb}(A,G,\mu^*,t,j)\in\mathbb Rpt,j​(G):=exceedProb(A,G,μ∗,t,j)∈R.
  • PT(θ):=pathMeasure(F(θ),T)\mathbb P^{(\theta)}_T := \mathrm{pathMeasure}(F^{(\theta)},T)PT(θ)​:=pathMeasure(F(θ),T) is a measure on some sample space Ω\OmegaΩ.
  • Ni(ω):=seatsCounted(A,μ∗,i,ω)∈RN_i(\omega) := \mathrm{seatsCounted}(A,\mu^*,i,\omega)\in\mathbb RNi​(ω):=seatsCounted(A,μ∗,i,ω)∈R. It has no explicit θ\thetaθ, kkk or horizon argument; it depends only on AAA, μ∗\mu^*μ∗, iii and ω\omegaω.
  • JH:=heuristicValue(A, F(θ), T, y, μ∗)∈RJ^H := \mathrm{heuristicValue}(A,\,F^{(\theta)},\,T,\,y,\,\mu^*)\in\mathbb RJH:=heuristicValue(A,F(θ),T,y,μ∗)∈R.

Data.

  • m,n∈Nm,n\in\mathbb Nm,n∈N.
  • A matrix A=(aij)A=(a_{ij})A=(aij​) with i∈{0,…,m−1}i\in\{0,\dots,m-1\}i∈{0,…,m−1}, j∈{0,…,n−1}j\in\{0,\dots,n-1\}j∈{0,…,n−1} and natural-number entries aij∈Na_{ij}\in\mathbb Naij​∈N.
  • A sequence of measures FtF_tFt​ on Rn\mathbb R^nRn, indexed by every t∈Nt\in\mathbb Nt∈N.
  • A horizon k∈Nk\in\mathbb Nk∈N.
  • A capacity vector x∈Nmx\in\mathbb N^mx∈Nm.
  • A real number CCC.
  • A real vector μ∗∈Rm\mu^*\in\mathbb R^mμ∗∈Rm.
  • A natural number θ\thetaθ.

Hypotheses.

  1. For every t∈{1,…,k}t\in\{1,\dots,k\}t∈{1,…,k}, IsRequestLaw(Ft)\mathrm{IsRequestLaw}(F_t)IsRequestLaw(Ft​) holds. Nothing is assumed about FtF_tFt​ for t=0t=0t=0 or t>kt>kt>k.
  2. For every t∈{1,…,k}t\in\{1,\dots,k\}t∈{1,…,k}, for FtF_tFt​-almost every r∈Rnr\in\mathbb R^nr∈Rn, every coordinate satisfies rj≤Cr_j\le Crj​≤C. This is only an upper bound; no lower bound on rjr_jrj​ is assumed, and CCC is not required to be nonnegative.
  3. IsRelaxedMinimizer(A,F,k,x,μ∗)\mathrm{IsRelaxedMinimizer}(A,F,k,x,\mu^*)IsRelaxedMinimizer(A,F,k,x,μ∗) holds.
  4. θ≥1\theta\ge 1θ≥1.

Conclusion. The statement asserts

∑t=1θk∑j∫max⁡(rj−βj, 0) dFt(θ)(r)  +  ∑t=1θk∑jpt,j(F(θ)) βj  −  C∑i∫Ωmax⁡(Ni(ω)−θxi, 0) dPθk(θ)(ω)  ≤  JH(A, F(θ), θk, θx, μ∗),\sum_{t=1}^{\theta k}\sum_{j}\int \max\bigl(r_j-\beta_j,\,0\bigr)\,dF^{(\theta)}_t(r) \;+\;\sum_{t=1}^{\theta k}\sum_{j} p_{t,j}\bigl(F^{(\theta)}\bigr)\,\beta_j \;-\;C\sum_{i}\int_\Omega \max\bigl(N_i(\omega)-\theta x_i,\,0\bigr)\,d\mathbb P^{(\theta)}_{\theta k}(\omega) \;\le\; J^H\bigl(A,\,F^{(\theta)},\,\theta k,\,\theta x,\,\mu^*\bigr),t=1∑θk​j∑​∫max(rj​−βj​,0)dFt(θ)​(r)+t=1∑θk​j∑​pt,j​(F(θ))βj​−Ci∑​∫Ω​max(Ni​(ω)−θxi​,0)dPθk(θ)​(ω)≤JH(A,F(θ),θk,θx,μ∗),

where:

  • the sums over jjj run over all nnn indices and the sums over iii run over all mmm indices;
  • θx\theta xθx is the componentwise product (θx1,…,θxm)∈Nm(\theta x_1,\dots,\theta x_m)\in\mathbb N^m(θx1​,…,θxm​)∈Nm;
  • the integrals are Bochner integrals, so the integral of a function that is not integrable is taken to be 000.

Hypotheses 1 and 2 speak about FtF_tFt​ only for 1≤t≤k1\le t\le k1≤t≤k. The sums in the conclusion run up to θk\theta kθk over the scaled laws Ft(θ)F^{(\theta)}_tFt(θ)​. How Ft(θ)F^{(\theta)}_tFt(θ)​ relates to the FtF_tFt​ is determined by the opaque definition of scaledLaw\mathrm{scaledLaw}scaledLaw.

Degenerate cases.

  • k=0k=0k=0: Hypotheses 1 and 2 are vacuous, and both sums over ttt are empty. The claim becomes
−C∑i∫max⁡(Ni−θxi,0) dP0(θ)≤JH(A,F(θ),0,θx,μ∗),-C\sum_i\int\max(N_i-\theta x_i,0)\,d\mathbb P^{(\theta)}_0\le J^H(A,F^{(\theta)},0,\theta x,\mu^*),−Ci∑​∫max(Ni​−θxi​,0)dP0(θ)​≤JH(A,F(θ),0,θx,μ∗),

with CCC completely unconstrained.

  • n=0n=0n=0: Both double sums over jjj are 000. Hypothesis 2 holds trivially because there are no coordinates, so CCC is again unconstrained.
  • m=0m=0m=0: The last sum over iii is 000, so the CCC-term vanishes.
  • θ=1\theta=1θ=1: Allowed. The claim concerns horizon kkk, capacity xxx and F(1)F^{(1)}F(1).
  • Sign of CCC: If C<0C<0C<0, the third term is added rather than subtracted.
  • Non-integrable integrands: Any integrand here that fails to be integrable (for example, if max⁡(rj−βj,0)\max(r_j-\beta_j,0)max(rj​−βj​,0) is not Ft(θ)F^{(\theta)}_tFt(θ)​-integrable) contributes 000 in place of its integral.

Whether hypotheses 1 and 3 can be satisfied at all depends on the opaque definitions and cannot be determined from this code.

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