Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1: the fixed-bid-price heuristic is asymptotically optimal, J^H_θk(θx) ≥ (1 − K/√θ) J_θk(θx)

Proved
BidPriceControl.Asymptotic.fixed_bid_price_asymptotically_optimal

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

dynamic-programmingp2o-batch-rm-cafterp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilityrevenue-management

Consider a network with seat matrix AAA, capacities xxx, horizon kkk and request laws F1,…,FkF_1, \dots, F_kF1​,…,Fk​ satisfying the standing assumptions of §1. Suppose the revenues are bounded, Rtj≤CR_t^j \le CRtj​≤C almost surely. Let μ∗\mu^*μ∗ be an optimal solution of (9) for (x,k)(x, k)(x,k). Then there is a constant KKK, depending on the instance but not on θ\thetaθ, such that for every integer θ≥1\theta \ge 1θ≥1 the fixed-bid-price heuristic with bid prices μ∗\mu^*μ∗ in the θ\thetaθ-scaled problem satisfies

JθkH(θx)≥(1−Kθ) Jθk(θx).J^H_{\theta k}(\theta x) \ge \Big(1 - \frac{K}{\sqrt\theta}\Big)\,J_{\theta k}(\theta x).JθkH​(θx)≥(1−θ​K​)Jθk​(θx).

This is Theorem 1, JθkH(θx)/Jθk(θx)≥1−O(θ−1/2)J^H_{\theta k}(\theta x)/J_{\theta k}(\theta x) \ge 1 - O(\theta^{-1/2})JθkH​(θx)/Jθk​(θx)≥1−O(θ−1/2). Here Jθk(θx)J_{\theta k}(\theta x)Jθk​(θx) is the optimal expected revenue given by the Bellman equations (2)–(3). JθkH(θx)J^H_{\theta k}(\theta x)JθkH​(θx) is the expected revenue of the heuristic that accepts a request for itinerary jjj with revenue rrr if and only if capacity suffices and r>μ∗Ajr > \mu^* A^jr>μ∗Aj. So using the single fixed vector of bid prices from the upper-bound problem loses a vanishing fraction of the optimal revenue as capacity and demand grow in proportion.

Formalization Note. The ratio is multiplied out, because Jθk(θx)J_{\theta k}(\theta x)Jθk​(θx) may be 000 (for example when every itinerary uses a leg of capacity 000). There the paper's ratio is 0/00/00/0, while Lean's 0/0=00/0 = 00/0=0 would make the literal ratio statement false. For J>0J > 0J>0 the two forms are equivalent. The constant KKK is quantified before θ\thetaθ and may depend on A,F,C,k,x,μ∗A, F, C, k, x, \mu^*A,F,C,k,x,μ∗. The paper's "in particular" limit JH/J→1J^H/J \to 1JH/J→1 is not part of this item. It needs vk(x)>0v_k(x) > 0vk​(x)>0, which the paper leaves implicit.

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

open MeasureTheory ProbabilityTheory

/-- Theorem 1 (Talluri–van Ryzin 1998, p. 1585): if `R_t^j ≤ C` (a.s.), then
`J^H_{θk}(θx) / J_{θk}(θx) ≥ 1 − O(θ^{-1/2})`. Stated multiplied out, with an explicit constant
`K` fixed before `θ`: for every optimal solution `μ*` of (9) for `(x, k)` there is `K` such that
for every integer `θ ≥ 1` the fixed-bid-price heuristic with bid prices `μ*` in the `θ`-scaled
problem earns `J^H_{θk}(θx) ≥ (1 − K/√θ) J_{θk}(θx)`. -/
theorem fixed_bid_price_asymptotically_optimal {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) :
    ∃ K : ℝ, ∀ θ : ℕ, 1 ≤ θ →
      (1 - K / Real.sqrt (θ : ℝ)) * optValue A (scaledLaw F θ) (θ * k) (θ • x)
        ≤ 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, Theorem 1
Read-back

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

Let m,n∈Nm, n \in \mathbb{N}m,n∈N. The statement takes the following data:

  • a matrix A=(Aij)A = (A_{ij})A=(Aij​) of natural numbers, with rows indexed by i∈{0,…,m−1}i \in \{0,\dots,m-1\}i∈{0,…,m−1} and columns by j∈{0,…,n−1}j \in \{0,\dots,n-1\}j∈{0,…,n−1};
  • a sequence (Ft)t∈N(F_t)_{t \in \mathbb{N}}(Ft​)t∈N​ of measures on Rn\mathbb{R}^nRn, with no restriction on its type such as being a probability measure;
  • a natural number kkk and a vector x∈Nmx \in \mathbb{N}^mx∈Nm;
  • a real number CCC and a vector μ∗∈Rm\mu^* \in \mathbb{R}^mμ∗∈Rm.

The hypotheses are:

  1. For every ttt with 1≤t≤k1 \le t \le k1≤t≤k, FtF_tFt​ satisfies the predicate IsRequestLaw\mathrm{IsRequestLaw}IsRequestLaw.
  2. For every ttt with 1≤t≤k1 \le t \le k1≤t≤k, for FtF_tFt​-almost every r∈Rnr \in \mathbb{R}^nr∈Rn, rj≤Cr_j \le Crj​≤C for every coordinate jjj. This is only an upper bound. Nothing bounds rjr_jrj​ from below, and CCC need not be nonnegative.
  3. μ∗\mu^*μ∗ satisfies IsRelaxedMinimizer(A,F,k,x,μ∗)\mathrm{IsRelaxedMinimizer}(A, F, k, x, \mu^*)IsRelaxedMinimizer(A,F,k,x,μ∗).

