§7, p.52 — the regret against is at least
ProvedBilateralProfitLB.regret_displaybilateral-tradelower-boundsonline-learningp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1posted-pricesregret-bounds
Let , , , and let be any posted-price policy with two-bit feedback, possibly randomized through a seed drawn from a probability space . Let be the number of rounds with buyer price and the expectation when the valuations are i.i.d. , independent of the seed. Then the regret of against satisfies
witnessed by a single comparator: there is with .
Each round spent outside the right interval costs at least the gap ; together with Claim 3.6 this gives Theorem 7.1.
Formalization Note The comparator is not fixed to , since need not maximize inside .
Differences from the source:
- generalization: "the deterministic algorithm " → every, possibly randomized, two-bit policy on a probability space of seeds; reason: a deterministic algorithm is the case of a one-point seed space, and the same argument applies round by round
- encoding: → some comparator achieves the bound; reason: the supremum is attained (p.4), so the two agree
- reading: counts buyer prices in , a piece of a partition with unspecified endpoints → open; reason: the strongest choice: fewer rounds are counted, so the bound implies the one for every choice of endpoints
Preamble
import Mathlib import Definitions.Def_BilateralProfitLB_Construction import Definitions.Def_BilateralProfitLB_Stochastic
Formal statement
namespace BilateralProfitLB
open MeasureTheory
/-- **§7, p.52 (PDF 54), display after Claim 3.6's proof**, Brüstle, di Gregorio, Fusco,
Leonardi (manuscript, sha256 e91e8127…): "By Claim 3.4 and recalling that `∆ = w²/(384·12)` is
the 'suboptimality gap' of playing outside the right interval, the regret of the deterministic
algorithm `𝒜` against the generic distribution `𝒟_j` is `R_T(𝒜, 𝒟_j) ≥ (T − E^j[N_j])∆`".
Stated for every `K ≥ 1`, `j ∈ {1, …, K}`, horizon `T` and every (possibly randomized) two-bit
policy `π` on a probability space `(Ω, P)`: some comparator `(p, q) ∈ [0, 1]²` has
`Σ_t (E^j[Profit_t(p, q)] − E^j[Profit_t(p_t, q_t)]) ≥ (T − E^j[N_j]) ∆`.
**Formalization Note.** The paper's `R_T` is the supremum over comparators; a comparator that
achieves the bound is the same statement (the supremum is attained, p.4). The comparator is not
fixed to `(q⋆_j/2, q⋆_j)`: `q⋆_j` need not maximize `h^j` on `I_j`. -/
theorem regret_display (K : ℕ) (hK : 1 ≤ K) (j : ℕ) (hj1 : 1 ≤ j) (hjK : j ≤ K) (T : ℕ)
(Ω : Type) [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P] (π : Policy Ω) :
∃ a ∈ Set.Icc (0 : ℝ) 1 ×ˢ Set.Icc (0 : ℝ) 1,
((T : ℝ) - expCount π P (law K j) T (I K j)) * Delta K ≤ regret π P (law K j) T a := by sorry
end BilateralProfitLB
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), §7, p.52 (PDF 54), display after the proof of Claim 3.6; also p.16 (PDF 18)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.