Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 6.5 — calibration with O(log⁡T/η)O(\log T/\eta)O(logT/η) regret, and unbiased bounded loss observations of 1/rλ1/r_\lambda1/rλ​

Proved
BilateralProfitRegular.lemma_6_5

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

bilateral-tradeonline-learningp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1posted-pricesregret-boundsregular-distributions

Assume the guarantees of Lemma 6.4's event with a trigger: η<δ\eta<\deltaη<δ, δ≤μ⋆<6δ\delta\le\mu^\star<6\deltaδ≤μ⋆<6δ, and a valid candidate (Ki,wi,θi,P^(wi))(\mathcal K_i,w_i,\theta_i,\widehat P(w_i))(Ki​,wi​,θi​,P(wi​)). Let z∈Kiz\in\mathcal K_iz∈Ki​ be a reference, and let η∈(0,1)\eta\in(0,1)η∈(0,1) with ⌈1/η⌉≤T\lceil1/\eta\rceil\le T⌈1/η⌉≤T. There is a universal constant CCC such that the following hold.

(i) Calibration. There is a procedure, built from the known data, with the following properties:

  • it posts only prices in T\mathcal TT;
  • it incurs expected regret at most Clog⁡(T)/ηC\log(T)/\etaClog(T)/η;
  • except with probability at most 1/T1/T1/T, it returns ρ>0\rho>0ρ>0 with
∣log⁡ρλzλi∣≤10−3η/δ.(49)\Big|\log\frac{\rho\lambda_z}{\lambda_i}\Big|\le10^{-3}\sqrt{\eta/\delta}. \tag{49}​logλi​ρλz​​​≤10−3η/δ​.(49)

(ii) Loss observations. Let ρ\rhoρ satisfy (49), let λ=ρλz\lambda=\rho\lambda_zλ=ρλz​ and L=1/rλL=1/r_\lambdaL=1/rλ​. Each query x∈Kix\in\mathcal K_ix∈Ki​ admits an observation procedure with the following properties:

  • it uses at least one trading round;
  • its output YxY_xYx​ satisfies 0≤Yx≤C/δ0\le Y_x\le C/\delta0≤Yx​≤C/δ and E[Yx]=L(x)\mathbb E[Y_x]=L(x)E[Yx​]=L(x);
  • its expected number of rounds is at most C/δC/\deltaC/δ;
  • every price pair yyy it posts lies in T\mathcal TT and satisfies
μ⋆−μ(y)≤C(μ⋆−rλ(z))+Cδ2(L(x)−min⁡KiL).(51)\mu^\star-\mu(y)\le C\big(\mu^\star-r_\lambda(z)\big)+C\delta^2\big(L(x)-\min_{\mathcal K_i}L\big). \tag{51}μ⋆−μ(y)≤C(μ⋆−rλ​(z))+Cδ2(L(x)−Ki​min​L).(51)

The procedures use fresh randomness and fresh valuations, so these are also the conditional statements given the past and xxx.

Differences from the source:

  • generalization: "Assume the guarantees of the high probability event in Lemma 6.4 hold, with Initialize regular triggering"; a candidate of its list → any candidate satisfying Valid with η<δ\eta<\deltaη<δ, δ≤μ⋆<6δ\delta\le\mu^\star<6\deltaδ≤μ⋆<6δ (not necessarily output by Algorithm 7); reason: the proof uses only these properties; on Lemma 6.4's event every listed candidate satisfies them
  • encoding: "can be implemented", "admits an observation"; "E[Yx∣past,x]\mathbb E[Y_x\mid\text{past},x]E[Yx​∣past,x]", "conditionally on the choice of xxx and the history" → there exist sampling procedures, chosen from the known data before the environment; statements for a fixed xxx; reason: the procedures use fresh randomness and valuations, so conditioning on the past changes nothing
  • encoding: "incur O(log⁡(T)/η)O(\log(T)/\eta)O(log(T)/η) regret"; "every price pair posted … satisfies (51)" → expected sum of μ⋆−μ(y)\mu^\star-\mu(y)μ⋆−μ(y) over posted yyy; (51) and y∈Ty\in\mathcal Ty∈T for every price the procedure can post (every seed, every history); reason: regret is the expected sum of gaps (p.4); the static form is the stronger one
  • encoding: independent regular seller and buyer distributions on [0,1][0,1][0,1] with strictly positive densities (§2, §6) → RegularUnit E for a published Environment E (supports [0,1][0,1][0,1], E.Regular); PPP, μ\muμ from the joint law E.prior, Fs,FbF_s,F_bFs​,Fb​ = 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
import Definitions.Def_BilateralProfitRegular_Proc
import Definitions.Def_BilateralProfitRegular_InitRegular
Formal statement
namespace BilateralProfitRegular

open MeasureTheory MechanismDesign.BilateralTrade

