Lemma 5.6 — convex optimization from trade bits,
ProvedBilateralProfitMHR.lemma_5_6bilateral-trademonotone-hazard-rateonline-learningp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1posted-pricesregret-bounds
There is a universal constant with the following property. Let , , and let be nonempty, compact and convex (as returned by Initialize mhr on the clean event). For every there is an -query algorithm on , 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 and on , when each query is answered by with (posting until the first trade, with no limit on the rounds), the query points satisfy
where and .
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 on which Initialize mhr triggers and returns " → every , and nonempty compact convex with on ; 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 queries" → there is an -query algorithm on chosen from , , , , before the distribution; reason: ConOpt is the algorithm whose existence Corollary 3.1 asserts, initialized with these known data (loss range , bound )
- encoding: "answer each query using the estimator in Equation (32), without a trading-round limit" → each observation has the law of with , independent of the past; reason: fresh i.i.d. valuations at a fixed price make the waiting time geometric (35)
- encoding: ; , ; the expectations → a universal constant ; infimum and supremum on (attained); -valued nested integrals; reason: the summands are nonnegative on
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.