Lemma 4 — lower bound on cumulative pricing error (incumbent price problem)
ProvedKeskinZeevi.IncumbentLowerBound.cumulative_pricing_error_lower_boundConsider the incumbent price model, in which the incumbent price relation (18) holds and the demand shocks are i.i.d. . There exist finite positive constants and , depending only on the model, with the following property. For every pricing policy and every horizon ,
Here is the price deviation, is the optimal deviation, and is the information metric (24). The supremum on the left ranges over the slopes for which the incumbent price is not optimal. The supremum on the right ranges over all of .
This is the incumbent price analog of Lemma 1. It says that the cumulative pricing error can be small only if information accumulates, and it is the step from which Theorem 3 follows.
Formalization Note. Lean period is the paper's period . The paper's is the Lean sum over , and the paper's in term is expInfo … t, which sums over Lean periods . The constants are chosen before the probability space, the noise, the policy and the horizon, so they depend only on the model .
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
/-- Lemma 4 (Lower Bound on Cumulative Pricing Error), p. 1149, Eq. (25). Lean period `t` is the
paper's period `t + 1`, so the paper's `Σ_{t=2}^T` is `Σ_{t ∈ [1, T)}` here, and the paper's
`Ĵ_{t−1}` for the deviation `x_t` is `expInfo … t` for the Lean deviation `dev … t`. The
left supremum ranges over `{β ∈ 𝔅 : ψ(β) ≠ 0}`, the right one over all of `𝔅`, as printed.
The constants depend only on the model `M`. -/
theorem cumulative_pricing_error_lower_bound (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.B, expInfo M P ε π (β : ℝ) 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 . Write and , where .
The statement asserts that there exist constants and , chosen depending on alone, with the following property. Take:
- any measurable space (in a fixed but arbitrary universe) and any probability measure on it;
- any sequence of real functions on satisfying the predicate "Gaussian noise with parameter under ";
- any policy on ;
- any .
Then
Here:
The deviations are , where is the price path generated by under slope and shocks , with period indices starting at .
The Gaussian-noise predicate is imported from a separate bundle and its definition is not part of this code. The read-back therefore cannot state what it requires, for instance independence, the variance , or measurability of each . Beyond that predicate, no measurability of is assumed.
Both suprema are real suprema, which equal if the family is not bounded above. In particular:
- is either a genuine supremum of nonnegative numbers or the default . Either way the denominator is at least , so no division by zero occurs.
- If the right-hand family were unbounded, the right side would be .
Degenerate cases:
- For and the sum over is empty, so the left side is . The statement then asserts only that the right-hand supremum is , which holds because every is nonnegative.
- The same must work for all , , , and simultaneously.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.