§4.2.2 (proof of Theorem 4.1) — rounding valuations to the grid preserves profit and feedback
ProvedBilateralProfit.grid_roundingbilateral-tradeonline-learningp2o-gran-per-chapterp2o-plan-paperp2o-v1posted-pricesregret-bounds
Let . For put and (seller values rounded up, buyer values down). Then
- ;
- for every action , and ;
- hence for every valuation sequence in and every realization of its randomness, Algorithm 1 posts the same prices, holds the same weights and performs the same number of operations on the sequence as on its rounding.
So restricting the valuations to is without loss of generality.
Differences from the source:
- encoding: the grid of step size → hypothesis ; reason: the step size presupposes (Lemma A.6: "for every integer ")
- reading: "Restricting to is without loss of generality since rounding … preserves the profit and feedback for any action in " → the rounding lands in , preserves trade bit and profit at every action, and leaves the whole run of Algorithm 1 unchanged; reason: the run depends on the valuations only through the trade bits, which is what makes the restriction without loss of generality
Preamble
import Mathlib import Definitions.Def_BilateralProfit_Algorithm1
Formal statement
namespace BilateralProfit
/-- **Grid rounding of valuations in the proof of Theorem 4.1**, Brüstle, di Gregorio, Fusco,
Leonardi (manuscript, sha256 e91e8127…), §4.2.2, p.23 (PDF 25): "rounding seller values up and
buyer values down to the grid preserves the profit and feedback for any action in `𝒜`".
For `(s, b) ∈ [0,1]²` let `s̄ = ⌈Ks⌉/K` and `b̄ = ⌊Kb⌋/K`. Then
1. `(s̄, b̄)` is a point of `G_K`;
2. for every `a ∈ 𝒜`, `z_a(s, b) = z_a(s̄, b̄)` and `Profit((s, b), a) = Profit((s̄, b̄), a)`;
3. consequently, for every valuation sequence in `[0,1]²` and every realization of the
randomness, Algorithm 1 posts the same prices, holds the same weights and performs the same
operations on the sequence and on its rounding. -/
theorem grid_rounding (K : ℕ) (hK : 0 < K) :
(∀ s b : ℝ, s ∈ Set.Icc (0 : ℝ) 1 → b ∈ Set.Icc (0 : ℝ) 1 →
(∃ x : Grid K, pt K x = ((⌈(K : ℝ) * s⌉₊ : ℝ) / K, (⌊(K : ℝ) * b⌋₊ : ℝ) / K)) ∧
∀ a : Act K,
tradeBit (s, b) (pt K a.1) =
tradeBit ((⌈(K : ℝ) * s⌉₊ : ℝ) / K, (⌊(K : ℝ) * b⌋₊ : ℝ) / K) (pt K a.1) ∧
profit (s, b) (pt K a.1) =
profit ((⌈(K : ℝ) * s⌉₊ : ℝ) / K, (⌊(K : ℝ) * b⌋₊ : ℝ) / K) (pt K a.1)) ∧
∀ (T : ℕ) (S : Fin T → ℝ × ℝ), (∀ t, S t ∈ Set.Icc (0 : ℝ) 1 ×ˢ Set.Icc (0 : ℝ) 1) →
∀ ω : Fin T → Fin (Jpar K),
runW (alg1 K T S ω) =
runW (alg1 K T (fun t => ((⌈(K : ℝ) * (S t).1⌉₊ : ℝ) / K,
(⌊(K : ℝ) * (S t).2⌋₊ : ℝ) / 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), proof of Theorem 4.1, §4.2.2, p.23 (PDF 25)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.