Lemma A.6 — discretization error
ProvedBilateralProfit.lemma_A_6bilateral-tradeonline-learningp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1posted-pricesregret-bounds
For every integer and every (that is, ) there is a pair such that for every valuation pair ,
Consequently, restricting the comparator to adds at most to regret: for every horizon , valuation sequence and sequence of (expected) profits of any algorithm,
Differences from the source:
- generalization: every valuation pair (in ) → every real pair ; reason: the bound holds for all reals and specializes to
- reading: "restricting the comparator to adds at most to regret" → for every , every valuation sequence and every profit sequence of an algorithm, the regret against is at most the regret against plus , with the same ; reason: with this gives the sup over at most the sup over plus
Preamble
import Mathlib import Definitions.Def_BilateralProfit_Model
Formal statement
namespace BilateralProfit
/-- **Lemma A.6 (Discretization Error)**, Brüstle, di Gregorio, Fusco, Leonardi (manuscript,
sha256 e91e8127…), p.57 (PDF 59): for every integer `K ≥ 1` and every `(p, q) ∈ 𝒯` there is a
pair `(p′, q′) ∈ 𝒜` such that, for every valuation pair `(s_t, b_t)`,
`Profit_t(p, q) ≤ Profit_t(p′, q′) + 2/K`. Consequently, restricting the comparator to `𝒜` adds at
most `2T/K` to regret.
**Formalization Note.** `𝒯 = {0 ≤ p ≤ q ≤ 1}`. The pointwise bound is stated for all real
valuation pairs. The regret consequence is stated for every horizon `T`, every valuation
sequence and every sequence `X_t` of (expected) profits of any algorithm, with the same grid pair
`(p′, q′)`. -/
theorem lemma_A_6 (K : ℕ) (hK : 1 ≤ K) (p q : ℝ) (hp : 0 ≤ p) (hpq : p ≤ q) (hq : q ≤ 1) :
∃ a' : Act K,
(∀ s b : ℝ, profit (s, b) (p, q) ≤ profit (s, b) (pt K a'.1) + 2 / K) ∧
∀ (T : ℕ) (S : Fin T → ℝ × ℝ) (X : Fin T → ℝ),
∑ t, (profit (S t) (p, q) - X t) ≤ ∑ t, (profit (S t) (pt K a'.1) - X t) + 2 * T / 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 A.6, p.57 (PDF 59)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.