Eq. (17) — the measure controls profit differences, and
ProvedBilateralProfit.eq_17bilateral-tradeonline-learningp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1posted-pricesregret-bounds
Let be a valuation law on , , and as in (16). For seller prices and buyer prices in ,
and the total mass of is .
In Step 2 of the proof of Lemma 4.8 this is used with , the valuation marginal of , to choose the buyer blocks (Algorithm 3) and to bound their number.
Formalization Note is written . is Lebesgue measure on .
Differences from the source:
- generalization: , the valuation marginal of on , and grid prices in a seller node, in the buyer grid → every valuation law on and all prices , in ; reason: the marginal of is such a law, and its expected-profit differences are
- encoding: the Lebesgue measure in , a measure on → Lebesgue measure restricted to ; reason: is a measure on , and every set the statement measures lies in , where both give the same value
Preamble
import Mathlib import Definitions.Def_BilateralProfit_SellerTree
Formal statement
namespace BilateralProfit
open MeasureTheory
/-- **Equation (17)** and the total mass of `ν`, Brüstle, di Gregorio, Fusco, Leonardi
(manuscript, sha256 e91e8127…), Step 2 of the proof of Lemma 4.8, p.24 (PDF 26).
For a valuation law `P` on `[0,1]²` and `ν = L ⊗ P_b + P_s ⊗ L + P` (16): for seller prices
`l ≤ r` and buyer prices `q₀ ≤ q` in `[0, 1]`,
`|Δ((r, q), (l, q)) − Δ((r, q₀), (l, q₀))| ≤ ν((l, r] × [q₀, q))`, where
`Δ(a′, a) = E_P[Profit(V, a′) − Profit(V, a)]`; and `ν([0,1]²) = 3`.
**Formalization Note.** The paper uses the valuation marginal `P_{P0}` of `ρ` (a law on the
grid) and grid prices in a seller node; the statement holds for every valuation law and all
prices in `[0, 1]`. -/
theorem eq_17 (μ : Measure (ℝ × ℝ)) (hμ : IsValLaw μ) :
(∀ l r q₀ q : ℝ, l ∈ Set.Icc (0 : ℝ) 1 → r ∈ Set.Icc (0 : ℝ) 1 → q₀ ∈ Set.Icc (0 : ℝ) 1 →
q ∈ Set.Icc (0 : ℝ) 1 → l ≤ r → q₀ ≤ q →
|(muP μ (r, q) - muP μ (l, q)) - (muP μ (r, q₀) - muP μ (l, q₀))| ≤
(nuMeas μ (Set.Ioc l r ×ˢ Set.Ico q₀ q)).toReal) ∧
nuMeas μ (Set.Icc (0 : ℝ) 1 ×ˢ Set.Icc (0 : ℝ) 1) = 3 := 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), proof of Lemma 4.8, Step 2, p.24 (PDF 26), eqs. (15)–(17)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.