Lemma 6.4 — Initialize regular: scale, valid candidates, and regret
ProvedBilateralProfitRegular.lemma_6_4bilateral-tradeonline-learningp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1posted-pricesregret-boundsregular-distributions
Let , let , and let the distributions be independent and regular on with strictly positive densities. Consider Algorithm 7 (Initialize regular) run until it finishes, without stopping at . With probability at least one of the following holds:
- it returns "no trigger" and ; or
- it returns a scale and candidates with and , such that:
- each is compact and convex and contains its root ;
- (i) for every candidate and , on , and some candidate satisfies for ;
- (ii) for any two points of both crosses belong to , the trade probabilities of the crosses and of the points lie in , , and on ;
- the run's regret is at most .
Here is a universal constant, and the statement holds for every processing order of step 4. The proof gives in the no-trigger case.
Differences from the source:
- generalization: "Process retained pairs in a fixed order" (Algorithm 7, step 4) → the statement holds for every processing order (a duplicate-free list of ); reason: it specializes to whichever fixed order the algorithm uses
- reading: Algorithm 4's bisection and "the midpoint of the first recursive split separating "; step 4's choice of root when several pass; for → splits into and ; the earliest created root that passes; for ; reason: the paper does not spell these out; the bisection is the reading under which (48) uses sampled pairs (p.60); pairs with are used only after the test
- encoding: "with probability at least " over fresh trade bits; "", "", " regret" → the measure of the failure event is at most ; one universal constant chosen before , the environment and the order; reason: trade bits realized from i.i.d. uniforms with the same law; the complement form is the stronger one; the constants are universal in the proof
- encoding: "initialization incurs regret" → over all rounds of the full run of , on the good triggered event; reason: the rounds of the run are a function of its transcript; regret of fixed posted pairs is the sum of their gaps
- encoding: independent regular seller and buyer distributions on with strictly positive densities (§2, §6) →
RegularUnit Efor a publishedEnvironmentE(supports ,E.Regular); , from the joint lawE.prior, =E.cdfS,E.cdfB; reason: the same class: Definitions 2.1–2.2 with the standing positivity of the densities; the valuation laws are the environment's
Preamble
import Mathlib import Definitions.Def_BilateralProfitRegular_Stochastic import Definitions.Def_BilateralProfitRegular_Auxiliary import Definitions.Def_BilateralProfitRegular_InitRegular
Formal statement
namespace BilateralProfitRegular
open MeasureTheory MechanismDesign.BilateralTrade
/-- **Lemma 6.4 (Initialization)**, Brüstle, di Gregorio, Fusco, Leonardi (manuscript, sha256
e91e8127…), p.40 (PDF 42); proof App. A.6, pp.61–65 (PDF 63–67). Consider Initialize regular
(Algorithm 7) running until it is finished, without stopping at `T`. With probability at least
`1 − 1/T` it either returns "no trigger", with `µ⋆ = O(1/K)`, or returns a scale `δ > η` with
`δ ≤ µ⋆ < 6δ` and a list of `N = O(√(δ/η) log(2T))` candidates `(𝒦_i, w_i, θ_i, P̂(w_i))`,
each `𝒦_i ⊂ int(𝒯)` compact and convex containing its root `w_i`, satisfying (i) the
auxiliary-profit guarantees (with some candidate `i⋆` near-optimal) and (ii) the crossed-query
bounds (`Candidate.Valid`, `Candidate.NearOpt`, `InitGuarantee`); on such a valid triggered
transcript, initialization incurs `O(K log²(T))` regret.
**Formalization Note.** The run is Algorithm 7 to completion (`initRegular`), driven by i.i.d.
uniforms that realize fresh trade bits; the probability is over them. The failure event's measure
is bounded (the complement form, which is the stronger one for a possibly non-measurable event).
`O(·)` is one universal constant `C` chosen before `T`, `η`, the environment and the processing
order of step 4; the statement holds for every order. `K = ⌈1/η⌉ ≤ T` is the algorithm's input
condition. The regret is `∑ (µ⋆ − µ(a_t))` over all rounds of the full run. The proof gives
`µ⋆ < 6·2^16/K` in the no-trigger case. -/
theorem lemma_6_4 :
∃ C : ℝ, 0 < C ∧
∀ (T : ℕ) (η : ℝ), 0 < η → η < 1 → gridK η ≤ T →
∀ (E : Environment), RegularUnit E →
∀ ord : List (ℕ × ℕ), IsOrder (gridK η) ord →
initCoinLaw {U |
¬ (match initRegular T η ord (P E) U with
| none => muStar E ≤ C / gridK η
| some (δ, cs) =>
InitGuarantee E η δ cs ∧
(cs.length : ℝ) ≤ C * Real.sqrt (δ / η) * Real.log (2 * T) ∧
initRegret E T η U ≤ C * gridK η * Real.log T ^ 2)} ≤
ENNReal.ofReal (1 / T) := by sorry
end BilateralProfitRegular
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 6.4, p.40 (PDF 42); proof App. A.6, pp.61–65 (PDF 63–67)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.