Claim 3.4 — has a plateau of maximizers on with value , and
ProvedBilateralProfitLB.claim_3_4bilateral-tradelower-boundsonline-learningp2o-gran-per-chapterp2o-plan-paperp2o-v1posted-pricesregret-bounds
Let , and . Let be the expected profit of the prices under , for buyer prices . Then:
- for every , and for , if and only if : the function has a plateau of maximizers on , with maximum value ;
- for every , with the midpoint of ,
that is, .
Every perturbed instance thus has its optimum inside its own interval , by a margin of order , while the baseline does not single out any interval.
Differences from the source:
- reading: " has a plateau of maximizers in " → on the maximizers of are exactly ; reason: the proof shows the first branch increasing and the last decreasing; this is the stronger reading
- reading: → ; reason: (76) and p.52 write ; the other parse makes (ii) false at (gain )
- encoding: → a bound for every ; reason: buyer prices range over and the maximum is attained, so the two agree
- reading: , a piece of a partition of with unspecified endpoints → open; reason: the strongest choice: (ii) then covers every outside the open interval, including both endpoints, where , so it implies (ii) for every choice of endpoints
Preamble
import Mathlib import Definitions.Def_BilateralProfitLB_Construction
Formal statement
namespace BilateralProfitLB
/-- **Claim 3.4**, Brüstle, di Gregorio, Fusco, Leonardi (manuscript, sha256 e91e8127…), p.15
(PDF 17), restated with its proof p.51 (PDF 53): for any `j = 1, …, K`,
(i) the function `h^0` has a plateau of maximizers in `[1/4, 1/2]`, with maximum value `1/192`;
(ii) letting `q⋆_j` be the midpoint of `I_j`, `h^j(q⋆_j) − max_{q ∉ I_j} h^j(q) ≥ ∆`, where
`∆ = w²/(384·12)`.
**Formalization Note.** Buyer prices range over `[0, 1]`. (i) is: `h^0 ≤ 1/192` on `[0, 1]`, and
on `[0, 1]` the maximizers are exactly `[1/4, 1/2]` (the proof shows the first branch increasing
and the last decreasing). (ii) is stated for every `q ∈ [0, 1] ∖ I_j`, which is the same as the
bound on the maximum (it is attained). `h^0` does not depend on `K`. -/
theorem claim_3_4 (K : ℕ) (hK : 1 ≤ K) :
((∀ q ∈ Set.Icc (0 : ℝ) 1, h K 0 q ≤ 1 / 192) ∧
∀ q ∈ Set.Icc (0 : ℝ) 1, (h K 0 q = 1 / 192 ↔ q ∈ Set.Icc (1 / 4 : ℝ) (1 / 2))) ∧
∀ j : ℕ, 1 ≤ j → j ≤ K →
∀ q ∈ Set.Icc (0 : ℝ) 1, q ∉ I K j → Delta K ≤ h K j (qstar K j) - h K j q := 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), Claim 3.4, p.51 (PDF 53), with eq. (76); first stated p.15 (PDF 17)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.