Lemma 4.6 — OneRound guarantee
ProvedBilateralProfit.lemma_4_6bilateral-tradeonline-learningp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1posted-pricesregret-bounds
Let and let be a constant for which the information inequality of Theorem 4.2 holds at resolution for every distribution on . Let be a probability vector on with for all , and let be the proposal returned by OneRound. Then its score (6) satisfies
the expectation being over the uniform draw of OneRound.
This is the per-round guarantee that the proof of Theorem 4.1 telescopes.
Formalization Note The score uses the returned and the input ; the expectation over is the average over the draws; the maximum is a bound for every .
Differences from the source:
- generalization: the universal constant of Theorem 4.2 → any for which Theorem 4.2's inequality holds at this for every ; reason: the universal is such a constant, so the paper's statement is the special case
- encoding: the grid of step size → hypothesis ; reason: the step size presupposes (Lemma A.6: "for every integer ")
- encoding: over the randomness of OneRound → for every , the average over () of the score of the returned proposal; reason: OneRound's only randomness is , uniform on
Preamble
import Mathlib import Definitions.Def_BilateralProfit_OneRound
Formal statement
namespace BilateralProfit
/-- **Lemma 4.6 (OneRound guarantee)**, Brüstle, di Gregorio, Fusco, Leonardi (manuscript,
sha256 e91e8127…), p.21 (PDF 23), eq. (13).
Let `C0` be a constant for which the information inequality (Theorem 4.2) holds at resolution
`K`. Let `w` be a probability vector on `𝒜` with `w(a′) ≥ 1/(|𝒜|(1 + βK))` for all `a′`, and let
`(a, Q_0, Q_1)` be the proposal returned by `OneRound(w)`. Then for every `a′ ∈ 𝒜` and `v ∈ G_K`,
`E[h_a(v, a′)] ≤ (C0 + 2)/K`, the expectation being over the uniform draw `j⋆ ∈ {1, …, J}`.
**Formalization Note.** The score `h_a` is (6), computed from the returned `Q_0, Q_1` and the
input `w`. The expectation over `j⋆` is the average over `j : Fin J`. -/
theorem lemma_4_6 (K : ℕ) (hK : 0 < K) (C₀ : ℝ)
(hC₀ : ∀ ρ : Grid K × Act K → ℝ, IsDist ρ →
∃ a : Act K, gap ρ a - beta K * info ρ a ≤ C₀ / K)
(w : Act K → ℝ) (hw : IsDist w) (hwf : ∀ a', wFloor K ≤ w a') (v : Grid K) (a' : Act K) :
(∑ j : Fin (Jpar K), hScore w (oneRoundVal K w j) v a') / Jpar K ≤ (C₀ + 2) / K := by sorry
end BilateralProfit
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 4.6, p.21 (PDF 23), eq. (13); proof pp.21–22 (PDF 23–24)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.