Proof of Theorem 3, first display — Lemma 4 with the information metric bounded by (u − l)²(t − 1)
ProvedKeskinZeevi.IncumbentLowerBound.cumulative_pricing_error_lower_bound_linearConsider the incumbent price model with i.i.d. demand shocks. There exist finite positive constants and , depending only on the model, with the following property. For every pricing policy and every horizon ,
The paper derives it from Lemma 4 and the bound on the information metric, which holds because both the prices and the incumbent price lie in . It is the first display of the proof of Theorem 3.
Formalization Note. Lean period is the paper's period . For the paper's , the paper's is the Lean index itself. The constants are chosen before the probability space, the noise, the policy and the horizon.
import Mathlib import Definitions.Def_KeskinZeevi_IncumbentLowerBound_Model import Definitions.Def_KeskinZeevi_IncumbentLowerBound_Policy import Definitions.Def_RobustBooking_Shared_GaussianNoise import Definitions.Def_KeskinZeevi_IncumbentLowerBound_Regret open RobustBooking.Shared open MeasureTheory
namespace KeskinZeevi.IncumbentLowerBound
/-- Proof of Theorem 3, first display (p. 1158): since `Ĵ_s ≤ (u − l)² s`, Lemma 4 gives
`sup_{β∈𝔅, ψ(β)≠0} Σ_{t=2}^T E^π_β(x_t − ψ(β))² ≥ Σ_{t=2}^T c₀ / (c₁ + (u − l)²(t − 1))`.
Lean period `t` is the paper's period `t + 1`; the paper's `t − 1` for `t ∈ [2, T]` is the Lean
index `t ∈ [1, T)` itself. The constants depend only on the model `M`. -/
theorem cumulative_pricing_error_lower_bound_linear (M : Model) :
∃ c₀ : ℝ, 0 < c₀ ∧ ∃ c₁ : ℝ, 0 < c₁ ∧
∀ {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
(ε : ℕ → Ω → ℝ), GaussianNoise M.σ P ε →
∀ (π : Policy M.l M.u) (T : ℕ),
∑ t ∈ Finset.Ico 1 T, c₀ / (c₁ + (M.u - M.l) ^ 2 * (t : ℝ))
≤ ⨆ β : M.Bexcl, ∑ t ∈ Finset.Ico 1 T, sqErr M P ε π (β : ℝ) t := by sorry
end KeskinZeevi.IncumbentLowerBound
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Let be any model, with fields , , , , . Let , where .
The statement asserts that there exist constants and , depending on alone, with the following property. Take:
- any measurable space (fixed but arbitrary universe) and any probability measure on it;
- any real functions on satisfying the imported predicate "Gaussian noise with parameter under ";
- any policy on ;
- any .
Then
Here , where is the price, starting from period , generated by under slope and shocks . Each expectation is a Bochner integral, defaulting to if not integrable.
The Gaussian-noise predicate is defined outside this code and cannot be unfolded here; no other measurability of is assumed. The supremum is the real supremum, which is if the family is unbounded above.
Degenerate cases:
- Each denominator is , since and .
- For the left side is the empty sum . The assertion then reduces to the right-hand supremum being , which holds because every term is nonnegative.
- One pair must serve all .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.