Theorem 4.1 — every double auction with independent values and costs admits a worst-rationed stratification with Strat ≥ FB/27843
ProvedStratifyMarkets.DoubleAuction.theorem_4_1double-auctiongains-from-trademarket-stratificationp2o-gran-per-chapterp2o-plan-paperp2o-v1
Consider any double auction instance: buyers and sellers (), buyer 's value and seller 's cost , all values and costs mutually independent, and every , a continuous distribution supported on (not necessarily identical). Then there is a market stratification , (), that applies the worst-rationed rule within each submarket at price and satisfies
where is the first-best gains from trade. This is the paper's main result; the constant comes from .
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: indices k = 1, …, N → 0-based
k : Fin N, submarket k is [m k.castSucc, m k.succ] with price p k; reason: relabelling only
Preamble
import Mathlib import Definitions.Def_StratifyMarkets_DoubleAuction_Instance import Definitions.Def_StratifyMarkets_DoubleAuction_WorstRationed open MeasureTheory
Formal statement
namespace StratifyMarkets.DoubleAuction
/-- Theorem 4.1 (p. 25): for every double auction instance (any `n` buyers and `m` sellers with
independent continuous values and costs on `[0, 1]`), some stratification that applies the
worst-rationed rule within each submarket satisfies `Strat ≥ FB / 27843`. -/
theorem theorem_4_1 {n m : ℕ} (I : DAInstance n m) :
∃ σ : Stratification, 1 / 27843 * I.FB ≤ I.strat σ := by sorry
end StratifyMarkets.DoubleAuction
Source
Deng, Lin, Schoepflin, Wang, Stratifying Markets for Efficient Trade, STOC 2027 submission (manuscript sha256 49372bcf…), p. 25, Theorem 4.1 (proof p. 49)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.