Explicit bound: J^H_θk(θx) ≥ θ v_k(x) − (C/2)√θ Σ_i √(Σ_t Σ_j Var(Y_ijt))
ProvedBidPriceControl.Asymptotic.explicit_lower_boundp2o-batch-rm-cafterp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilityrevenue-management
Assume the standing assumptions of §1 and almost surely, and let be an optimal solution of (9) for , so that . Then for every integer the fixed-bid-price heuristic with bid prices earns, in the -scaled problem,
where and with . This is the paper's with the explicit constant of p. 1586.
Formalization Note. The constant is carried exactly as printed. is the Bernoulli closed form under the original laws , .
Preamble
import Mathlib import Definitions.Def_BidPriceControl_Asymptotic_Model
Formal statement
namespace BidPriceControl.Asymptotic
open MeasureTheory ProbabilityTheory
/-- The last display of the proof of Theorem 1 (p. 1586): if the revenues are bounded by `C` (a.s.)
and `μ*` is an optimal solution of (9), then for every integer `θ ≥ 1`
`J^H_{θk}(θx) ≥ θ v_k(x) − (C/2) √θ ∑_i √(∑_{t=1}^k ∑_j Var(Y_ijt))`,
where `v_k(x) = J̄_k(x, μ*)` and `Y_ijt = 1{R_t^j > μ*A^j} a_ij`. -/
theorem explicit_lower_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 ≤ θ) :
(θ : ℝ) * relaxedValue A F k x μstar
- C / 2 * Real.sqrt (θ : ℝ) *
∑ i, Real.sqrt (∑ t ∈ Finset.Icc 1 k, ∑ j, indicatorVar A F μstar i t j)
≤ 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. 1586, proof of Theorem 1, last display
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Data. The theorem takes , measures on , , , a real , and with .
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.
- For each such , -a.e. has for every .
- minimizes over , where .
Notation.
- .
- is the expected revenue of the following heuristic under the product measure on whose chronological coordinate has law . It starts from capacity and processes periods in order. In each period it sells the smallest with that fits the current capacity, earning and subtracting . Otherwise it sells nothing.
Conclusion.
Degenerate cases.
- No minimizer: if none exists, the statement is vacuous.
- Sign of : is forced when . When or , is unconstrained.
- : the claim is .
- : the claim is also .
- Square roots: every argument is nonnegative, since .
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.