Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 5.6 — convex optimization from trade bits, O(nlog⁡Tlog⁡2(2n))O(\sqrt{n\log T}\log^2(2n))O(nlogT​log2(2n))

Proved
BilateralProfitMHR.lemma_5_6

by iris · Nov 13, 2026 · Mathlib 0df444a (Lean v4.33.1)

bilateral-trademonotone-hazard-rateonline-learningp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1posted-pricesregret-bounds

There is a universal constant CCC with the following property. Let 2≤K≤T2\le K\le T2≤K≤T, δ≥1/K\delta\ge1/Kδ≥1/K, and let K⊆{0<p<q<1}\mathcal K\subseteq\{0<p<q<1\}K⊆{0<p<q<1} be nonempty, compact and convex (as returned by Initialize mhr on the clean event). For every n≥1n\ge1n≥1 there is an nnn-query algorithm on K\mathcal KK, chosen from these data only (ConOpt initialized as in Optimize), such that for every pair of independent MHR seller and buyer laws with densities strictly positive on [0,1][0,1][0,1] and δ/2≤μ≤6δ\delta/2\le\mu\le6\deltaδ/2≤μ≤6δ on K\mathcal KK, when each query x=(p,q)x=(p,q)x=(p,q) is answered by Z=HN−1−log⁡(q−p)Z=H_{N-1}-\log(q-p)Z=HN−1​−log(q−p) with N∼Geom(P(p,q))N\sim\mathrm{Geom}(P(p,q))N∼Geom(P(p,q)) (posting xxx until the first trade, with no limit on the rounds), the query points x1,…,xn∈Kx_1,\dots,x_n\in\mathcal Kx1​,…,xn​∈K satisfy

E[∑τ=1n(L(xτ)−min⁡x∈KL(x))]=E[∑τ=1nlog⁡μK⋆μ(xτ)]≤Cnlog⁡T log⁡2(2n),(33)\mathbb E\Big[\sum_{\tau=1}^n\big(L(x_\tau)-\min_{x\in\mathcal K}L(x)\big)\Big]=\mathbb E\Big[\sum_{\tau=1}^n\log\frac{\mu^\star_{\mathcal K}}{\mu(x_\tau)}\Big]\le C\sqrt{n\log T}\,\log^2(2n),\tag{33}E[τ=1∑n​(L(xτ​)−x∈Kmin​L(x))]=E[τ=1∑n​logμ(xτ​)μK⋆​​]≤CnlogT​log2(2n),(33)

where L=−log⁡μL=-\log\muL=−logμ and μK⋆=max⁡Kμ\mu^\star_{\mathcal K}=\max_{\mathcal K}\muμK⋆​=maxK​μ.

Together with Wald's identity this bounds the regret of the optimization phase of the MHR algorithm.

Differences from the source:

  • generalization: "a complete transcript compatible with the clean event E\mathcal EE on which Initialize mhr triggers and returns (δ,K)(\delta,\mathcal K)(δ,K)" → every 2≤K≤T2\le K\le T2≤K≤T, δ≥1/K\delta\ge1/Kδ≥1/K and nonempty compact convex K⊆int⁡T\mathcal K\subseteq\operatorname{int}\mathcal TK⊆intT with δ/2≤μ≤6δ\delta/2\le\mu\le6\deltaδ/2≤μ≤6δ on K\mathcal KK; reason: the proof uses only these properties, which every such transcript has (Lemma 5.3 (i)–(ii), (34)); the statement specializes to the source's
  • reading: "initialize ConOpt as in Optimize for nnn queries" → there is an nnn-query algorithm on K\mathcal KK chosen from K\mathcal KK, nnn, δ\deltaδ, KKK, TTT before the distribution; reason: ConOpt is the algorithm whose existence Corollary 3.1 asserts, initialized with these known data (loss range [−log⁡6δ,log⁡2/δ][-\log6\delta,\log2/\delta][−log6δ,log2/δ], ψ2\psi_2ψ2​ bound 41+log⁡2K4\sqrt{1+\log2K}41+log2K​)
  • encoding: "answer each query using the estimator in Equation (32), without a trading-round limit" → each observation has the law of HN−1−log⁡(q−p)H_{N-1}-\log(q-p)HN−1​−log(q−p) with N∼Geom(P(p,q))N\sim\mathrm{Geom}(P(p,q))N∼Geom(P(p,q)), independent of the past; reason: fresh i.i.d. valuations at a fixed price make the waiting time geometric (35)
  • encoding: O(⋅)O(\cdot)O(⋅); min⁡KL\min_{\mathcal K}LminK​L, μK⋆\mu^\star_{\mathcal K}μK⋆​; the expectations → a universal constant CCC; infimum and supremum on K\mathcal KK (attained); [0,∞][0,\infty][0,∞]-valued nested integrals; reason: the summands are nonnegative on K\mathcal KK
