Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Theorem 3, first display on p. 1159 — worst-case regret as the supremum of −β times the cumulative squared pricing error, and its lower bound

Proved
KeskinZeevi.IncumbentLowerBound.regret_eq_neg_beta_sum_sqErr

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

dynamic-pricingincumbent-pricep2o-batch-rm-cafterp2o-gran-per-chapterp2o-plan-paperp2o-v1regret

Consider the incumbent price model with i.i.d. N(0,σ2)\mathcal N(0,\sigma^2)N(0,σ2) demand shocks. 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,

Δπ(T)=sup⁡β∈B, ψ(β)≠0{−β∑t=1TEβπ(xt−ψ(β))2}  ≥  ∣bmax⁡∣∑t=2Tc0c1+(u−l)2(t−1).\Delta^\pi(T) = \sup_{\beta \in \mathfrak B,\ \psi(\beta) \ne 0} \left\{ -\beta \sum_{t=1}^T \mathbb E^\pi_\beta (x_t - \psi(\beta))^2 \right\} \;\ge\; |b_{\max}| \sum_{t=2}^T \frac{c_0}{c_1 + (u-l)^2 (t-1)}.Δπ(T)=β∈B, ψ(β)=0sup​{−βt=1∑T​Eβπ​(xt​−ψ(β))2}≥∣bmax​∣t=2∑T​c1​+(u−l)2(t−1)c0​​.

The paper writes the right side as ∣bmax⁡∣sup⁡β∈B, ψ(β)≠0∑t=2Tc0/(c1+(u−l)2(t−1))|b_{\max}| \sup_{\beta \in \mathfrak B,\ \psi(\beta) \ne 0} \sum_{t=2}^T c_0/(c_1 + (u-l)^2(t-1))∣bmax​∣supβ∈B, ψ(β)=0​∑t=2T​c0​/(c1​+(u−l)2(t−1)); the summand does not depend on β\betaβ, so the supremum is the sum itself.

The equality holds because rβr_\betarβ​ is a quadratic with leading coefficient β\betaβ that is maximized at ψ(β)\psi(\beta)ψ(β), so rβ(ψ(β))−rβ(x)=−β(x−ψ(β))2r_\beta(\psi(\beta)) - r_\beta(x) = -\beta (x - \psi(\beta))^2rβ​(ψ(β))−rβ​(x)=−β(x−ψ(β))2. The inequality follows from −β≥∣bmax⁡∣-\beta \ge |b_{\max}|−β≥∣bmax​∣ for β∈[bmin⁡,bmax⁡]\beta \in [b_{\min}, b_{\max}]β∈[bmin​,bmax​] and the previous display. It turns the lower bound on cumulative pricing error into a lower bound on regret.

Formalization Note. Lean period ttt is the paper's period t+1t+1t+1. The paper's ∑t=1T\sum_{t=1}^T∑t=1T​ is the Lean sum over Finset.range T, and the paper's ∑t=2T\sum_{t=2}^T∑t=2T​ with the term t−1t-1t−1 is the Lean sum over t∈[1,T)t \in [1, T)t∈[1,T) with the term ttt. The constants are chosen before the probability space, the noise, the policy and the horizon, as in Lemma 4, of which they are the constants on the page.

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

/-- Proof of Theorem 3, first display on p. 1159: because `β ∈ [b_min, b_max]`,
`Δ^π(T) = sup_{β∈𝔅, ψ(β)≠0} {−β Σ_{t=1}^T E^π_β(x_t − ψ(β))²}
  ≥ |b_max| sup_{β∈𝔅, ψ(β)≠0} Σ_{t=2}^T c₀ / (c₁ + (u − l)²(t − 1))`,
