Coupling bound (14): J^H_θk(θx) ≥ Σ E(R − μ*A^j)⁺ + Σ P(R > μ*A^j)μ*A^j − C Σ_i E(Nⁱ − θxⁱ)⁺
ProvedBidPriceControl.Asymptotic.coupling_boundAssume the standing assumptions of §1 and almost surely. Let be an optimal solution of (9) for and let be an integer. The fixed-bid-price heuristic with bid prices in the -scaled problem earns
where . 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 for each seat that system sells beyond a leg's capacity.
Formalization Note. As on the page, the bid prices are an optimal solution of (9) (a predicate, IsRelaxedMinimizer, so every minimizer is covered). The page calls "the number of leg 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 periods.
import Mathlib import Definitions.Def_BidPriceControl_Asymptotic_Model
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
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:
- is a property of a measure.
- is a property of the data and a vector.
- .
- is a measure on .
- .
- is a measure on some sample space .
- . It has no explicit , or horizon argument; it depends only on , , and .
- .
Data.
- .
- A matrix with , and natural-number entries .
- A sequence of measures on , indexed by every .
- A horizon .
- A capacity vector .
- A real number .
- A real vector .
- A natural number .
Hypotheses.
- For every , holds. Nothing is assumed about for or .
- For every , for -almost every , every coordinate satisfies . This is only an upper bound; no lower bound on is assumed, and is not required to be nonnegative.
- holds.
- .
Conclusion. The statement asserts
where:
- the sums over run over all indices and the sums over run over all indices;
- is the componentwise product ;
- the integrals are Bochner integrals, so the integral of a function that is not integrable is taken to be .
Hypotheses 1 and 2 speak about only for . The sums in the conclusion run up to over the scaled laws . How relates to the is determined by the opaque definition of .
Degenerate cases.
- : Hypotheses 1 and 2 are vacuous, and both sums over are empty. The claim becomes
with completely unconstrained.
- : Both double sums over are . Hypothesis 2 holds trivially because there are no coordinates, so is again unconstrained.
- : The last sum over is , so the -term vanishes.
- : Allowed. The claim concerns horizon , capacity and .
- Sign of : If , the third term is added rather than subtracted.
- Non-integrable integrands: Any integrand here that fails to be integrable (for example, if is not -integrable) contributes 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.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.