Lemma 6.3 — crossed prices of two high-auxiliary-profit pairs are in , nearly optimal, with comparable trade probabilities
ProvedBilateralProfitRegular.lemma_6_3bilateral-tradeonline-learningp2o-gran-per-chapterp2o-plan-paperp2o-v1posted-pricesregret-boundsregular-distributions
Let . Suppose and in satisfy . Then:
- and ;
- each crossed pair satisfies
- the four trade probabilities are within a factor of of each other.
The lemma ensures that the crossed queries needed to estimate through eq. (42) are themselves cheap in regret.
Differences from the source:
- reading: "either crossed pair satisfies" → both crossed pairs satisfy the bound; reason: the proof (46) bounds each crossed pair; "either" means "each"
- reading: "the four trade probabilities are within a factor of 3 of each other" → for any two of the four pairs; reason: the proof shows
- encoding: independent regular seller and buyer distributions on with strictly positive densities (§2, §6) →
RegularUnit Efor a publishedEnvironmentE(supports ,E.Regular); , from the joint lawE.prior, =E.cdfS,E.cdfB; reason: the same class: Definitions 2.1–2.2 with the standing positivity of the densities; the valuation laws are the environment's
Preamble
import Mathlib import Definitions.Def_BilateralProfitRegular_Stochastic import Definitions.Def_BilateralProfitRegular_Auxiliary
Formal statement
namespace BilateralProfitRegular
open MechanismDesign.BilateralTrade
/-- **Lemma 6.3 (Crossed prices)**, Brüstle, di Gregorio, Fusco, Leonardi (manuscript, sha256
e91e8127…), p.38 (PDF 40). If `x = (p, q)` and `z = (u, v)` in `int(𝒯)` satisfy
`r_λ(x), r_λ(z) ≥ 0.99µ⋆`, then `(p, v)` and `(u, q)` belong to `𝒯`, either crossed pair `y`
satisfies `µ⋆ − µ(y) ≤ 4(µ⋆ − r_λ(x) + µ⋆ − r_λ(z))`, and the four trade probabilities
`P(x), P(z), P(p, v), P(u, q)` are within a factor of `3` of each other.
**Formalization Note.** "Either crossed pair" is read as "each of the two crossed pairs" (the
proof bounds both). "Within a factor of 3": `P(a) ≤ 3 P(b)` for any two of the four pairs.
Stated for every `λ > 0`. -/
theorem lemma_6_3 (E : Environment) (hE : RegularUnit E) (lam : ℝ) (hlam : 0 < lam)
(x z : ℝ × ℝ) (hx : x ∈ intT) (hz : z ∈ intT)
(hrx : 99 / 100 * muStar E ≤ auxProfit E lam x)
(hrz : 99 / 100 * muStar E ≤ auxProfit E lam z) :
(x.1, z.2) ∈ triT ∧ (z.1, x.2) ∈ triT ∧
muStar E - mu E (x.1, z.2) ≤
4 * (muStar E - auxProfit E lam x + (muStar E - auxProfit E lam z)) ∧
muStar E - mu E (z.1, x.2) ≤
4 * (muStar E - auxProfit E lam x + (muStar E - auxProfit E lam z)) ∧
∀ a ∈ ({x, z, (x.1, z.2), (z.1, x.2)} : Set (ℝ × ℝ)),
∀ b ∈ ({x, z, (x.1, z.2), (z.1, x.2)} : Set (ℝ × ℝ)), P E a ≤ 3 * P E b := by sorry
end BilateralProfitRegular
Source
Brüstle, di Gregorio, Fusco, Leonardi, Regret Bounds for Profit Maximization in Bilateral Trade: Learning the Best Posted-Price Mechanism (manuscript, STOC 2027 submission, sha256 e91e81279505b765c7c96c219d674c0fbbbd6ca47a00da8fe228d498ca25ac87), Lemma 6.3, p.38 (PDF 40); proof pp.38–39 (PDF 40–41)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.