Eq. (15): E(Nⁱ − θxⁱ)⁺ ≤ √Var(Nⁱ)/2
ProvedBidPriceControl.Asymptotic.overflow_boundp2o-batch-rm-cafterp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilityrevenue-management
Assume the standing assumptions of §1, let be an optimal solution of (9) for , and let be an integer. In the -scaled problem let . Then for every leg ,
The expected overflow of the uncapacitated system on each leg thus grows at most like a standard deviation, that is, like , while revenues grow like .
Formalization Note. and are taken under the product law of the scaled periods (pathMeasure). No bound is needed.
Preamble
import Mathlib import Definitions.Def_BidPriceControl_Asymptotic_Model
Formal statement
namespace BidPriceControl.Asymptotic
open MeasureTheory ProbabilityTheory
/-- Display (15) of the proof of Theorem 1 (pp. 1585–1586): for an optimal solution `μ*` of (9) and
the `θ`-scaled problem, `E(N^i − θx^i)^+ ≤ √Var(N^i) / 2` for every leg `i`, where
`N^i = ∑_{t=1}^{θk} ∑_j 1{R_t^j(θ) > μ*A^j} a_ij`. -/
theorem overflow_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))
(μstar : Fin m → ℝ) (hmin : IsRelaxedMinimizer A F k x μstar) (θ : ℕ) (hθ : 1 ≤ θ)
(i : Fin m) :
∫ ω, max (seatsCounted A μstar i ω - (θ : ℝ) * (x i : ℝ)) 0
∂(pathMeasure (scaledLaw F θ) (θ * k))
≤ Real.sqrt (variance (seatsCounted A μstar i) (pathMeasure (scaledLaw F θ) (θ * k))) / 2 := by sorry
end BidPriceControl.Asymptotic
Source
Talluri, van Ryzin, An Analysis of Bid-Price Controls for Network Revenue Management, Management Sci. 44(11), 1998, pp. 1585–1586, eq. (15)
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Data. The theorem takes , measures on , , , , with , and a leg .
Hypotheses.
- For , is a request law: a probability measure, a.s. nonnegative with at most one positive coordinate, no positive-value atoms, and integrable coordinates.
- minimizes over , and . Here .
Notation.
- is the product measure on with coordinate distributed as .
- .
Conclusion.
Degenerate cases.
- No minimizer: if none exists, the statement is vacuous.
- or : and the claim is .
- Zero variance: in that case the claim is , i.e. a.s. .
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.