Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 4 — lower bound on cumulative pricing error (incumbent price problem)

Proved
KeskinZeevi.IncumbentLowerBound.cumulative_pricing_error_lower_bound

by mikedeng1 · Oct 3, 2026 · Mathlib 0df444a (Lean v4.33.1)

dynamic-pricingincumbent-pricelower-boundp2o-batch-rm-cafterp2o-gran-per-chapterp2o-plan-paperp2o-v1van-trees

Consider the incumbent price model, in which the incumbent price relation (18) holds and the demand shocks are i.i.d. N(0,σ2)\mathcal N(0,\sigma^2)N(0,σ2). There exist finite positive constants c0c_0c0​ and c1c_1c1​, depending only on the model, with the following property. For every pricing policy π\piπ and every horizon TTT,

sup⁡β∈B, ψ(β)≠0{∑t=2TEβπ(xt−ψ(β))2}  ≥  ∑t=2Tc0c1+sup⁡β∈B{Eβπ[J^t−1]}.\sup_{\beta \in \mathfrak B,\ \psi(\beta) \ne 0} \left\{ \sum_{t=2}^T \mathbb E^\pi_\beta (x_t - \psi(\beta))^2 \right\} \;\ge\; \sum_{t=2}^T \frac{c_0}{c_1 + \sup_{\beta\in\mathfrak B}\{\mathbb E^\pi_\beta[\hat J_{t-1}]\}}.β∈B, ψ(β)=0sup​{t=2∑T​Eβπ​(xt​−ψ(β))2}≥t=2∑T​c1​+supβ∈B​{Eβπ​[J^t−1​]}c0​​.

Here xt=pt−p^x_t = p_t - \hat pxt​=pt​−p^​ is the price deviation, ψ(β)\psi(\beta)ψ(β) is the optimal deviation, and J^t=∑s=1txs2\hat J_t = \sum_{s=1}^t x_s^2J^t​=∑s=1t​xs2​ 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 B\mathfrak BB.

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 ttt is the paper's period t+1t+1t+1. The paper's ∑t=2T\sum_{t=2}^T∑t=2T​ is the Lean sum over t∈[1,T)t \in [1, T)t∈[1,T), and the paper's J^t−1\hat J_{t-1}J^t−1​ in term ttt is expInfo … t, which sums over Lean periods 0,…,t−10, \dots, t-10,…,t−1. The constants are chosen before the probability space, the noise, the policy and the horizon, so they depend only on the model (l,u,p^,D^,bmin⁡,bmax⁡,σ)(l, u, \hat p, \hat D, b_{\min}, b_{\max}, \sigma)(l,u,p^​,D^,bmin​,bmax​,σ).

Preamble
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
Formal statement
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
Source
Keskin and Zeevi, Dynamic Pricing with an Unknown Demand Model, Operations Research 62(5), 2014, p. 1149, Lemma 4
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Let MMM be any model, with fields l,u,p^,D^,βmin⁡,βmax⁡,σl,u,\hat p,\hat D,\beta_{\min},\beta_{\max},\sigmal,u,p^​,D^,βmin​,βmax​,σ. Write B=[βmin⁡,βmax⁡]\mathfrak B=[\beta_{\min},\beta_{\max}]B=[βmin​,βmax​] and B≠={β∈B:ψ(β)≠0}\mathfrak B^{\ne}=\{\beta\in\mathfrak B:\psi(\beta)\neq0\}B=={β∈B:ψ(β)=0}, where ψ(β)=−p^/2−D^/(2β)\psi(\beta) = -\hat p/2-\hat D/(2\beta)ψ(β)=−p^​/2−D^/(2β).

The statement asserts that there exist constants c0>0c_0>0c0​>0 and c1>0c_1>0c1​>0, chosen depending on MMM alone, with the following property. Take:

  • any measurable space Ω\OmegaΩ (in a fixed but arbitrary universe) and any probability measure PPP on it;
  • any sequence of real functions ε0,ε1,…\varepsilon_0,\varepsilon_1,\dotsε0​,ε1​,… on Ω\OmegaΩ satisfying the predicate "Gaussian noise with parameter σ\sigmaσ under PPP";
  • any policy π\piπ on [l,u][l,u][l,u];
  • any T∈NT\in\mathbb NT∈N.

Then

∑t=1T−1c0c1+sup⁡β∈BInfoβ(t)  ≤  sup⁡β∈B≠∑t=1T−1SqErrβ(t).\sum_{t=1}^{T-1} \frac{c_0}{c_1 + \sup_{\beta\in\mathfrak B}\mathrm{Info}_\beta(t)} \;\le\; \sup_{\beta\in\mathfrak B^{\ne}} \sum_{t=1}^{T-1}\mathrm{SqErr}_\beta(t).t=1∑T−1​c1​+supβ∈B​Infoβ​(t)c0​​≤β∈B=sup​t=1∑T−1​SqErrβ​(t).

Here:

Infoβ(t)=EP[∑s=0t−1xs2],SqErrβ(t)=EP[(xt−ψ(β))2].\mathrm{Info}_\beta(t)=\mathbb E_P\Big[\sum_{s=0}^{t-1}x_s^2\Big],\qquad \mathrm{SqErr}_\beta(t)=\mathbb E_P\big[(x_t-\psi(\beta))^2\big].Infoβ​(t)=EP​[s=0∑t−1​xs2​],SqErrβ​(t)=EP​[(xt​−ψ(β))2].

The deviations are xs=ps−p^x_s = p_s-\hat pxs​=ps​−p^​, where psp_sps​ is the price path generated by π\piπ under slope β\betaβ and shocks εs(ω)\varepsilon_s(\omega)εs​(ω), with period indices starting at 000.

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 σ2\sigma^2σ2, or measurability of each εt\varepsilon_tεt​. Beyond that predicate, no measurability of ε\varepsilonε is assumed.

Both suprema are real suprema, which equal 000 if the family is not bounded above. In particular:

  • sup⁡BInfoβ(t)\sup_{\mathfrak B}\mathrm{Info}_\beta(t)supB​Infoβ​(t) is either a genuine supremum of nonnegative numbers or the default 000. Either way the denominator is at least c1>0c_1>0c1​>0, so no division by zero occurs.
  • If the right-hand family were unbounded, the right side would be 000.

Degenerate cases:

  • For T=0T=0T=0 and T=1T=1T=1 the sum over ttt is empty, so the left side is 000. The statement then asserts only that the right-hand supremum is ≥0\ge 0≥0, which holds because every SqErr\mathrm{SqErr}SqErr is nonnegative.
  • The same c0,c1c_0,c_1c0​,c1​ must work for all Ω\OmegaΩ, PPP, ε\varepsilonε, π\piπ and TTT simultaneously.
Human review
  • Endorsed by Shuze Chen · Oct 21, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 21, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me