with `c₀, c₁` the constants of Lemma 4 (the summand does not depend on `β`, so the second
supremum is the sum itself). Lean period `t` is the paper's period `t + 1`: the paper's
`Σ_{t=1}^T` is `Finset.range T`, and the paper's `Σ_{t=2}^T` with `t − 1` is `Finset.Ico 1 T`
with the Lean index `t`. The constants depend only on the model `M`. -/
theorem regret_eq_neg_beta_sum_sqErr (M : Model) :
    ∃ c₀ : ℝ, 0 < c₀ ∧ ∃ c₁ : ℝ, 0 < c₁ ∧
      ∀ {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
        (ε : ℕ → Ω → ℝ), GaussianNoise M.σ P ε →
      ∀ (π : Policy M.l M.u) (T : ℕ),
        worstRegret M P ε π T
            = ⨆ β : M.Bexcl, -(β : ℝ) * ∑ t ∈ Finset.range T, sqErr M P ε π (β : ℝ) t ∧
          |M.bMax| * ∑ t ∈ Finset.Ico 1 T, c₀ / (c₁ + (M.u - M.l) ^ 2 * (t : ℝ))
            ≤ worstRegret 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. 1159, Section A.3, proof of Theorem 3, first display
Read-back

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

This statement uses several definitions whose code is not shown here: Model, Policy, GaussianNoise, worstRegret, sqErr, and the model fields σ\sigmaσ, lll, uuu, bmax⁡b_{\max}bmax​ and Bexcl\mathfrak{B}_{\mathrm{excl}}Bexcl​. This read-back names them but cannot unfold them. It describes only what the statement says about them. The only thing visible about Bexcl\mathfrak{B}_{\mathrm{excl}}Bexcl​ is that its elements can be turned into real numbers. Below, β\betaβ denotes that real number.

Fix a model MMM. It has real parameters σ=M.σ\sigma = M.\sigmaσ=M.σ, l=M.ll = M.ll=M.l, u=M.uu = M.uu=M.u and bmax⁡=M.bmax⁡b_{\max} = M.b_{\max}bmax​=M.bmax​, and an index collection Bexcl=M.Bexcl\mathfrak{B}_{\mathrm{excl}} = M.\mathrm{Bexcl}Bexcl​=M.Bexcl. The statement claims that there exist real constants c0>0c_0 > 0c0​>0 and c1>0c_1 > 0c1​>0 that depend only on MMM, with the following property.

Take any measurable space Ω\OmegaΩ, any probability measure PPP on Ω\OmegaΩ, and any real-valued process ε=(εt)t∈N\varepsilon = (\varepsilon_t)_{t \in \mathbb{N}}ε=(εt​)t∈N​ of functions εt:Ω→R\varepsilon_t : \Omega \to \mathbb{R}εt​:Ω→R that satisfies the predicate GaussianNoise(σ,P,ε)\mathrm{GaussianNoise}(\sigma, P, \varepsilon)GaussianNoise(σ,P,ε). Then for every policy π\piπ of the type Policy(l,u)\mathrm{Policy}(l, u)Policy(l,u) and every horizon T∈NT \in \mathbb{N}T∈N, both of the following hold.

  1. Identity. The quantity worstRegret(M,P,ε,π,T)\mathrm{worstRegret}(M, P, \varepsilon, \pi, T)worstRegret(M,P,ε,π,T) equals a supremum over the index set:
worstRegret(M,P,ε,π,T)  =  sup⁡β∈Bexcl(−β∑t=0T−1sqErr(M,P,ε,π,β,t)).\mathrm{worstRegret}(M,P,\varepsilon,\pi,T) \;=\; \sup_{\beta \in \mathfrak{B}_{\mathrm{excl}}} \Big( -\beta \sum_{t=0}^{T-1} \mathrm{sqErr}(M,P,\varepsilon,\pi,\beta,t) \Big).worstRegret(M,P,ε,π,T)=β∈Bexcl​sup​(−βt=0∑T−1​sqErr(M,P,ε,π,β,t)).

The supremum is the real-valued supremum over all elements of Bexcl\mathfrak{B}_{\mathrm{excl}}Bexcl​. The sum runs over the periods t=0,1,…,T−1t = 0, 1, \dots, T-1t=0,1,…,T−1.

  1. Lower bound. With the same c0c_0c0​ and c1c_1c1​:
∣bmax⁡∣∑t=1T−1c0c1+(u−l)2 t  ≤  worstRegret(M,P,ε,π,T).|b_{\max}| \sum_{t=1}^{T-1} \frac{c_0}{c_1 + (u-l)^2\, t} \;\le\; \mathrm{worstRegret}(M,P,\varepsilon,\pi,T).∣bmax​∣t=1∑T−1​c1​+(u−l)2tc0​​≤worstRegret(M,P,ε,π,T).

The sum runs over t=1,…,T−1t = 1, \dots, T-1t=1,…,T−1. The summand does not involve β\betaβ, π\piπ, PPP or ε\varepsilonε.

The order of the quantifiers matters here. The constants c0c_0c0​ and c1c_1c1​ are chosen once for MMM, before Ω\OmegaΩ, PPP, ε\varepsilonε, π\piπ and TTT. So the same pair must work for every probability space, every admissible noise process, every policy and every horizon. Nothing further is assumed about MMM: there is no sign condition on bmax⁡b_{\max}bmax​, no requirement that l<ul < ul<u, and no requirement that Bexcl\mathfrak{B}_{\mathrm{excl}}Bexcl​ is nonempty.

Degenerate cases.

  • T=0T = 0T=0: Both sums are empty, so each expression inside the supremum is −β⋅0=0-\beta \cdot 0 = 0−β⋅0=0. The identity then claims worstRegret(M,P,ε,π,0)=0\mathrm{worstRegret}(M,P,\varepsilon,\pi,0) = 0worstRegret(M,P,ε,π,0)=0, and the lower bound reduces to 0≤00 \le 00≤0.
  • T=1T = 1T=1: The lower-bound sum is empty, so the bound only says worstRegret(M,P,ε,π,1)≥0\mathrm{worstRegret}(M,P,\varepsilon,\pi,1) \ge 0worstRegret(M,P,ε,π,1)≥0. The identity still involves the single period t=0t = 0t=0.
  • u=lu = lu=l: Every summand is the constant c0/c1c_0/c_1c0​/c1​. The denominator c1+(u−l)2tc_1 + (u-l)^2 tc1​+(u−l)2t is always at least c1>0c_1 > 0c1​>0, so no division by zero can occur.
  • bmax⁡=0b_{\max} = 0bmax​=0: The lower bound is 000.
  • The supremum: It uses the convention for real suprema. If Bexcl\mathfrak{B}_{\mathrm{excl}}Bexcl​ is empty, or the set of values is not bounded above, the supremum is by convention 000. In that situation the identity claims the worst regret is 000. The lower bound then requires ∣bmax⁡∣∑t=1T−1c0/(c1+(u−l)2t)≤0|b_{\max}| \sum_{t=1}^{T-1} c_0/(c_1+(u-l)^2 t) \le 0∣bmax​∣∑t=1T−1​c0​/(c1​+(u−l)2t)≤0. With c0,c1>0c_0, c_1 > 0c0​,c1​>0, that can only hold if bmax⁡=0b_{\max} = 0bmax​=0 or T≤1T \le 1T≤1.
  • Vacuous cases: If no process satisfies GaussianNoise(σ,P,ε)\mathrm{GaussianNoise}(\sigma, P, \varepsilon)GaussianNoise(σ,P,ε) for any probability space, or if Policy(l,u)\mathrm{Policy}(l, u)Policy(l,u) has no elements, the part after the choice of constants holds vacuously. The statement then only asserts that some positive c0c_0c0​ and c1c_1c1​ exist.
  • Hidden conventions: sqErr\mathrm{sqErr}sqErr and worstRegret\mathrm{worstRegret}worstRegret may involve expectations. An expectation of a non-integrable function would silently take the default value 000, but that cannot be seen from this code.
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