(6), p.9 — the inner product of step-function sums on
ProvedLearnVsOpt.display_6budgeted-gamescalibrationgame-theoryonline-learningp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and be finite linear combinations of step functions, with real weights and with thresholds . Then the inner product evaluates as
This is what makes the calibration error computable: the program's arithmetic on is this formula.
Differences from the source:
- encoding: finite index sets of k, ℓ → Fin m, Fin m′; reason: relabeling
Preamble
import Mathlib
Formal statement
namespace LearnVsOpt
/-- **Display (6)** (Fikioris, Sivan & Tardos, *Learning vs. Optimizing Players in Budgeted Games*,
arXiv:2611.05580, (6), p.9). For linear combinations of step functions `r = Σ_k w_k 1_{·≤q_k}` and
`r̃ = Σ_ℓ w̃_ℓ 1_{·≤q̃_ℓ}` with thresholds in `[0, 1]`, the inner product (5) on `L²([−1, 1])` is
`⟨r, r̃⟩ = Σ_{k,ℓ} w_k w̃_ℓ (1 + min{q_k, q̃_ℓ})`, and `‖r‖²_{L²} = Σ_{k,k'} w_k w_{k'} (1 + min{q_k, q_{k'}})`.
-/
theorem display_6 {m m' : ℕ} (w q : Fin m → ℝ) (w' q' : Fin m' → ℝ)
(hq : ∀ k, q k ∈ Set.Icc (0 : ℝ) 1) (hq' : ∀ l, q' l ∈ Set.Icc (0 : ℝ) 1) :
(∫ y in (-1 : ℝ)..1, (∑ k, w k * (if y ≤ q k then 1 else 0)) *
(∑ l, w' l * (if y ≤ q' l then 1 else 0))) =
∑ k, ∑ l, w k * w' l * (1 + min (q k) (q' l)) ∧
(∫ y in (-1 : ℝ)..1, (∑ k, w k * (if y ≤ q k then 1 else 0)) ^ 2) =
∑ k, ∑ k', w k * w k' * (1 + min (q k) (q k')) := by sorry
end LearnVsOpt
Source
Fikioris, Sivan & Tardos, Learning vs. Optimizing Players in Budgeted Games, arXiv:2611.05580, (6), p.9
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.