Lemma 6.5 — calibration with regret, and unbiased bounded loss observations of
ProvedBilateralProfitRegular.lemma_6_5bilateral-tradeonline-learningp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1posted-pricesregret-boundsregular-distributions
Assume the guarantees of Lemma 6.4's event with a trigger: , , and a valid candidate . Let be a reference, and let with . There is a universal constant 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 ;
- it incurs expected regret at most ;
- except with probability at most , it returns with
(ii) Loss observations. Let satisfy (49), let and . Each query admits an observation procedure with the following properties:
- it uses at least one trading round;
- its output satisfies and ;
- its expected number of rounds is at most ;
- every price pair it posts lies in and satisfies
The procedures use fresh randomness and fresh valuations, so these are also the conditional statements given the past and .
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
Validwith , (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"; "", "conditionally on the choice of and the history" → there exist sampling procedures, chosen from the known data before the environment; statements for a fixed ; reason: the procedures use fresh randomness and valuations, so conditioning on the past changes nothing
- encoding: "incur regret"; "every price pair posted … satisfies (51)" → expected sum of over posted ; (51) and 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 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 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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.