Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 4 — Step 2 revenue; equation (29)

Disproved
CloseGaps.DPA.lemma_4

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

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

Lemma 4. E[∑{i=1}^{N^u} ∑{j=1}^{κ_i^u} p_{i,j}^u Y_{ij}^u I(⋃{l=i}^{N^u+1} B_l) I(A_1)] ≥ ∑{i=1}^{N^u} nτ_i^u p^D λ(p^D) P(⋃_{l=i}^{N^u+1} B_i) − Cnτ_1^u log n. (29)

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.
  • 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 lemma_4 (c : Coefficients) (hc : c.Positive) (x : ℝ) (hx : 0 < x) :
    ∃ C : ℝ, 0 < C ∧
    ∀ a : Market, a.Valid → a.hi - a.lo = 1 →
    ∃ π : ℝ → PriceRule, ∀ n : ℝ, 3 ≤ n →
    ∀ lam : ℝ → ℝ, InClass c a x 1 lam →
    ∃ N : StageCounts, Experiment a lam n x (π n) N ∧
      (∑ i ∈ Finset.Icc 1 N.Nu,
        n * tauU n i * dOpt a x 1 lam * lam (dOpt a x 1 lam) *
          probability (⋃ (_l : ℕ) (_h : _l ∈ Icc i (N.Nu + 1)), B a lam n x N i)) -
        C * n * tauU n 1 * Real.log n ≤ ∫ E, revenue4 a lam n x N E ∂clockLaw := by sorry

end CloseGaps.DPA
Source
Wang, Deng, and Ye (2014), Operations Research 62(2), 318–331, DOI 10.1287/opre.2013.1245, Lemma 4, p. 325 (PDF 8)
Read-back

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

Statement. For all coefficients ccc with M,K,mL,mU>0M,K,m_L,m_U>0M,K,mL​,mU​>0, and every x>0x>0x>0, there is a constant C>0C>0C>0 such that:

for every market aaa with alo<ahia_{\mathrm{lo}}<a_{\mathrm{hi}}alo​<ahi​ and ahi−alo=1a_{\mathrm{hi}}-a_{\mathrm{lo}}=1ahi​−alo​=1, there is a family of price rules (πn)(\pi_n)(πn​), chosen before nnn and λ\lambdaλ, such that for every real n≥3n\ge3n≥3 and every λ\lambdaλ with InClass(c,a,x,1,λ)(c,a,x,1,\lambda)(c,a,x,1,λ), there exist N=(Nu,Nc)N=(N_u,N_c)N=(Nu​,Nc​) with Experiment(a,λ,n,x,πn,N)(a,\lambda,n,x,\pi_n,N)(a,λ,n,x,πn​,N) and

∑i=1Nun τiU(n) d λ(d)  P(⋃l∈[i, Nu+1]Bi)  −  C n τ1U(n)ln⁡n  ≤  ∫R4 dP.\sum_{i=1}^{N_u} n\,\tau^U_i(n)\,d\,\lambda(d)\;\mathbb{P}\Big(\bigcup_{l\in[i,\,N_u+1]}B_i\Big)\;-\;C\,n\,\tau^U_1(n)\ln n\;\le\;\int R_4\,d\mathbb{P}.i=1∑Nu​​nτiU​(n)dλ(d)P(l∈[i,Nu​+1]⋃​Bi​)−Cnτ1U​(n)lnn≤∫R4​dP.

Terms.

  • d=d∗=max⁡(u∗,c∗)d=d^*=\max(u^*,c^*)d=d∗=max(u∗,c∗), where:
    • u∗u^*u∗ is the supremum of the maximizers of pλ(p)p\lambda(p)pλ(p) on I=[alo,ahi]I=[a_{\mathrm{lo}},a_{\mathrm{hi}}]I=[alo​,ahi​];
    • c∗c^*c∗ is the supremum of the minimizers of ∣λ(p)−x∣|\lambda(p)-x|∣λ(p)−x∣;
    • each is 000 if empty.
  • τ1U(n)=n−1/2(ln⁡n)7/2\tau^U_1(n)=n^{-1/2}(\ln n)^{7/2}τ1U​(n)=n−1/2(lnn)7/2 and τiU(n)=n−12(3/5)i−1(ln⁡n)5\tau^U_i(n)=n^{-\frac12(3/5)^{i-1}}(\ln n)^5τiU​(n)=n−21​(3/5)i−1(lnn)5 for i≥2i\ge2i≥2.
  • Bi={E:ℓ(E)=i}B_i=\{E:\ell(E)=i\}Bi​={E:ℓ(E)=i}, where ℓ\ellℓ is the switch index. The set inside the union is BiB_iBi​ for every lll (the index of BBB is iii, not lll). Since [i,Nu+1][i,N_u+1][i,Nu​+1] is nonempty for i≤Nui\le N_ui≤Nu​, the probability is P(Bi)=P(ℓ=i)\mathbb{P}(B_i)=\mathbb{P}(\ell=i)P(Bi​)=P(ℓ=i).
  • P\mathbb{P}P is the infinite product of rate-1 exponential laws on noise EEE.

R4R_4R4​.

