rank_score_veto_core_opposition_cost_le
theoremverified
For every voter v who ranks c* strictly above a, the candidate distance d(a,c*) is at most twice the voter's own distance to c*; summing over those voters gives #{v : c* <_v a} * d(a,c*) at most twice the social cost of c*.
Statement
theorem rank_score_veto_core_opposition_cost_le : ∀ (C V : Type*) [Fintype C] [Fintype V] [PseudoMetricSpace (V ⊕ C)] (prof : V → LinearOrder C), is_consistent_pseudometric V C prof → ∀ (a c_star : C), ((Finset.univ.filter (fun v : V => (prof v).lt c_star a)).card : ℝ) * dist (Sum.inr a : V ⊕ C) (Sum.inr c_star : V ⊕ C) ≤ 2 * candidate_metric_social_cost V c_star
- Source
- step towards rank_score_veto_core_tightness_conjecture
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - is_consistent_pseudometricGiven types V and C, a pseudometric space instance on V ⊕ C, and an election profile prof : V → LinearOrder C assigning a linear order on…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - candidate_metric_social_costThe social cost of candidate c under a pseudometric space on V ⊕ C is the sum over all voters v in V of the distance between v and c.
- LinearOrder.toTotalPreorderEvery
- Used by 1
- not_rank_score_veto_core_target_of_side_count_boundThe statement
rank_score_veto_core_target_of_side_count_boundis false: The statement is false as stated. The scoring vector s has no…
- not_rank_score_veto_core_target_of_side_count_boundThe statement
Lean source view module on GitHub
/-- The voters who prefer c* to a pay for the candidate distance: #{v : c* <_v a} * dist(a,c*) <= 2 * SC(c*). -/ theorem rank_score_veto_core_opposition_cost_le : ∀ (C V : Type*) [Fintype C] [Fintype V] [PseudoMetricSpace (V ⊕ C)] (prof : V → LinearOrder C), is_consistent_pseudometric V C prof → ∀ (a c_star : C), ((Finset.univ.filter (fun v : V => (prof v).lt c_star a)).card : ℝ) * dist (Sum.inr a : V ⊕ C) (Sum.inr c_star : V ⊕ C) ≤ 2 * candidate_metric_social_cost V c_star := by intro C V _ _ _ prof hcons a c_star let D : ℝ := dist (Sum.inr a : V ⊕ C) (Sum.inr c_star : V ⊕ C) let W := Finset.univ.filter (fun v : V => (prof v).lt c_star a) have mono : ∀ (v : V) (x y : C), (prof v).le x y → dist (Sum.inl v : V ⊕ C) (Sum.inr y) ≤ dist (Sum.inl v : V ⊕ C) (Sum.inr x) := by intro v x y hxy let _ : LinearOrder C := prof v by_contra h rw [not_le] at h exact absurd (hcons v x y h) (not_lt.mpr hxy) have hv : ∀ v ∈ W, D ≤ 2 * dist (Sum.inl v : V ⊕ C) (Sum.inr c_star) := by intro v hvW have hlt : (prof v).lt c_star a := (Finset.mem_filter.mp hvW).2 have hle : (prof v).le c_star a := by let _ : LinearOrder C := prof v exact le_of_lt hlt have hmono := mono v c_star a hle have htri := dist_triangle (Sum.inr a : V ⊕ C) (Sum.inl v : V ⊕ C) (Sum.inr c_star : V ⊕ C) rw [dist_comm (Sum.inr a : V ⊕ C) (Sum.inl v : V ⊕ C)] at htri linarith have hsum : (∑ v ∈ W, D) ≤ ∑ v ∈ W, 2 * dist (Sum.inl v : V ⊕ C) (Sum.inr c_star) := Finset.sum_le_sum hv rw [Finset.sum_const, nsmul_eq_mul] at hsum have h_univ : (∑ v ∈ W, 2 * dist (Sum.inl v : V ⊕ C) (Sum.inr c_star)) ≤ ∑ v ∈ Finset.univ, 2 * dist (Sum.inl v : V ⊕ C) (Sum.inr c_star) := by apply Finset.sum_le_sum_of_subset_of_nonneg (Finset.subset_univ W) intro i _ _ positivity have h_cost : (∑ v ∈ Finset.univ, 2 * dist (Sum.inl v : V ⊕ C) (Sum.inr c_star)) = 2 * candidate_metric_social_cost V c_star := by rw [← Finset.mul_sum] rfl linarith