Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1 — Uniform near-optimal regret for DPA

Disproved
CloseGaps.DPA.theorem_1

by Shuze Chen · Oct 29, 2026 · Mathlib 0df444a (Lean v4.33.1)

dpap2o-gran-per-chapterp2o-plan-paperp2o-v1

Theorem 1. Let Assumption 1 hold for Γ = Γ(M, K, m_L, m_U). Then there exists an admissible policy π generated by Algorithm DPA, such that for all n ≥ 1,

sup_{λ∈Γ} R_n^π(x,T;λ) ≤ C(log n)^{4.5}/√n

for some constant C.

Differences from the source:

  • encoding: Continuous-time controlled Poisson sales with an off action. → A measurable price rule on sale histories, exponential interarrivals and Option-valued actions.; reason: The off action has zero intensity and revenue; the history rule cannot access the unknown demand.
  • reading: The size parameter n is written without an integrality restriction. → n is real.; reason: This retains the displayed domain, including every integer size.
  • encoding: The DPA objects are constructed by the displayed algorithm. → Partial stage construction and successful construction in the conclusion.; reason: Definedness is asserted in the conclusion at the source sizes: every printed real grid count must be an exact positive integer, each stage duration positive, and each stopping minimum attained; no rounding or restriction to executable sizes is introduced.
  • encoding: A supremum of regrets over the demand class. → The same C bounds the regret for every member of the full class.; reason: Pointwise uniform comparison avoids empty or unbounded real-supremum defaults.
  • encoding: General T and feasible price interval. → Multiplicative price and time normalization in the algorithm, with the physical fluid benchmark.; reason: Multiplication preserves revenue ordering; C remains outside the price-interval quantifier.
  • encoding: Inventory sales are integral and at most nx. → The stochastic sale cap is floor(nx); the fluid inventory remains nx.; reason: These are the same unit-sales constraint, without restricting real initial inventory.
  • reading: Stage counts appear as fixed summation limits and deterministic factors outside expectations in section 5, although the interval widths are random. → A common pair of deterministic counts satisfies the actual stopping tests almost surely on the constructed virtual traces.; reason: This is the literal fixed-count reading of the printed formulas; nominal-width equalities are not assumed, and successful construction is asserted in the conclusion.
  • encoding: Grid prices have indices j=1,...,κ_i. → Grid indices are j=0,...,k-1, with price lo+j(hi-lo)/k.; reason: The same left endpoints are enumerated; only the index origin changes.
  • reading: The empirical argmax and argmin do not specify a tie rule. → Choose the least grid index attaining each finite optimum.; reason: This fixes an observable deterministic selection from the source argmax or argmin, without demand information.
  • reading: The base-instance estimator is count/Δ and its inventory target is x/T. → For the size-n normalized instance, estimate base demand by count/(nΔ) and compare with x.; reason: Instantiating the pseudocode with inventory nx and dividing its rate estimate and target by n gives this rule; normalized time has horizon one.
Preamble
import Definitions.Def_CloseGaps_DPA_RevenueEvents

open MeasureTheory Set

open scoped Classical
Formal statement
namespace CloseGaps.DPA

theorem theorem_1 (c : Coefficients) (hc : c.Positive)
    (x T : ℝ) (hx : 0 < x) (hT : 0 < T) :
    ∃ C : ℝ, 0 < C ∧ ∀ a : Market, a.Valid →
      ∃ π : ℝ → PriceRule, ∀ n : ℝ, 1 ≤ n →
        ∀ lam : ℝ → ℝ, InClass c a x T lam →
          (∃ N : StageCounts, generated a lam n x T (π n) N) ∧
          admissible a lam n x T (π n) ∧
          (fluidRevenues a x T lam).Nonempty ∧ BddAbove (fluidRevenues a x T lam) ∧
          0 < fluidValue a x T lam ∧
          1 - expectedRevenue (π n) lam n x T / (n * fluidValue a x T lam) ≤
            C * (Real.log n) ^ (9 / 2 : ℝ) / Real.sqrt n := by sorry

end CloseGaps.DPA
Source
Wang, Deng, and Ye (2014), Operations Research 62(2), 318–331, DOI 10.1287/opre.2013.1245, Theorem 1, p. 322 (PDF 5)
Read-back

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

For a coefficient object ccc (of type Coefficients) that satisfies the predicate c.Positive, and for real numbers x>0x > 0x>0 and T>0T > 0T>0, the statement asserts the following.

