droop_monroe_tie_violates_droop_ejr_plus_fjr
theoremverifiedoriginal
With ties, the Droop Monroe rule can output a committee violating Droop-EJR+ and Droop-FJR even when k + 1 divides n: n = 3, k = 2, ballots {0,1,3}, {0,1,3}, {0,2,3}, winning committee {1, 2}.
Statement
theorem droop_monroe_tie_violates_droop_ejr_plus_fjr :
(2 + 1) ∣ 3 ∧ is_droop_monroe_committee droop_monroe_tie_ballot 2 {1, 2} ∧
¬ is_droop_ejr_plus droop_monroe_tie_ballot 2 {1, 2} ∧
¬ is_droop_fjr droop_monroe_tie_ballot 2 {1, 2}- Related work
- answers the open Droop-EJR+ / Droop-FJR entries for Droop Monroe in Justified Representation: From Hare to Droop, arXiv:2508.00811, Table 1, negatively when ties are broken adversarially (n = 3, k = 2); whether some winning committee always satisfies them remains open
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- is_droop_valid_assignmentA Droop-valid Monroe assignment (arXiv:2508.00811, Def. 16): |W| = k, each voter goes to a member of W or to the dummy (none), each c ∈ W…
- droop_monroe_scoreMonroe score of a Droop assignment: the number of voters sent to a non-dummy candidate they approve.
- is_droop_monroe_committeeW is a winning committee of the Droop Monroe rule: some Droop-valid assignment for W scores at least as much as every Droop-valid…
- is_droop_ejr_plusDroop-EJR+ (arXiv:2508.00811, Def. 12): for every ℓ ∈ [k], every group S with |S| > ℓn/(k+1) jointly approving a candidate outside W has a…
- is_droop_fjrDroop-FJR (arXiv:2508.00811, Def. 10): every Droop weakly (ℓ, T)-cohesive group (each member approves ≥ ℓ members of T and |S| >…
- droop_monroe_tie_ballotBallots of the Droop Monroe tie example: three voters approving {0,1,3}, {0,1,3} and {0,2,3}.
- droop_monroe_score_leA Droop-valid assignment scores at most n - ⌊n/(k+1)⌋, since the dummy voters are unsatisfied.
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.
/-- With ties, the Droop Monroe rule can output a committee that violates Droop-EJR+ and Droop-FJR even when `k + 1` divides `n`: three voters, `k = 2`, ballots {0,1,3}, {0,1,3}, {0,2,3}; every committee scores 2, and `W = {1, 2}` gives each voter only one approved member although all three jointly approve the two candidates 0 and 3. -/theorem droop_monroe_tie_violates_droop_ejr_plus_fjr : (2 + 1) ∣ 3 ∧ is_droop_monroe_committee droop_monroe_tie_ballot 2 {1, 2} ∧ ¬ is_droop_ejr_plus droop_monroe_tie_ballot 2 {1, 2} ∧ ¬ is_droop_fjr droop_monroe_tie_ballot 2 {1, 2} := by refine ⟨by norm_num, ⟨![some 1, none, some 2], ?_, ?_⟩, ?_, ?_⟩ · unfold is_droop_valid_assignment; decide · intro W' π' hv' have h := droop_monroe_score_le droop_monroe_tie_ballot 2 W' π' hv' have h2 : droop_monroe_score droop_monroe_tie_ballot ![some 1, none, some 2] = 2 := by unfold droop_monroe_score; decide rw [h2]; norm_num at h; omega · intro h obtain ⟨i, _, hi⟩ := h 2 (by norm_num) le_rfl Finset.univ (by simp) ⟨0, by decide, by decide⟩ revert hi; revert i; decide · intro h obtain ⟨i, _, hi⟩ := h 2 (by norm_num) le_rfl {0, 3} Finset.univ (by decide) (by simp) revert hi; revert i; decide