hare_monroe_satisfies_droop_jr
theoremverifiedoriginal
Every committee selected by the (Hare) Monroe rule satisfies Droop-JR, for all n and k. This answers the open question of Justified Representation: From Hare to Droop (arXiv:2508.00811, App., after Prop. 2), which proved it only when k divides n.
Statement
theorem hare_monroe_satisfies_droop_jr {n m : ℕ} (A : Fin n → Finset (Fin m)) (k : ℕ)
(W : Finset (Fin m)) (hW : is_hare_monroe_committee A k W) : is_droop_jr A k W- Related work
- answers the open case of Justified Representation: From Hare to Droop, arXiv:2508.00811, App., after Prop. 2 / Table 1 note d (Monroe satisfies Droop-JR when k divides n; other n, k open): holds for all n and k
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- is_hare_monroe_committeeW is a winning committee of the (Hare) Monroe rule: some Hare-valid assignment for W has Monroe score at least that of every Hare-valid…
- is_droop_jrDroop-JR: every group S of voters with |S| > n/(k+1) that jointly approves some candidate contains a voter who approves some member of W.
- monroe_exists_heavyCounting step: if (W, π) is Hare-valid and |S| > n/(k+1), then some c ∈ W satisfies |π⁻¹(c)| < min(|π⁻¹(c)|, |S|) + |π⁻¹(c) ∩ S|.
- monroe_exchangeExchange step: replacing c ∈ W by c ∉ W approved by all of S (no member of S being satisfied by π) yields a Hare-valid assignment whose…
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.
/-- Every committee selected by the (Hare) Monroe rule satisfies Droop-JR, for all n and k. This answers the open question of Justified Representation: From Hare to Droop (arXiv:2508.00811, App., after Prop. 2), which proved it only when k divides n. -/theorem hare_monroe_satisfies_droop_jr {n m : ℕ} (A : Fin n → Finset (Fin m)) (k : ℕ) (W : Finset (Fin m)) (hW : is_hare_monroe_committee A k W) : is_droop_jr A k W := by obtain ⟨π, hv, hopt⟩ := hW intro S hS ⟨c', hc'⟩ by_contra hno push Not at hno have hun : ∀ i ∈ S, π i ∉ A i := fun i hi h => hno i hi (π i) (hv.2.1 i) h have hSne : S.Nonempty := by rw [← Finset.card_pos] rcases Nat.eq_zero_or_pos S.card with h | h · rw [h] at hS; simp at hS · exact h obtain ⟨i₀, hi₀⟩ := hSne have hc'W : c' ∉ W := fun h => hno i₀ hi₀ c' h (hc' i₀ hi₀) obtain ⟨c, hcW, hheavy⟩ := monroe_exists_heavy k W π hv S hS obtain ⟨π', hv', hsc⟩ := monroe_exchange A k W π hv c c' hcW hc'W S hc' hun have hle := hopt _ π' hv' have hP : ((Finset.univ.filter fun i => π i = c).filter fun i => i ∉ S).card + (S.filter fun i => π i = c).card = (Finset.univ.filter fun i => π i = c).card := by have : (S.filter fun i => π i = c).card = ((Finset.univ.filter fun i => π i = c).filter fun i => i ∈ S).card := by congr 1; ext v; simp [and_comm] rw [this, add_comm]; exact Finset.card_filter_add_card_filter_not _ omega