There is a real constant C>0C > 0C>0, depending only on ccc, xxx and TTT, with this property. For every market aaa (of type Market) that satisfies the predicate a.Valid, there is a family of price rules π=(πn)n∈R\pi = (\pi_n)_{n \in \mathbb{R}}π=(πn​)n∈R​. Each πn\pi_nπn​ is an object of type PriceRule, and the family is indexed by all real numbers nnn, not only by integers. The family may depend on aaa, ccc, xxx, TTT and CCC. It is chosen before any intensity function is fixed, so it may not depend on λ\lambdaλ.

The family must work as follows. For every real n≥1n \ge 1n≥1 and every function λ:R→R\lambda : \mathbb{R} \to \mathbb{R}λ:R→R satisfying InClass c a x T λ, all five of these hold at once:

  1. Generation. There is a stage-count object NNN (of type StageCounts) such that generated a λ n x T (π n) N holds.
  2. Admissibility. admissible a λ n x T (π n) holds.
  3. Fluid revenues. The set F(a,x,T,λ)\mathcal{F}(a, x, T, \lambda)F(a,x,T,λ) given by fluidRevenues a x T λ is a nonempty subset of R\mathbb{R}R and is bounded above.
  4. Fluid value. The real number V(a,x,T,λ)V(a, x, T, \lambda)V(a,x,T,λ) given by fluidValue a x T λ is strictly positive.
  5. Revenue gap. Write R(πn,λ,n,x,T)R(\pi_n, \lambda, n, x, T)R(πn​,λ,n,x,T) for the real number expectedRevenue (π n) λ n x T. Then
1−R(πn,λ,n,x,T)n V(a,x,T,λ)  ≤  C (log⁡n)9/2n,1 - \frac{R(\pi_n, \lambda, n, x, T)}{n \, V(a, x, T, \lambda)} \;\le\; \frac{C \, (\log n)^{9/2}}{\sqrt{n}},1−nV(a,x,T,λ)R(πn​,λ,n,x,T)​≤n​C(logn)9/2​,

where log⁡\loglog is the natural logarithm and (log⁡n)9/2(\log n)^{9/2}(logn)9/2 is a real power.

Undefined names. Coefficients, Positive, Market, Valid, PriceRule, StageCounts, InClass, generated, admissible, fluidRevenues, fluidValue and expectedRevenue all come from the imported module Definitions.Def_CloseGaps_DPA_RevenueEvents. That module was not provided, so this read-back cannot unfold them. What each one asserts or computes is outside what is described here. In particular, conclusions 1–4 are claims about those definitions, and their content depends entirely on how the definitions are written. Conclusions 3 and 4 (nonemptiness, boundedness above, positivity) are asserted as conclusions, not assumed as hypotheses.

Logical form. The gap bound is one-sided. If RRR exceeds nVnVnV, the left-hand side is negative and the inequality holds automatically. No lower bound on the gap and no upper bound on RRR is claimed. The constant CCC is uniform over all valid markets aaa, all real n≥1n \ge 1n≥1 and all admissible λ\lambdaλ. Only the price-rule family is allowed to depend on aaa.

Degenerate cases.

  • If no market satisfies a.Valid, everything after the choice of CCC is vacuous, and the statement reduces to the existence of some C>0C > 0C>0, which is trivially true.
  • For a given aaa and nnn, if no λ\lambdaλ satisfies InClass c a x T λ, then nothing is required of πn\pi_nπn​ for that pair.
  • If c.Positive can never hold, the whole statement is vacuous.
  • The denominator nVn VnV is strictly positive, because n≥1n \ge 1n≥1 and conclusion 4 asserts V>0V > 0V>0. So the junk value that division by zero would give never enters.
  • Because n≥1n \ge 1n≥1, log⁡n≥0\log n \ge 0logn≥0, so the real power (log⁡n)9/2(\log n)^{9/2}(logn)9/2 is the usual nonnegative value. Also n≥1\sqrt{n} \ge 1n​≥1, so neither the power nor the square root takes a junk value.
  • At n=1n = 1n=1, log⁡1=0\log 1 = 0log1=0, so the right-hand side is 000. The statement then requires R(π1,λ,1,x,T)≥V(a,x,T,λ)R(\pi_1, \lambda, 1, x, T) \ge V(a, x, T, \lambda)R(π1​,λ,1,x,T)≥V(a,x,T,λ) for every admissible λ\lambdaλ.
  • Non-integer nnn (for example n=1.5n = 1.5n=1.5) are included, with the same requirements.
  • Whether expectedRevenue or fluidValue can take a default value (for example an integral of a non-integrable function, or a supremum of an empty or unbounded set) depends on the unseen definitions. The statement only guarantees that F\mathcal{F}F is nonempty and bounded above, and that V>0V > 0V>0.
Human review
  • Endorsed by Community (Bot) · Oct 29, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Shuze Chen · Oct 29, 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