Theorem 1: the fixed-bid-price heuristic is asymptotically optimal, J^H_θk(θx) ≥ (1 − K/√θ) J_θk(θx)
ProvedBidPriceControl.Asymptotic.fixed_bid_price_asymptotically_optimalConsider a network with seat matrix , capacities , horizon and request laws satisfying the standing assumptions of §1. Suppose the revenues are bounded, almost surely. Let be an optimal solution of (9) for . Then there is a constant , depending on the instance but not on , such that for every integer the fixed-bid-price heuristic with bid prices in the -scaled problem satisfies
This is Theorem 1, . Here is the optimal expected revenue given by the Bellman equations (2)–(3). is the expected revenue of the heuristic that accepts a request for itinerary with revenue if and only if capacity suffices and . 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 may be (for example when every itinerary uses a leg of capacity ). There the paper's ratio is , while Lean's would make the literal ratio statement false. For the two forms are equivalent. The constant is quantified before and may depend on . The paper's "in particular" limit is not part of this item. It needs , which the paper leaves implicit.
import Mathlib import Definitions.Def_BidPriceControl_Asymptotic_Model
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
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Let . The statement takes the following data:
- a matrix of natural numbers, with rows indexed by and columns by ;
- a sequence of measures on , with no restriction on its type such as being a probability measure;
- a natural number and a vector ;
- a real number and a vector .
The hypotheses are:
- For every with , satisfies the predicate .
- For every with , for -almost every , for every coordinate . This is only an upper bound. Nothing bounds from below, and need not be nonnegative.
- satisfies .
The predicates and and the functions , and 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 can be satisfied, or whether it and look at outside .
The conclusion is that there exists a real number such that, for every natural number ,
Here is the componentwise product in and is the product in . is chosen after all the data and may depend on them, but it cannot depend on .
is any real number. It is not required to be positive, so the factor may exceed or be negative. The heuristic value is always taken at the same unscaled vector for every . The inequality compares values multiplied out; no ratio of the two values appears. How strong the claim is depends on the signs of the terms, which the statement does not constrain:
- If , the claim is equivalent to for all .
- If , it only says .
- If , the direction of the bound on reverses.
Degenerate cases, as the code reads:
- . Hypotheses 1 and 2 are vacuous, and all are unconstrained by them, and every scaled problem has horizon .
- . has one point and the quantifier over is empty, so hypothesis 2 holds automatically for any .
- . , and are empty.
- Zero measure. If some is the zero measure, hypothesis 2 holds trivially for that , unless excludes it.
- Measures outside . and for are not restricted by hypotheses 1 and 2.
- . The inequality reads .
- . Excluded, so and no division by zero occurs.
- Junk values. Whether or 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.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.