/-- **Lemma 6.5 (Convex loss observations)**, Brüstle, di Gregorio, Fusco, Leonardi (manuscript,
sha256 e91e8127…), p.41 (PDF 43); proof pp.41–43 (PDF 43–45). Assume the guarantees of the
high-probability event of Lemma 6.4 hold with a trigger; fix a candidate `i` and a reference
`z ∈ 𝒦_i`.

(i) *Calibration.* Calibration can be implemented so as to incur `O(log(T)/η)` regret, returning a
multiplier `ρ` such that, except with probability at most `1/T`,
`|log(ρλ_z/λ_i)| ≤ 10⁻³ √(η/δ)` (49).

(ii) *Loss observations.* For a constant `C` and `ρ` satisfying (49), set `λ = ρλ_z` and
`L = 1/r_λ`. Each query `x ∈ 𝒦_i` admits an observation `Y_x` using at least one trading round at
prices in `𝒯`, with `0 ≤ Y_x ≤ C/δ` and `E[Y_x | past, x] = L(x)` (50), with expected number of
trading rounds at most `C/δ`; every price pair `y` posted to produce `Y_x` satisfies
`µ⋆ − µ(y) ≤ C(µ⋆ − r_λ(z)) + Cδ²(L(x) − min_{𝒦_i} L)` (51).

**Formalization Note.**
* "The guarantees of Lemma 6.4" enter as the hypotheses the proof uses: `η < δ`,
  `δ ≤ µ⋆ < 6δ`, and candidate `i` valid (`Candidate.Valid`), for an arbitrary candidate
  `(𝒦, w, θ, P̂(w))` and `z ∈ 𝒦`, not only for those output by Algorithm 7. Section 6's standing
  assumptions `η ∈ (0, 1)`, `K = ⌈1/η⌉ ≤ T` are kept.
* "Can be implemented" / "admits": there exist procedures, chosen from the known data
  (`T, η, δ`, the candidate, `z`, and in (ii) `ρ` and `x`) before the environment, which they see
  only through trade bits. A procedure uses fresh randomness and fresh valuations, so the
  conditional statements "given the past and `x`" are statements about the procedure for a fixed
  `x`.
* Regret of a procedure: `E[∑_{posted y} (µ⋆ − µ(y))]`. The calibration failure event includes
  "no output" and `ρ ≤ 0`. `min_{𝒦_i} L` is `sInf (L '' 𝒦_i)`.
* One constant `C` serves (i) and (ii); it is universal (chosen before everything else). -/
theorem lemma_6_5 :
    ∃ C : ℝ, 0 < C ∧
      (∀ (T : ℕ) (η : ℝ), 0 < η → η < 1 → gridK η ≤ T →
        ∀ (δ : ℝ) (c : Candidate) (z : ℝ × ℝ),
        ∃ (Ω : Type) (_ : MeasurableSpace Ω) (Pω : Measure Ω) (_ : IsProbabilityMeasure Pω)
          (cal : Proc (ℝ × ℝ) ℝ Ω),
          ∀ E : Environment, RegularUnit E → η < δ → δ ≤ muStar E → muStar E < 6 * δ →
            c.Valid E δ → z ∈ c.region →
            cal.QueriesIn triT ∧
            cal.expCost (P E) Pω (fun y => muStar E - mu E y) ≤
              ENNReal.ofReal (C * Real.log T / η) ∧
            Proc.law Pω {x | ¬ ∃ ρ, cal.out (P E) x.1 x.2 = some ρ ∧ CalibValid E η δ c z ρ} ≤
              ENNReal.ofReal (1 / T)) ∧
      (∀ (η δ : ℝ) (c : Candidate) (z : ℝ × ℝ) (ρ : ℝ) (x : ℝ × ℝ),
        ∃ (Ω : Type) (_ : MeasurableSpace Ω) (Pω : Measure Ω) (_ : IsProbabilityMeasure Pω)
          (obs : Proc (ℝ × ℝ) ℝ Ω),
          ∀ E : Environment, RegularUnit E → 0 < η → η < 1 → η < δ → δ ≤ muStar E →
            muStar E < 6 * δ → c.Valid E δ → z ∈ c.region → CalibValid E η δ c z ρ →
            x ∈ c.region →
            obs.QueriesFirst ∧
            obs.OutputsIn (Set.Icc 0 (C / δ)) ∧
            obs.expRounds (P E) Pω ≤ ENNReal.ofReal (C / δ) ∧
            Proc.law Pω {y | obs.out (P E) y.1 y.2 = none} = 0 ∧
            ∫ y, (obs.out (P E) y.1 y.2).getD 0 ∂(Proc.law Pω) =
              1 / auxProfit E (ρ * balance E z) x ∧
            ∀ ω h y, obs.step ω h = Sum.inl y →
              y ∈ triT ∧
              muStar E - mu E y ≤
                C * (muStar E - auxProfit E (ρ * balance E z) z) +
                  C * δ ^ 2 * (1 / auxProfit E (ρ * balance E z) x -
                    sInf ((fun a => 1 / auxProfit E (ρ * balance E z) a) '' c.region))) := 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.5, p.41 (PDF 43); proof pp.41–43 (PDF 43–45)
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