Lemma 15, p. 20 — two distinct points on the same open half-axis with the optimum off the axes: there is a strictly worse instance
ProvedLearnAugFL.CMP.lemma_15Throughout, 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 be a profile with optimal location , , , and suppose two agents have distinct points on the same (open) half-axis , , or . Then:
- (consistency) if , there is an instance (any number of agents, the same ) with optimal location such that ;
- (robustness) if , there is an instance with optimal location such that .
The lemma forces the worst case to have at most one cluster per half-axis (property 4(a) of the CA family).
Formalization Note The optimal location is taken as any with IsOpt P o (a minimizer of ; it is unique unless the points are collinear). The confidence enters through Admissible c n k: and copies of the prediction. Ratios are real quotients ratio P ô o k; on every family used here the optimal cost is positive (if all points sat at , CMP would return because ), so no ratio is a junk . The paper's half-axes contain the origin; the proof takes both points strictly inside the half-axis (), and that is the version stated here.
import Mathlib import Definitions.Def_LearnAugFL_CMP_Setting
namespace LearnAugFL.CMP
theorem lemma_15 (c : ℝ) (hc0 : 0 ≤ c) (hc1 : c < 1) {n k : ℕ} (hnk : Admissible c n k)
(P : Fin n → Pt) (o : Pt) (hP : IsOpt P o) (ho0 : 0 < o 0) (ho1 : 0 < o 1)
(hpair : ∃ i j : Fin n, P i ≠ P j ∧
((posX' (P i) ∧ posX' (P j)) ∨ (negX' (P i) ∧ negX' (P j)) ∨
(posY' (P i) ∧ posY' (P j)) ∨ (negY' (P i) ∧ negY' (P j)))) :
(cmp P o k = 0 → ∃ (m k' : ℕ) (Q : Fin m → Pt) (oQ : Pt),
Admissible c m k' ∧ IsOpt Q oQ ∧ ratio P o o k < ratio Q oQ oQ k') ∧
(cmp P 0 k = 0 → ∃ (m k' : ℕ) (Q : Fin m → Pt) (oQ : Pt),
Admissible c m k' ∧ IsOpt Q oQ ∧ ratio P 0 o k < ratio Q 0 oQ k') := by sorry
end LearnAugFL.CMP
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.