Theorem 4.2 — information inequality
ProvedBilateralProfit.theorem_4_2bilateral-tradeonline-learningp2o-gran-per-chapterp2o-plan-paperp2o-v1posted-pricesregret-bounds
There is a universal constant such that, for every and every distribution over , with ,
Against every table , some price either has small expected gap or reveals much information about the coupling between the valuation and the action. This is the engine of Lemma 4.6 and hence of the regret bound.
Formalization Note is chosen before and . The minimum over the finite nonempty is written as the existence of a minimizing action. Logarithms are natural.
Differences from the source:
- encoding: the grid of step size → hypothesis ; reason: the step size presupposes (Lemma A.6: "for every integer ")
- encoding: → with the value ; reason: equivalent over a finite nonempty set
Preamble
import Mathlib import Definitions.Def_BilateralProfit_Analysis
Formal statement
namespace BilateralProfit
/-- **Theorem 4.2 (Information Inequality)**, Brüstle, di Gregorio, Fusco, Leonardi
(manuscript, sha256 e91e8127…), p.19 (PDF 21): there is a universal constant `C0` such that for
every distribution `ρ` over `G_K × 𝒜`, with `β = K² log⁶ K`,
`min_{a ∈ 𝒜} {Δ_ρ(a) − β ℐ_ρ(a)} ≤ C0/K`.
**Formalization Note.** `C0` is chosen before `K` and `ρ`. The minimum over the finite nonempty
`𝒜` is written as the existence of a minimizing action. `0 < K` is the grid's step size `1/K`. -/
theorem theorem_4_2 :
∃ C₀ : ℝ, ∀ K : ℕ, 0 < K → ∀ ρ : Grid K × Act K → ℝ, IsDist ρ →
∃ a : Act K, gap ρ a - beta K * info ρ a ≤ C₀ / 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), Theorem 4.2, p.19 (PDF 21); proof pp.19–21 (PDF 21–23)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.