Lemma 18, pp. 20–21 — from an OA instance to a COA instance without improving the ratio
ProvedLearnAugFL.CMP.lemma_18Throughout, 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 .
Fix .
- (consistency) For every with optimal location there is an instance with optimal location such that either , or (so ) and .
- (robustness) For every with optimal location there is with optimal location such that either , or and .
Together with Lemmas 24–25 this moves the worst case into the COA 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 page's robustness clause contains the typo "r(P, (0, 0, c)", read as .
import Mathlib import Definitions.Def_LearnAugFL_CMP_Setting
namespace LearnAugFL.CMP
theorem lemma_18 (c : ℝ) (hc0 : 0 ≤ c) (hc1 : c < 1) :
(∀ (n k : ℕ) (P : Fin n → Pt) (o : Pt), OA_C c n k P o →
∃ (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' ∨
(COA_C c m k' Q ∧ oQ = !₂[0, 1] ∧ ratio P o o k ≤ ratio Q oQ oQ k'))) ∧
(∀ (n k : ℕ) (P : Fin n → Pt) (o : Pt), OA_R c n k P o →
∃ (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' ∨
(COA_R c m k' Q ∧ oQ = !₂[0, 1] ∧ 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.