AFTD Auto-Formalizing Theoretical Domains

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

/-- 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
See it in the graphDiscuss this resultChallenge it