Lemma 4.18 — with t̲ ≤ t̄, some refinement of the submarket has Strat ≥ (3/512) OneTrade(𝓑, 𝓢)
ProvedStratifyMarkets.DoubleAuction.lemma_4_18double-auctiongains-from-trademarket-stratificationp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Fix a double auction instance, a submarket (), a buyer threshold and a seller threshold of the submarket with . There is a refinement of — consecutive submarkets (), a price in each, and the worst-rationed rule in each (Remark 4.19) — whose gains satisfy
The constant is .
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: a refinement of [m̲, m̄] (Remark 4.19) → a
Stratificationσ with σ.m 0 = a and σ.m (Fin.last σ.N) = b; Strat =I.strat σ; reason: a refinement is exactly a partition of [a, b] into consecutive submarkets with a price in each - 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.18 (p. 44): inside a submarket `[a, b]` with thresholds `t̲ ≤ t̄`, some refinement of
`[a, b]` (Remark 4.19: consecutive submarkets `a = r₀ < r₁ < ⋯ < r_K = b`, a price in each, the
worst-rationed rule in each) has `Strat ≥ (3/512) OneTrade(𝓑, 𝓢)`. -/
theorem lemma_4_18 {n m : ℕ} (I : DAInstance n m) (a b tB tS : ℝ)
(ha : 0 ≤ a) (hab : a < b) (hb : b ≤ 1)
(htB : I.IsBuyerThreshold a b tB) (htS : I.IsSellerThreshold a b tS) (hle : tS ≤ tB) :
∃ σ : Stratification, σ.m 0 = a ∧ σ.m (Fin.last σ.N) = b ∧
3 / 512 * I.oneTrade a b tB tS ≤ I.strat σ := by sorry
end StratifyMarkets.DoubleAuction
Source
Deng, Lin, Schoepflin, Wang, Stratifying Markets for Efficient Trade, STOC 2027 submission (manuscript sha256 49372bcf…), p. 44, Lemma 4.18 (proof pp. 44–47; Remark 4.19)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.