monroe_exists_heavy
theoremverified
Counting step: if (W, π) is Hare-valid and |S| > n/(k+1), then some c ∈ W satisfies |π⁻¹(c)| < min(|π⁻¹(c)|, |S|) + |π⁻¹(c) ∩ S|.
Statement
theorem monroe_exists_heavy {n m : ℕ} (k : ℕ) (W : Finset (Fin m)) (π : Fin n → Fin m) (hv : is_hare_valid_assignment k W π) (S : Finset (Fin n)) (hS : n < (k + 1) * S.card) : ∃ c ∈ W, (Finset.univ.filter fun i => π i = c).card < min (Finset.univ.filter fun i => π i = c).card S.card + (S.filter fun i => π i = c).card
- Source
- step towards hare_monroe_satisfies_droop_jr (Monroe and Droop-JR, open case of Justified Representation: From Hare to Droop, arXiv:2508.00811)
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- is_hare_valid_assignmentA Hare-valid Monroe assignment (arXiv:2508.00811, Def. 16): W has k members, π sends every voter into W, and every c ∈ W receives between…
- monroe_ceil_le_floor_succ⌈n/k⌉ ≤ ⌊n/k⌋ + 1, written (n + k - 1)/k ≤ n/k + 1, for all natural n, k.
- Used by 1
- hare_monroe_satisfies_droop_jrEvery committee selected by the (Hare) Monroe rule satisfies Droop-JR, for all n and k. This answers the open question of Justified…
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- The counting step: if `S` has more than `n/(k+1)` voters, some committee member `c` has `|π⁻¹(c)| < min(|π⁻¹(c)|, |S|) + |π⁻¹(c) ∩ S|`. -/theorem monroe_exists_heavy {n m : ℕ} (k : ℕ) (W : Finset (Fin m)) (π : Fin n → Fin m) (hv : is_hare_valid_assignment k W π) (S : Finset (Fin n)) (hS : n < (k + 1) * S.card) : ∃ c ∈ W, (Finset.univ.filter fun i => π i = c).card < min (Finset.univ.filter fun i => π i = c).card S.card + (S.filter fun i => π i = c).card := by obtain ⟨hW, hmap, hload⟩ := hv by_contra hcon push Not at hcon set x := S.card with hx have ht : ∀ c ∈ W, (S.filter fun i => π i = c).card ≤ (Finset.univ.filter fun i => π i = c).card - x := by intro c hc; have := hcon c hc; omega have hsumS : ∑ c ∈ W, (S.filter fun i => π i = c).card = x := (Finset.card_eq_sum_card_fiberwise (fun i _ => hmap i)).symm have hsumN : ∑ c ∈ W, (Finset.univ.filter fun i => π i = c).card = n := by rw [← Finset.card_eq_sum_card_fiberwise (fun i _ => hmap i)]; simp have hle : x ≤ ∑ c ∈ W, ((Finset.univ.filter fun i => π i = c).card - x) := calc x = ∑ c ∈ W, (S.filter fun i => π i = c).card := hsumS.symm _ ≤ _ := Finset.sum_le_sum ht have hxpos : 0 < x := by rcases Nat.eq_zero_or_pos x with h | h · rw [h] at hS; simp at hS · exact h by_cases hsmall : x ≤ n / k · have hge : ∀ c ∈ W, x ≤ (Finset.univ.filter fun i => π i = c).card := fun c hc => hsmall.trans (hload c hc).1 have hsum : ∑ c ∈ W, ((Finset.univ.filter fun i => π i = c).card - x) + k * x = n := by have h := Finset.sum_congr rfl fun c hc => Nat.sub_add_cancel (hge c hc) rw [Finset.sum_add_distrib, Finset.sum_const, smul_eq_mul, hW] at h omega have : (k + 1) * x = k * x + x := by ring omega · have hz : ∀ c ∈ W, (Finset.univ.filter fun i => π i = c).card - x = 0 := by intro c hc have := (hload c hc).2 have := monroe_ceil_le_floor_succ n k omega rw [Finset.sum_eq_zero hz] at hle omega