Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 4.17 — with t̲ ≤ t̄ and a price q ∈ [t̲, t̄] with E[A], E[T] ≤ 1/4, WorstRationed(q) ≥ (3/128) OneTrade(𝓑, 𝓢)

Proved
StratifyMarkets.DoubleAuction.lemma_4_17

by Shuze Chen · Nov 11, 2026 · Mathlib 0df444a (Lean v4.33.1)

double-auctiongains-from-trademarket-stratificationp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1

Fix a double auction instance, a submarket [a,b][a,b][a,b] (0≤a<b≤10\le a<b\le10≤a<b≤1), a buyer threshold tˉ\bar ttˉ and a seller threshold t‾\underline tt​ of the submarket with t‾≤tˉ\underline t\le\bar tt​≤tˉ, and a price q∈[t‾,tˉ]q\in[\underline t,\bar t]q∈[t​,tˉ]. Let AAA be the number of buyers with values in [q,tˉ][q,\bar t][q,tˉ] and TTT the number of sellers with costs in [t‾,q][\underline t,q][t​,q]. If Ev[A]≤1/4\mathbb E_{\mathbf v}[A]\le1/4Ev​[A]≤1/4 and Ec[T]≤1/4\mathbb E_{\mathbf c}[T]\le1/4Ec​[T]≤1/4, then

WorstRationed(a,q,b)≥3128 OneTrade(B,S).\mathrm{WorstRationed}(a,q,b)\ge\frac3{128}\,\mathrm{OneTrade}(\mathcal B,\mathcal S).WorstRationed(a,q,b)≥1283​OneTrade(B,S).

The constant is 23⋅9256\frac23\cdot\frac9{256}32​⋅2569​.

Differences from the source:

  • encoding: continuous F_1..F_n, G_1..G_m supported on [0, 1], all values and costs mutually independent → a DAInstance n m: no-atom probability measures with mass 1 on [0, 1]; expectations over the product (Measure.pi μB).prod (Measure.pi μS); reason: same instances; independence is the product measure
  • encoding: a submarket [m̲, m̄] (footnote 3) → reals a, b with 0 ≤ a < b ≤ 1; counts within the submarket are sums of Pr[lo ≤ v_i ≤ hi] / Pr[lo ≤ c_j ≤ hi] over closed intervals (E_v[A] = Σ_i Pr[q ≤ v_i ≤ t̄], E_c[T] = Σ_j Pr[t̲ ≤ c_j ≤ q]); reason: footnote 3's convention; closed intervals as in Remark 2.4; this lemma has no price p of its own
  • encoding: the buyer threshold t̄ and seller threshold t̲ of the submarket → arbitrary tB, tS ∈ [a, b] with Σ_i Pr[tB ≤ v_i ≤ b] = 1/4 and Σ_j Pr[a ≤ c_j ≤ tS] = 1/4; reason: the thresholds need not be unique; quantifying over all of them is at least as strong as fixing one
  • encoding: OneTrade(𝓑, 𝓢) = E[Σ_{i∈𝓑, j∈𝓢}(v_i − c_j) | B = 1 and S = 1] → E[Σ_{i∈𝓑, j∈𝓢}(v_i − c_j) · 1{B = 1, S = 1}] / Pr[B = 1 and S = 1]; reason: elementary conditional expectation; the denominator is at least 9/256 > 0 under the hypotheses, (4.21)
  • encoding: 'if there exists a price q between t̲ and t̄ such that E_v[A] ≤ 1/4 and E_c[T] ≤ 1/4, then WorstRationed(q) ≥ …' → for every q with t̲ ≤ q ≤ t̄, Σ_i Pr[q ≤ v_i ≤ t̄] ≤ 1/4 and Σ_j Pr[t̲ ≤ c_j ≤ q] ≤ 1/4 imply the bound at that q; reason: the conclusion is about the q of the hypothesis
  • generalization: §4.2.1–4.2.2 (pp. 38, 40): the expected number of buyers and the expected number of sellers in the submarket are both greater than 1/4, which makes t̄ and t̲ well defined → no such hypothesis; the threshold equations (IsBuyerThreshold, IsSellerThreshold) are hypotheses, which imply both counts are at least 1/4, so the boundary instances with a count exactly 1/4 are also covered; reason: on every instance the source allows the statement is the source's; the condition serves only to make the thresholds exist, and the proofs (pp. 40–47) use only E_v[B] = E_c[S] = 1/4 and the order of t̄, t̲
Preamble
import Mathlib
import Definitions.Def_StratifyMarkets_DoubleAuction_Instance
import Definitions.Def_StratifyMarkets_DoubleAuction_WorstRationed
import Definitions.Def_StratifyMarkets_DoubleAuction_Submarket

open MeasureTheory
Formal statement
namespace StratifyMarkets.DoubleAuction

/-- Lemma 4.17 (p. 42): inside a submarket `[a, b]` with thresholds `t̲ ≤ t̄`, if a price
`q ∈ [t̲, t̄]` has `E_𝐯[A] ≤ 1/4` (buyers with values in `[q, t̄]`) and `E_𝐜[T] ≤ 1/4` (sellers with
costs in `[t̲, q]`), then `WorstRationed(a, q, b) ≥ (3/128) OneTrade(𝓑, 𝓢)`. -/
theorem lemma_4_17 {n m : ℕ} (I : DAInstance n m) (a b tB tS q : ℝ)
    (ha : 0 ≤ a) (hab : a < b) (hb : b ≤ 1)
    (htB : I.IsBuyerThreshold a b tB) (htS : I.IsSellerThreshold a b tS) (hle : tS ≤ tB)
    (hq1 : tS ≤ q) (hq2 : q ≤ tB)
    (hA : I.expBuyersIn q tB ≤ 1 / 4) (hT : I.expSellersIn tS q ≤ 1 / 4) :
    3 / 128 * I.oneTrade a b tB tS ≤ I.worstRationedIn a q b := by sorry

end StratifyMarkets.DoubleAuction
Source
Deng, Lin, Schoepflin, Wang, Stratifying Markets for Efficient Trade, STOC 2027 submission (manuscript sha256 49372bcf…), p. 42, Lemma 4.17
Human review
  • Endorsed by Community (Bot) · Nov 11, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Shuze Chen · Nov 11, 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