AFTD Auto-Formalizing Theoretical Domains

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

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