Lemma 3.5 — ordered fully tradable matchings with OrderedMatching ≥ SellerProfit/4 and with OrderedMatching ≥ BuyerProfit/4
ProvedStratifyMarkets.DoubleAuction.lemma_3_5bilateral-tradegains-from-trademarket-stratificationp2o-gran-per-chapterp2o-plan-paperp2o-v1
For every bilateral trade instance there is an ordered fully tradable matching with
and there is an ordered fully tradable matching with . Here SellerProfit and BuyerProfit are the expected profits of the seller-pricing and buyer-pricing mechanisms at profit-maximizing prices in . It is Step 2 of the bilateral argument.
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: SellerProfit(c) = (s_c − c) F̄(s_c) and BuyerProfit(v) = (v − b_v) G(b_v) at profit-maximizing prices → the suprema over s ∈ [0, 1] of (s − c) F̄(s) and over b ∈ [0, 1] of (v − b) G(b); reason: the maxima are attained (continuous functions on [0, 1]), so the values agree and no argmax selection is needed
- 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_Bilateral import Definitions.Def_StratifyMarkets_DoubleAuction_Stratification open MeasureTheory
Formal statement
namespace StratifyMarkets.DoubleAuction
/-- Lemma 3.5 (p. 20): for every bilateral trade instance there is an ordered fully tradable
matching with `OrderedMatching ≥ SellerProfit / 4`, and there is one with
`OrderedMatching ≥ BuyerProfit / 4`. -/
theorem lemma_3_5 (I : BTInstance) :
(∃ M : OrderedMatching, 1 / 4 * I.sellerProfit ≤ I.orderedMatching M) ∧
(∃ M : OrderedMatching, 1 / 4 * I.buyerProfit ≤ I.orderedMatching M) := by sorry
end StratifyMarkets.DoubleAuction
Source
Deng, Lin, Schoepflin, Wang, Stratifying Markets for Efficient Trade, STOC 2027 submission (manuscript sha256 49372bcf…), p. 20, Lemma 3.5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.