Theorem 9, p. 14 — CMP with confidence c ∈ [0,1) is √(2c²+2)/(1+c)-consistent and √(2c²+2)/(1−c)-robust for the utilitarian cost
ProvedLearnAugFL.CMP.theorem_9Throughout, carries the Euclidean distance ; is a profile of preferred locations; is a confidence parameter with an integer; is the utilitarian social cost; is an optimal (cost-minimizing) location; and is the location chosen by the Coordinatewise Median with Predictions (CMP): each coordinate is the lower median of the values formed by the agents' coordinates and copies of the prediction's coordinate. The ratio is .
Let , let with an integer, and let be any profile of points in .
- Consistency. For every optimal location of , when the prediction is correct (),
- Robustness. For every prediction and every optimal location of ,
At CMP is the coordinatewise median and both bounds equal ; as consistency approaches while robustness degrades. Lemma 8 shows both bounds are attained.
Formalization Note The approximation-ratio statements are cross-multiplied, which avoids the of a unanimous profile (where both sides are ). The maximum over ranges over all with an integer (Admissible c n k, copies of the prediction). The optimal location is any minimizer IsOpt P o of ; the consistency clause holds for each of them. CMP uses the lower median of the values, as in the paper.
import Mathlib import Definitions.Def_LearnAugFL_CMP_Setting
namespace LearnAugFL.CMP
theorem theorem_9 (c : ℝ) (hc0 : 0 ≤ c) (hc1 : c < 1) (n k : ℕ) (hnk : Admissible c n k)
(P : Fin n → Pt) :
(∀ o : Pt, IsOpt P o →
ucost P (cmp P o k) ≤ Real.sqrt (2 * c ^ 2 + 2) / (1 + c) * ucost P o) ∧
(∀ ô o : Pt, IsOpt P o →
ucost P (cmp P ô k) ≤ Real.sqrt (2 * c ^ 2 + 2) / (1 - c) * ucost P o) := by sorry
end LearnAugFL.CMP
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.