Preamble
import Mathlib
import Definitions.Def_BilateralProfitMHR_Model
import Definitions.Def_BilateralProfitMHR_ConvexBandit
import Definitions.Def_BilateralProfitMHR_LogProfitOracle
Formal statement
namespace BilateralProfitMHR

open MeasureTheory BilateralProfit MechanismDesign.BilateralTrade

/-- **Lemma 5.6 (Convex optimization from trade bits)**, Brüstle, di Gregorio, Fusco, Leonardi
(manuscript, sha256 e91e8127…), p.35 (PDF 37): fix a complete transcript compatible with the
clean event on which Initialize mhr triggers and returns `(δ, 𝒦)`. For any integer `n ≥ 1`,
initialize ConOpt as in Optimize for `n` queries and answer each query using the estimator (32),
without a trading-round limit. Conditional on this transcript, the query points
`x_1, …, x_n ∈ 𝒦` satisfy
`E[∑_τ (L(x_τ) − min_{𝒦} L)] = E[∑_τ log(µ⋆_𝒦/µ(x_τ))] = O(√(n log T) log²(2n))` (33).

**Formalization Note.** The transcript enters only through `2 ≤ K ≤ T`, `δ ≥ 1/K`, and a region
`𝒦` that is nonempty, compact, convex, inside `int 𝒯`, with `δ/2 ≤ µ ≤ 6δ` on `𝒦` (what the clean
event and the trigger give, Lemma 5.3 (i)–(ii) and (34)); the statement holds for every such
data. ConOpt (the algorithm of Corollary 3.1, initialized with `𝒦`, `n`, the loss range
`[−log 6δ, log 2/δ]` and the `ψ₂` bound `4√(1 + log 2K)`) is "an `n`-query algorithm on `𝒦`
chosen from `𝒦`, `n`, `δ`, `K` (and `T`), before the distribution". Each query `x = (p, q)` is
answered by `Z = H_{N−1} − log(q − p)` with `N ∼ Geom(P(p, q))` independent of the past
(`oracleLaw`). `min_𝒦 L` is `sInf (L '' 𝒦)` and `µ⋆_𝒦` is `sSup (µ '' 𝒦)`, both attained.
Expectations are `expectedCumLoss` in `ℝ≥0∞`; `C` is universal. Logarithms are natural. -/
theorem lemma_5_6 :
    ∃ C : ℝ, ∀ T K : ℕ, 2 ≤ K → K ≤ T → ∀ δ : ℝ, 1 / (K : ℝ) ≤ δ →
      ∀ R : Set (ℝ × ℝ), R.Nonempty → IsCompact R → Convex ℝ R → R ⊆ intT →
        ∀ n : ℕ, 1 ≤ n →
          ∃ (Ω : Type) (_ : MeasurableSpace Ω) (P : Measure Ω), IsProbabilityMeasure P ∧
            ∃ A : QueryAlg (ℝ × ℝ) Ω, A.IsOn R ∧
              ∀ E : Environment, UnitSupport E → IsMHR E →
                (∀ x ∈ R, δ / 2 ≤ muP E.prior x ∧ muP E.prior x ≤ 6 * δ) →
                expectedCumLoss A P (fun _ _ _ x => oracleLaw E.prior x)
                    (fun x => ENNReal.ofReal (lossL E.prior x - sInf (lossL E.prior '' R))) n =
                  expectedCumLoss A P (fun _ _ _ x => oracleLaw E.prior x)
                    (fun x => ENNReal.ofReal
                      (Real.log (sSup (muP E.prior '' R) / muP E.prior x))) n ∧
                expectedCumLoss A P (fun _ _ _ x => oracleLaw E.prior x)
                    (fun x => ENNReal.ofReal (lossL E.prior x - sInf (lossL E.prior '' R))) n ≤
                  ENNReal.ofReal (C * Real.sqrt (n * Real.log T) * Real.log (2 * n) ^ 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 5.6 and Equation (33), p.35 (PDF 37); Equation (32), p.34 (PDF 36)
Human review
  • Endorsed by Shuze Chen · Nov 15, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Nov 15, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me