Lemma 3.3 — the filtering procedure, qualitative form (constants , regret )
ProvedBilateralProfitMHR.lemma_3_3bilateral-trademonotone-hazard-rateonline-learningp2o-gran-per-chapterp2o-plan-paperp2o-v1posted-pricesregret-bounds
There exist constants and such that the following holds for all and every pair of independent MHR seller and buyer laws with densities strictly positive on . With probability at least , the filtering procedure (Initialize mhr) either
-
does not trigger and , or
-
returns a scale and a convex body (nonempty, compact, convex) such that
- (i) every price has ;
- (ii) ;
- (iii) contains every maximizer of over , and ;
and the regret incurred during filtering, over the probing rounds, is at most .
This is the overview's summary of Lemma 5.3.
Differences from the source:
- reading: "with high probability" → with probability at least over the probing valuations; reason: the strength at which Lemma 5.3 and Proposition 5.4 prove it
- reading: "the regret incurred during filtering is " → at most for a universal ; reason: hides logarithmic factors in ; the bound proved is (display after (31), p.34)
- reading: "the filtering procedure" → Initialize mhr (Algorithm 4) with , on independent MHR laws with strictly positive densities on , with the bisection reading of Proposition 5.4; reason: the paper refers to Lemma 5.3 for the exact statement, whose standing hypotheses these are
- encoding: "convex body"; "" → nonempty compact convex set (possibly lower-dimensional); a maximizer in exists; reason: Lemma 5.3's "nonempty, compact, convex"; the maximum is attained
Preamble
import Mathlib import Definitions.Def_BilateralProfitMHR_InitializeMHR
Formal statement
namespace BilateralProfitMHR
open MeasureTheory BilateralProfit MechanismDesign.BilateralTrade
open scoped ENNReal
/-- **Lemma 3.3**, Brüstle, di Gregorio, Fusco, Leonardi (manuscript, sha256 e91e8127…), p.11
(PDF 13): there exist constants `0 < c < C` such that, with high probability, the filtering
procedure either does not trigger and `µ⋆ ≤ C/K`, or returns `ε_{h⋆} = 2^{−h⋆} ≥ 1/K` and a
convex body `𝒦 ⊆ int(𝒯)` satisfying (i) `µ(p, q) ≥ c·ε_{h⋆}` on `𝒦`; (ii)
`ε_{h⋆} ≤ µ⋆ ≤ C·ε_{h⋆}`; (iii) `𝒦` contains every maximizer of `µ` over `G_K ∩ 𝒯`, and therefore
`µ⋆ ≤ max_{𝒦} µ + C/K`. On the same high-probability event, if the procedure triggers, the regret
incurred during filtering is `Õ(K)`.
**Formalization Note.** The filtering procedure is Initialize mhr (Algorithm 4) with
`2 ≤ K ≤ T`; the paper refers to Lemma 5.3 for the exact statement. "With high probability" is
read as probability at least `1 − 1/T` (Lemma 5.3, Proposition 5.4) over the probing valuations;
`Õ(K)` as `C′·K·log²(2T)` for a universal `C′` (the display after (31), p.34); the regret during
filtering is the realized `∑ (µ⋆ − µ(p_t, q_t))` of the probing rounds. A convex body is a
nonempty compact convex set (possibly lower-dimensional). The max over `𝒦` is stated with
attainment. All constants are universal: chosen before `T`, `K` and the distributions
(independent, positive densities on `[0, 1]`, both MHR). -/
theorem lemma_3_3 :
∃ c C C' : ℝ, 0 < c ∧ c < C ∧ ∀ T K : ℕ, 2 ≤ K → K ≤ T →
∀ E : Environment, UnitSupport E → IsMHR E →
∃ G : Set (Samples K T), MeasurableSet G ∧ 1 - (T : ℝ≥0∞)⁻¹ ≤ initLaw K T E.prior G ∧
∀ ω ∈ G,
(initOut K T ω = none ∧ muStar E.prior ≤ C / K) ∨
∃ (h : ℕ) (R : Set (ℝ × ℝ)), initOut K T ω = some (h, R) ∧ 1 / (K : ℝ) ≤ delta h ∧
R.Nonempty ∧ IsCompact R ∧ Convex ℝ R ∧ R ⊆ intT ∧
(∀ x ∈ R, c * delta h ≤ muP E.prior x) ∧
(delta h ≤ muStar E.prior ∧ muStar E.prior ≤ C * delta h) ∧
(∀ e : Act K, IsGridMax K E.prior e → pt K e.1 ∈ R) ∧
(∃ x ∈ R, (∀ y ∈ R, muP E.prior y ≤ muP E.prior x) ∧
muStar E.prior ≤ muP E.prior x + C / K) ∧
filterRegret K T E.prior ω ≤ C' * K * Real.log (2 * T) ^ 2 := by sorry
end BilateralProfitMHR
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 3.3, p.11 (PDF 13); exact form Lemma 5.3, pp.32–34 (PDF 34–36)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.