Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.4 — a bounded α-strongly regular law with DET=cαOPT=cαAPRev\mathrm{DET}=c_\alpha\mathrm{OPT}=c_\alpha\mathrm{APRev}DET=cα​OPT=cα​APRev

Open
LotteryInterm.IID.Supplement.theorem_4_4

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

auction-theorymechanism-designp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1

Consider a single bidder.

  1. For every 0<α<10<\alpha<10<α<1 and every
H>max⁡{1+αα2, [(1−α)α1+α]−1/α}H>\max\Big\{\frac{1+\alpha}{\alpha^2},\ \big[(1-\alpha)\alpha^{1+\alpha}\big]^{-1/\alpha}\Big\}H>max{α21+α​, [(1−α)α1+α]−1/α}

there is a bounded α-strongly regular value law FFF whose support ends at the terminal point HHH such that

DET(F)=cα OPT(F)=cα APRev(F),\mathrm{DET}(F)=c_\alpha\,\mathrm{OPT}(F)=c_\alpha\,\mathrm{APRev}(F),DET(F)=cα​OPT(F)=cα​APRev(F),

and no tie-breaking rescues the seller: for every posted price p≥0p\ge0p≥0, every revenue-maximizing intermediary mechanism and every utility-maximizing option choice of the bidder, the seller's revenue is at most cα OPT(F)c_\alpha\,\mathrm{OPT}(F)cα​OPT(F). 2. For α=1\alpha=1α=1 and every H>4H>4H>4 the same holds with an MHR law ending at HHH and c1=1/ec_1=1/ec1​=1/e.

Here DET(F)\mathrm{DET}(F)DET(F) is the best revenue of a seller posting a price against a revenue-maximizing intermediary, with ties resolved against the seller (Assumptions 3.2/3.3). Both equalities are exact. With Theorem 4.2, this shows that cαc_\alphacα​ cannot be improved for deterministic sellers.

Differences from the source:

  • reading: a bounded distribution F_{alpha,H} → a ValueDist F with F.hi = H (terminal point H); reason: the subscript H is the truncation point of the witness in (1) and (2); the Lean witness is the more specific one
  • encoding: a single bidder → the one-bidder profile fun _ : Fin 1 => F; reason: same auction
  • generalization: DET(F_{alpha,H}) = c_alpha OPT, with the proof letting the bidder and the intermediary tie-break in favour of the seller → the published DET (worst case over intermediary best responses, lowest-payment bidder choice) equals c_alpha OPT, and in addition for every posted price p, every intermediary best response and every utility-maximizing option choice the seller earns at most c_alpha OPT; reason: a stronger conclusion: the source's DET is attained under either tie-breaking convention, so the statement covers the paper's standing Assumptions 3.2/3.3 and the proof's seller-favourable tie-breaking at once; dropping the extra conjunct gives the worst-case reading
  • encoding: the two cases (0 < alpha < 1; alpha = 1 and H > 4) → two conjuncts; reason: same statement
  • encoding: independent nonnegative bidder values and expected revenues → Fin n, product probability measures, EReal optima, and measurable mechanisms with integrable payments and all report sections; reason: these represent the same stochastic auction; unbounded optima and undefined real integrals cannot default to zero
  • encoding: Bayesian incentive compatibility and interim individual rationality → truthful inequalities for almost every original value against every real report; reason: null types do not affect revenue; reports outside the support extend the mechanism without changing its attainable revenues
  • encoding: alpha-strongly regular: phi(y) - phi(x) >= alpha (y - x) for all a <= x <= y <= b (Definition A.2) → StronglyRegular alpha D on the published ValueDist, asked for lo < x <= y <= hi; reason: the same set as the published Regular; the lowest point a is a null type whose density may vanish, and alpha = 0 gives exactly Regular
Preamble
import Definitions.Def_LotteryInterm_IID_Supplement_StrongRegularity
import Definitions.Def_LotteryInterm_IID_Supplement_GeneralMenu

open MeasureTheory
Formal statement
namespace LotteryInterm.IID.Supplement

/-- Theorem 4.4: tightness of `c_α`. For `0 < α < 1` and `H` above the threshold (or
`α = 1` and `H > 4`) some bounded α-strongly regular law with terminal point `H` gives
a single bidder `DET = c_α · OPT = c_α · APRev`, both equalities exact; moreover no
tie-breaking helps the seller: for every posted price, every intermediary best response
and every utility-maximizing option choice, the seller earns at most `c_α · OPT`. -/
theorem theorem_4_4 :
    (∀ α H : ℝ, 0 < α → α < 1 →
      max ((1 + α) / α ^ 2) (((1 - α) * α ^ (1 + α)) ^ (-1 / α)) < H →
      ∃ F : ValueDist, F.hi = (H : WithTop ℝ) ∧ StronglyRegular α F ∧
        DET (fun _ : Fin 1 => F) = ((cAlpha α : ℝ) : EReal) * OPT (fun _ : Fin 1 => F) ∧
        ((cAlpha α : ℝ) : EReal) * OPT (fun _ : Fin 1 => F) =
          ((cAlpha α : ℝ) : EReal) * APRev (fun _ : Fin 1 => F) ∧
        ∀ (p : ℝ) (hp : 0 ≤ p) (σ : ℝ → ℝ × ℝ),
          IsUtilityMaximizing (GenMenu.ofMenu (postedPrice p hp)) σ →
          ∀ I : Mechanism 1, BestResponse (fun _ : Fin 1 => F) (postedPrice p hp) I →
            ((genSellerRevenue (fun _ : Fin 1 => F) σ I : ℝ) : EReal) ≤
              ((cAlpha α : ℝ) : EReal) * OPT (fun _ : Fin 1 => F)) ∧
    (∀ H : ℝ, 4 < H →
      ∃ F : ValueDist, F.hi = (H : WithTop ℝ) ∧ StronglyRegular 1 F ∧
        DET (fun _ : Fin 1 => F) = ((cAlpha 1 : ℝ) : EReal) * OPT (fun _ : Fin 1 => F) ∧
        ((cAlpha 1 : ℝ) : EReal) * OPT (fun _ : Fin 1 => F) =
          ((cAlpha 1 : ℝ) : EReal) * APRev (fun _ : Fin 1 => F) ∧
        ∀ (p : ℝ) (hp : 0 ≤ p) (σ : ℝ → ℝ × ℝ),
          IsUtilityMaximizing (GenMenu.ofMenu (postedPrice p hp)) σ →
          ∀ I : Mechanism 1, BestResponse (fun _ : Fin 1 => F) (postedPrice p hp) I →
            ((genSellerRevenue (fun _ : Fin 1 => F) σ I : ℝ) : EReal) ≤
              ((cAlpha 1 : ℝ) : EReal) * OPT (fun _ : Fin 1 => F)) := by sorry

end LotteryInterm.IID.Supplement
Source
Jingyi Liu, Aviad Rubinstein, Ertem Nusret Tas, Matt Weinberg, Qianfan Zhang, STOC 2027 submission #623 (October 2026), Theorem 4.4, p.12 (PDF p.13); proof pp.12–14 (PDF pp.13–15); https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/623.pdf

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