Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 7.1 — One factor per side

Proved
SecondBestTrade.HalfEfficiency.one_factor_per_side

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

algorithmic-game-theorymechanism-designp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1

Fix a useful dual and nonnegative shared clock values θB,θS\theta_B,\theta_SθB​,θS​. Start agents independently from the product prior and run their chains with independent randomness conditional on these clocks. Each buyer's terminal law is fieθBQif_i e^{\theta_B Q_i}fi​eθB​Qi​ and each seller's is gjeθSQjg_j e^{\theta_S Q_j}gj​eθS​Qj​. Then

E[H~(v^,c^)∣θB,θS]≤eκ(θB+θS)Eπ[H~(v,c)].\mathbb E[\widetilde H(\widehat v,\widehat c)\mid\theta_B,\theta_S]\le e^{\kappa(\theta_B+\theta_S)}\mathbb E_\pi[\widetilde H(v,c)].E[H(v,c)∣θB​,θS​]≤eκ(θB​+θS​)Eπ​[H(v,c)].

The bound holds for every market in the full downward-closed model and incurs one density factor per side, independently of the number of buyers and sellers.

Differences from the source:

  • encoding: finite agent, trade and support sets with product-prior expectations → Fin labels, an injective nonnegative-vector support embedding, and finite product-weighted sums; reason: bijections cover every finite source market, and summing an overwritten own coordinate multiplies by its total probability one
  • encoding: conditional expected virtual surplus under shared clocks → the finite sum under the fixed-clock product of terminal laws, for every nonnegative clock pair; reason: conditioning leaves independent agent transitions and independent initial priors; the finite product sum is exactly that conditional law
Preamble
import Mathlib
import Definitions.Def_SecondBestTrade_HalfEfficiency_Dual

open scoped BigOperators NNReal
open MeasureTheory
set_option autoImplicit false
noncomputable section
Formal statement
namespace SecondBestTrade.HalfEfficiency

/-- Lemma 7.1, printed p. 13 (PDF p. 14). Conditional expectation is the fixed-clock finite product sum. -/
theorem one_factor_per_side (N : Market) (z : Dual N) (hz : useful N z)
    (thetaB thetaS : ℝ) (hB : 0 ≤ thetaB) (hS : 0 ≤ thetaS) :
    conditionalSurplus N z thetaB thetaS ≤
      Real.exp (kappa (z.tau : ℝ) * (thetaB + thetaS)) * expect N (Hvirtual N z) := by sorry

end SecondBestTrade.HalfEfficiency
Source
Dirk Bergemann, Yang Cai, Kangning Wang, Jinzhao Wu, Renzhe Xu, STOC 2027 submission #529 (October 2026), Lemma 7.1 — One factor per side, printed p. 13 (PDF p. 14)
Human review
  • Endorsed by Shuze Chen · Nov 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Nov 8, 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