Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3 — logarithmic lower bound on worst-case regret with a known incumbent price

Proved
KeskinZeevi.IncumbentLowerBound.regret_lower_bound_log

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

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

Consider the incumbent price model of §3.4. Prices lie in [l,u][l,u][l,u] with 0≤l<u0 \le l < u0≤l<u. The seller knows an incumbent price p^∈[l,u]\hat p \in [l,u]p^​∈[l,u] and the incumbent demand D^≠0\hat D \ne 0D^=0 at that price, so that D^=α+βp^\hat D = \alpha + \beta\hat pD^=α+βp^​ (the incumbent price relation (18)). The unknown slope β\betaβ lies in B=[bmin⁡,bmax⁡]\mathfrak B = [b_{\min}, b_{\max}]B=[bmin​,bmax​] with bmin⁡<bmax⁡<0b_{\min} < b_{\max} < 0bmin​<bmax​<0, and the optimal price is interior to [l,u][l,u][l,u] for every β∈B\beta \in \mathfrak Bβ∈B. Demand in period ttt is Dt=D^+βxt+ϵtD_t = \hat D + \beta x_t + \epsilon_tDt​=D^+βxt​+ϵt​, where xt=pt−p^x_t = p_t - \hat pxt​=pt​−p^​ and the shocks ϵt\epsilon_tϵt​ are i.i.d. N(0,σ2)\mathcal N(0, \sigma^2)N(0,σ2) with σ>0\sigma > 0σ>0.

Theorem 3. There exists a finite positive constant ccc such that for every pricing policy π\piπ and every horizon T≥3T \ge 3T≥3,

Δπ(T)  ≥  clog⁡T.\Delta^\pi(T) \;\ge\; c \log T.Δπ(T)≥clogT.

Here Δπ(T)=sup⁡{Δβπ(T):bmin⁡≤β≤bmax⁡, ψ(β)≠0}\Delta^\pi(T) = \sup\{\Delta^\pi_\beta(T) : b_{\min} \le \beta \le b_{\max},\ \psi(\beta) \ne 0\}Δπ(T)=sup{Δβπ​(T):bmin​≤β≤bmax​, ψ(β)=0} is the worst-case regret (22), and log⁡\loglog is the natural logarithm.

Knowing the demand at one price lets the seller learn "for free" whenever it charges any other price, and the attainable regret drops from order T\sqrt TT​ (Theorem 1) to order log⁡T\log TlogT. This theorem shows that log⁡T\log TlogT cannot be beaten. Theorem 4 shows that it is achieved.

Formalization Note. The constant ccc is chosen before the probability space, the noise, the policy and the horizon, so it depends 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​,σ). Policies are deterministic and non-anticipating, and their price process is generated from the noise by the recursion of the policy definition. The hypotheses p^∈[l,u]\hat p \in [l,u]p^​∈[l,u] and D^≠0\hat D \ne 0D^=0 are fields of the model; they are implicit on the page, and without D^≠0\hat D \ne 0D^=0 the theorem is false.

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