R4(E)=∑i=1Nu∑j<kipi,j yi,j  1[ℓ(E)≥i]  1[E∈A1],R_4(E)=\sum_{i=1}^{N_u}\sum_{j<k_i}p_{i,j}\,y_{i,j}\;\mathbf 1[\ell(E)\ge i]\;\mathbf 1[E\in A_1],R4​(E)=i=1∑Nu​​j<ki​∑​pi,j​yi,j​1[ℓ(E)≥i]1[E∈A1​],

where kik_iki​, pi,jp_{i,j}pi,j​ and yi,jy_{i,j}yi,j​ are the size, grid points and counts of u-stage iii, or zeros if it is missing.

A1A_1A1​ is A0A_0A0​ intersected with {∑i=1Nu∑j<kiyi,j<nx}\{\sum_{i=1}^{N_u}\sum_{j<k_i}y_{i,j}<nx\}{∑i=1Nu​​∑j<ki​​yi,j​<nx}, with the sum running over all NuN_uNu​ u-stages. A0A_0A0​ requires:

  • on {ℓ=Nu+1}\{\ell=N_u+1\}{ℓ=Nu​+1}: ddd in the intervals of u-stages 1..Nu1..N_u1..Nu​;
  • on {ℓ≤Nu}\{\ell\le N_u\}{ℓ≤Nu​}: u∗≤c∗u^*\le c^*u∗≤c∗, ddd in the intervals of u-stages 1..ℓ1..\ell1..ℓ, and ddd in the intervals of c-stages 1..Nc1..N_c1..Nc​ of branch ℓ\ellℓ.

A missing stage gives [0,0][0,0][0,0].

Stages. A stage on an interval with duration τ\tauτ and size κ\kappaκ exists only if all hold:

  • κ\kappaκ is exactly a positive integer kkk;
  • τ>0\tau>0τ>0;
  • the interval is ordered;
  • λ≥0\lambda\ge0λ≥0 on its grid pj=lo+j(hi−lo)/kp_j=\mathrm{lo}+j(\mathrm{hi}-\mathrm{lo})/kpj​=lo+j(hi−lo)/k.

The counts yjy_jyj​ are truncated increments of an imported counting process driven by EEE, along clock times advancing by nλ(pj)τ/kn\lambda(p_j)\tau/knλ(pj​)τ/k. The u-stages and c-branches shrink around the selected points, and the switch index ℓ\ellℓ is the first u-stage whose c-selected point exceeds its u-selected point by more than 2ln⁡n2\sqrt{\ln n}2lnn​ gaps, or Nu+1N_u+1Nu​+1.

Experiment requires all of:

  1. At horizon 111, both of:
    • almost surely, the complete trace holds;
    • almost surely, while πn\pi_nπn​'s sales process (thresholds EjE_jEj​, cap ⌊nx⌋+\lfloor nx\rfloor_+⌊nx⌋+​) has fewer than ⌊nx⌋+\lfloor nx\rfloor_+⌊nx⌋+​ sales strictly before t∈[0,1)t\in[0,1)t∈[0,1), its posted price is a real price, given by the stage schedule: an experimental grid point in the current subinterval, or the final posting.
  2. Almost surely, all of:
    • Nu≥1N_u\ge1Nu​≥1 and Nc≥1N_c\ge1Nc​≥1 are exactly the first u- and c-stopping indices (gap2ln⁡n<τ1U^2\sqrt{\ln n}<\tau^U_12lnn​<τ1U​, respectively gapln⁡n<τ1C\sqrt{\ln n}<\tau^C_1lnn​<τ1C​), with all stages up to them existing on every branch l≤Nul\le N_ul≤Nu​;
    • 1−TNuU≥01-T^U_{N_u}\ge01−TNu​U​≥0;
    • 1−TlU−TNcC≥01-T^U_l-T^C_{N_c}\ge01−TlU​−TNc​C​≥0 for l∈[1,Nu]l\in[1,N_u]l∈[1,Nu​];
    • λ(p~)≥0\lambda(\tilde p)\ge0λ(p~​)≥0 on BNu+1B_{N_u+1}BNu​+1​.
  3. A0A_0A0​, A1A_1A1​, A2A_2A2​ and every BiB_iBi​ are measurable.
  4. R4R_4R4​, R5R_5R5​, R6R_6R6​ and R7,lR_{7,l}R7,l​ are integrable.

Degenerate cases.

  • If mL<mUm_L<m_UmL​<mU​, the inner statement is vacuous.
  • Experiment, for every n≥3n\ge3n≥3, requires the sizes κiU(n)\kappa^U_i(n)κiU​(n) and κiC(n)\kappa^C_i(n)κiC​(n) of the needed stages to be exact positive integers. For example, at n=3n=3n=3, 31/10ln⁡3≈1.2263^{1/10}\ln3\approx1.22631/10ln3≈1.226 must be an integer.
  • If nx≤0nx\le0nx≤0, A1A_1A1​ is empty, but nx>0nx>0nx>0 here.
  • If P(Bi)=0\mathbb{P}(B_i)=0P(Bi​)=0 for all i≤Nui\le N_ui≤Nu​, the left side is −Cnτ1U(n)ln⁡n-Cn\tau^U_1(n)\ln n−Cnτ1U​(n)lnn.
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