The predicates IsRequestLaw\mathrm{IsRequestLaw}IsRequestLaw and IsRelaxedMinimizer\mathrm{IsRelaxedMinimizer}IsRelaxedMinimizer and the functions optValue\mathrm{optValue}optValue, heuristicValue\mathrm{heuristicValue}heuristicValue and scaledLaw\mathrm{scaledLaw}scaledLaw come from the imported module Definitions.Def_BidPriceControl_Asymptotic_Model. Their definitions are not part of the code under audit, so this read-back does not expand them. Their names are the only indication of their content, and what the statement asserts depends entirely on how they are defined. In particular, nothing here says whether IsRelaxedMinimizer\mathrm{IsRelaxedMinimizer}IsRelaxedMinimizer can be satisfied, or whether it and IsRequestLaw\mathrm{IsRequestLaw}IsRequestLaw look at FtF_tFt​ outside 1≤t≤k1 \le t \le k1≤t≤k.

The conclusion is that there exists a real number KKK such that, for every natural number θ≥1\theta \ge 1θ≥1,

(1−Kθ) optValue(A, scaledLaw(F,θ), θk, θx)  ≤  heuristicValue(A, scaledLaw(F,θ), θk, θx, μ∗).\Bigl(1 - \frac{K}{\sqrt{\theta}}\Bigr)\,\mathrm{optValue}\bigl(A,\ \mathrm{scaledLaw}(F,\theta),\ \theta k,\ \theta x\bigr) \;\le\; \mathrm{heuristicValue}\bigl(A,\ \mathrm{scaledLaw}(F,\theta),\ \theta k,\ \theta x,\ \mu^*\bigr).(1−θ​K​)optValue(A, scaledLaw(F,θ), θk, θx)≤heuristicValue(A, scaledLaw(F,θ), θk, θx, μ∗).

Here θx\theta xθx is the componentwise product in Nm\mathbb{N}^mNm and θk\theta kθk is the product in N\mathbb{N}N. KKK is chosen after all the data A,F,k,x,C,μ∗A, F, k, x, C, \mu^*A,F,k,x,C,μ∗ and may depend on them, but it cannot depend on θ\thetaθ.

KKK is any real number. It is not required to be positive, so the factor 1−K/θ1 - K/\sqrt{\theta}1−K/θ​ may exceed 111 or be negative. The heuristic value is always taken at the same unscaled vector μ∗\mu^*μ∗ for every θ\thetaθ. The inequality compares values multiplied out; no ratio of the two values appears. How strong the claim is depends on the signs of the optValue\mathrm{optValue}optValue terms, which the statement does not constrain:

  • If optValue>0\mathrm{optValue} > 0optValue>0, the claim is equivalent to (optValue−heuristicValue)θ/optValue≤K(\mathrm{optValue} - \mathrm{heuristicValue})\sqrt{\theta}/\mathrm{optValue} \le K(optValue−heuristicValue)θ​/optValue≤K for all θ≥1\theta \ge 1θ≥1.
  • If optValue=0\mathrm{optValue} = 0optValue=0, it only says heuristicValue≥0\mathrm{heuristicValue} \ge 0heuristicValue≥0.
  • If optValue<0\mathrm{optValue} < 0optValue<0, the direction of the bound on KKK reverses.

Degenerate cases, as the code reads:

  • k=0k = 0k=0. Hypotheses 1 and 2 are vacuous, CCC and all FtF_tFt​ are unconstrained by them, and every scaled problem has horizon θk=0\theta k = 0θk=0.
  • n=0n = 0n=0. R0\mathbb{R}^0R0 has one point and the quantifier over jjj is empty, so hypothesis 2 holds automatically for any CCC.
  • m=0m = 0m=0. xxx, μ∗\mu^*μ∗ and AAA are empty.
  • Zero measure. If some FtF_tFt​ is the zero measure, hypothesis 2 holds trivially for that ttt, unless IsRequestLaw\mathrm{IsRequestLaw}IsRequestLaw excludes it.
  • Measures outside 1≤t≤k1 \le t \le k1≤t≤k. F0F_0F0​ and FtF_tFt​ for t>kt > kt>k are not restricted by hypotheses 1 and 2.
  • θ=1\theta = 1θ=1. The inequality reads (1−K) optValue(A,scaledLaw(F,1),k,x)≤heuristicValue(A,scaledLaw(F,1),k,x,μ∗)(1 - K)\,\mathrm{optValue}(A, \mathrm{scaledLaw}(F,1), k, x) \le \mathrm{heuristicValue}(A, \mathrm{scaledLaw}(F,1), k, x, \mu^*)(1−K)optValue(A,scaledLaw(F,1),k,x)≤heuristicValue(A,scaledLaw(F,1),k,x,μ∗).
  • θ=0\theta = 0θ=0. Excluded, so θ≥1\sqrt{\theta} \ge 1θ​≥1 and no division by zero occurs.
  • Junk values. Whether optValue\mathrm{optValue}optValue or heuristicValue\mathrm{heuristicValue}heuristicValue return a default value (for example, an integral of a non-integrable function, or a supremum of an empty or unbounded set) cannot be seen from this code. If they do, the inequality compares those default values.
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