/-- Theorem 3 (Lower Bound on Regret), p. 1149: under the incumbent price relation (18) there
is a finite positive constant `c`, depending only on the model `M` (price interval, incumbent
price and demand, slope interval, noise level), such that `Δ^π(T) ≥ c log T` for every pricing
policy `π` and every horizon `T ≥ 3`; `Δ^π(T)` is the worst-case regret (22) over
`{β ∈ 𝔅 : ψ(β) ≠ 0}`. -/
theorem regret_lower_bound_log (M : Model) :
    ∃ c : ℝ, 0 < c ∧
      ∀ {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
        (ε : ℕ → Ω → ℝ), GaussianNoise M.σ P ε →
      ∀ (π : Policy M.l M.u) (T : ℕ), 3 ≤ T →
        c * Real.log 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. 1149, Theorem 3
Read-back

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

Fix a model MMM, an object of the bundle's type Model. The statement uses four named parts of MMM:

  • σ=M.σ\sigma = M.\sigmaσ=M.σ, a noise parameter;
  • l=M.ll = M.ll=M.l and u=M.uu = M.uu=M.u, two parameters that index the policy class;
  • MMM itself, which is passed whole to the regret functional.

The type Model is defined in the imported file Def_KeskinZeevi_IncumbentLowerBound_Model, whose code is not shown here. Nothing in this statement constrains MMM further. In particular, it imposes no relation between lll and uuu and no sign condition on σ\sigmaσ, beyond whatever the definition of Model itself enforces.

The statement asserts that there is a real number ccc with

c>0c > 0c>0

such that the following holds. The number ccc is chosen after MMM and before everything below, so it may depend on MMM only.

For every measurable space Ω\OmegaΩ, every probability measure PPP on Ω\OmegaΩ, and every real-valued process

ε:N→(Ω→R),t↦εt,\varepsilon : \mathbb{N} \to (\Omega \to \mathbb{R}), \qquad t \mapsto \varepsilon_t,ε:N→(Ω→R),t↦εt​,

suppose the hypothesis GaussianNoise(σ,P,ε)\mathrm{GaussianNoise}(\sigma, P, \varepsilon)GaussianNoise(σ,P,ε) holds. This predicate comes from the imported file Def_RobustBooking_Shared_GaussianNoise, whose code is not shown here. The statement uses it only as an assumption relating σ\sigmaσ, PPP and the sequence (εt)t∈N(\varepsilon_t)_{t \in \mathbb{N}}(εt​)t∈N​. No measurability, independence or distributional property of ε\varepsilonε is assumed beyond what that predicate contains.

Then, for every policy π\piπ and every natural number TTT with T≥3T \ge 3T≥3,

c⋅ln⁡T  ≤  RM(P,ε,π,T),c \cdot \ln T \;\le\; \mathcal{R}_M(P, \varepsilon, \pi, T),c⋅lnT≤RM​(P,ε,π,T),

where:

  • π\piπ ranges over the bundle's type Policy(l,u)\mathrm{Policy}(l, u)Policy(l,u), defined in Def_KeskinZeevi_IncumbentLowerBound_Policy;
  • ln⁡\lnln is the natural logarithm of TTT, viewed as a real number;
  • RM(P,ε,π,T)\mathcal{R}_M(P, \varepsilon, \pi, T)RM​(P,ε,π,T) is the real number worstRegret M P ε π T, defined in Def_KeskinZeevi_IncumbentLowerBound_Regret.

The definitions of Policy\mathrm{Policy}Policy and RM\mathcal{R}_MRM​ are not shown, so what this real number measures cannot be read off from the code given. The accompanying doc comment describes R\mathcal{R}R as a worst-case regret over a parameter set and ccc as depending on specific model quantities, but that comment is not part of the formal assertion.

The constant ccc is uniform across three things:

  • every probability space and every noise process satisfying the hypothesis;
  • every policy;
  • every horizon T≥3T \ge 3T≥3.

The statement does not claim that ccc is finite in any sense beyond being a real number, nor that it is computable or given by any formula.

Degenerate cases.

  • Probability space. Because PPP is a probability measure, Ω\OmegaΩ must be nonempty. A one-point Ω\OmegaΩ is allowed whenever GaussianNoise(σ,P,ε)\mathrm{GaussianNoise}(\sigma, P, \varepsilon)GaussianNoise(σ,P,ε) can hold there.
  • Unsatisfiable noise hypothesis. If GaussianNoise(σ,P,ε)\mathrm{GaussianNoise}(\sigma, P, \varepsilon)GaussianNoise(σ,P,ε) can never hold for this MMM, for example because of a degenerate σ\sigmaσ, the inner claim is vacuous. The whole statement then holds with any c>0c > 0c>0.
  • Empty policy type. If Policy(l,u)\mathrm{Policy}(l, u)Policy(l,u) is empty, for instance for some relation between lll and uuu, the claim is likewise vacuous.
  • Small horizons. The horizons T=0,1,2T = 0, 1, 2T=0,1,2 are excluded. For T≥3T \ge 3T≥3 we have ln⁡T≥ln⁡3>0\ln T \ge \ln 3 > 0lnT≥ln3>0, so the left side is strictly positive. The statement therefore forces RM(P,ε,π,T)>0\mathcal{R}_M(P, \varepsilon, \pi, T) > 0RM​(P,ε,π,T)>0 for every admitted P,ε,π,TP, \varepsilon, \pi, TP,ε,π,T.
  • Junk values in the regret. Suppose RM\mathcal{R}_MRM​ is internally a supremum over an empty or unbounded set, where the real-valued supremum returns the default 000. Or suppose it is an expectation of a non-integrable function, where the integral returns 000. In either case the statement would require 0≥cln⁡T>00 \ge c \ln T > 00≥clnT>0, which is impossible. So the theorem can only hold if, for every admitted case, RM\mathcal{R}_MRM​ is a genuine value bounded below by cln⁡Tc \ln TclnT.

Whether such junk values can arise depends on definitions not visible here.

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