Lemma 3.2 — every ordered fully tradable matching converts into a stratification with at least one-third of its gains from trade
ProvedStratifyMarkets.DoubleAuction.lemma_3_2bilateral-tradegains-from-trademarket-stratificationp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a bilateral trade instance and let be an ordered fully tradable matching (Definition 2.6), with gains . Then there is a market stratification (Definition 2.3) whose bilateral gains from trade satisfy
This is Step 1 of the bilateral argument (Figure 3.1).
Differences from the source:
- encoding: F and G are continuous distributions supported on [0, 1], v and c independent → a
BTInstance: probability measures μB, μS with no atoms (NullSingletonClass) and mass 1 on [0, 1]; expectations over the productμS.prod μB; reason: a CDF is continuous exactly when its law has no atoms; same instances - 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 - encoding: the matching 'can be converted into a stratification that achieves at least one-third of its gains from trade' → ∃ σ : Stratification, OrderedMatching(M)/3 ≤ Strat(σ), for the same instance; reason: the conversion is the existence of such a stratification
Preamble
import Mathlib import Definitions.Def_StratifyMarkets_DoubleAuction_Bilateral import Definitions.Def_StratifyMarkets_DoubleAuction_Stratification open MeasureTheory
Formal statement
namespace StratifyMarkets.DoubleAuction
/-- Lemma 3.2 (p. 16): every ordered fully tradable matching can be converted into a stratification
that achieves at least one-third of its gains from trade. -/
theorem lemma_3_2 (I : BTInstance) (M : OrderedMatching) :
∃ σ : Stratification, I.orderedMatching M / 3 ≤ I.strat σ := by sorry
end StratifyMarkets.DoubleAuction
Source
Deng, Lin, Schoepflin, Wang, Stratifying Markets for Efficient Trade, STOC 2027 submission (manuscript sha256 49372bcf…), p. 16, Lemma 3.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.