droop_monroe_violates_droop_pjr_plus_of_not_dvd
Without the assumption that k + 1 divides n, the Droop Monroe rule can output a committee violating Droop-PJR+: with n = 4 voters, k = 2 and ballots {1,3}, {1,3}, {3}, {2}, the committee {1, 2} is a Droop Monroe winner (a Droop-valid assignment scores 3, the most possible), but the group of the first three voters (2·4 < 3·3) jointly approves the unelected candidate 3 and collectively approves only one member of the committee.
Statement
theorem droop_monroe_violates_droop_pjr_plus_of_not_dvd :
¬ (2 + 1) ∣ 4 ∧
is_droop_monroe_committee (![{1, 3}, {1, 3}, {3}, {2}] : Fin 4 → Finset (Fin 4)) 2 {1, 2} ∧
¬ is_droop_pjr_plus (![{1, 3}, {1, 3}, {3}, {2}] : Fin 4 → Finset (Fin 4)) 2 {1, 2}- Formalizes
- Justified Representation: From Hare to Droop, arXiv:2508.00811, Proposition 4: Droop Monroe does not satisfy Droop-PJR if k + 1 does not divide n, and Droop-PJR+ implies Droop-PJR. The rule's definitions follow arXiv:2508.00811 (Def. 11, Def. 16). This instance (four voters, k = 2) was found by the agents' Prover when it refuted droop_monroe_satisfies_droop_pjr_plus_general.
- Verified
- 09 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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_pjr_plusDroop-PJR+ (arXiv:2508.00811, Def. 11): for every ℓ ∈ [k], every group S with |S| > ℓn/(k+1) jointly approving a candidate outside W…
- droop_monroe_score_leA Droop-valid assignment scores at most n - ⌊n/(k+1)⌋, since the dummy voters are unsatisfied.
- 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.
The proof, explained
The proof constructs a counterexample showing that the Droop Monroe rule can fail Droop-PJR+ when k + 1 does not divide n, using n = 4 voters and target committee size k = 2. It demonstrates that the committee {1, 2} is a Droop Monroe winner by providing an explicit valid assignment that scores 3, which is the maximum score any valid assignment can achieve on 4 voters. It then shows that {1, 2} violates Droop-PJR+ on the coalition of the first three voters: while these voters qualify for 2 seats and jointly approve unelected candidate 3, they collectively approve only a single member of the elected committee.
3 does not divide 4, and the assignment π = (some 1, some 1, none, some 2) is introduced as a candidate witness that {1, 2} is a Droop-Monroe committee.
We split the conjunction into three goals. First, 2 + 1 does not divide 4 (that is, 3 does not divide 4) is verified by direct calculation using `decide`. Second, to establish that {1, 2} is a Droop-Monroe committee, we supply the concrete assignment π assigning voter 0 to candidate 1, voter 1 to candidate 1, leaving voter 2 unassigned (none), and assigning voter 3 to candidate 2. This leaves proving that π is Droop-valid, that π achieves maximal score, and that {1, 2} violates Droop-PJR+.
refine ⟨by decide, ⟨![some 1, some 1, none, some 2], ?_, ?_⟩, ?_⟩
The assignment π is a Droop-valid assignment for committee size k = 2 and committee W = {1, 2}.
Unfolding the definition of `is_droop_valid_assignment`, we must verify: {1, 2} has cardinality 2; every assigned candidate belongs to {1, 2}; each candidate in {1, 2} is assigned between ⌊4 / 3⌋ = 1 and ⌊(4 + 2) / 3⌋ = 2 voters (candidate 1 receives 2 voters, candidate 2 receives 1); and exactly ⌊4 / 3⌋ = 1 voter is unassigned (voter 2). Since every condition is a decidable predicate on finite sets, `decide` verifies them directly.
· unfold is_droop_valid_assignment; decide
The assignment π achieves the maximum possible score among all Droop-valid assignments (namely 3), confirming that {1, 2} is a Droop-Monroe committee.
Given any committee W' and Droop-valid assignment π' (`intro W' π' hv'`), the lemma `droop_monroe_score_le` implies that score(A, π') + ⌊4 / 3⌋ ≤ 4, which simplifies using `norm_num` to score(A, π') ≤ 3. Meanwhile, unfolding `droop_monroe_score`, `decide` verifies that the score of our assignment π is exactly 3, since voters 0, 1, and 3 are assigned to candidates they approve (1 ∈ A(0), 1 ∈ A(1), and 2 ∈ A(3)). Linear integer arithmetic (`omega`) then concludes score(A, π') ≤ score(A, π).
uses
droop_monroe_score_le· intro W' π' hv' have h := droop_monroe_score_le (![{1, 3}, {1, 3}, {3}, {2}] : Fin 4 → Finset (Fin 4)) 2 W' π' hv' have h2 : droop_monroe_score (![{1, 3}, {1, 3}, {3}, {2}] : Fin 4 → Finset (Fin 4)) ![some 1, some 1, none, some 2] = 3 := by unfold droop_monroe_score; decide rw [h2]; norm_num at h; omega
The committee {1, 2} violates Droop-PJR+.
Assuming for contradiction that {1, 2} satisfies Droop-PJR+ (`intro h`), we instantiate the definition with ℓ = 2 and the coalition of the first three voters S = {0, 1, 2}. The required bounds hold: 1 ≤ 2 ≤ 2 (using `le_rfl`) and ℓ · n = 2 · 4 = 8 < (2 + 1) · |S| = 3 · 3 = 9. Furthermore, candidate 3 is not in {1, 2} and is approved by every voter in S (3 ∈ A(0), A(1), A(2)). Thus Droop-PJR+ requires that at least ℓ = 2 members of {1, 2} be approved by some voter in S. However, the only committee member approved by anyone in S is candidate 1 (candidate 2 is approved only by voter 3), so only 1 committee member is represented. This gives the contradiction 2 ≤ 1, which `decide` refutes.
uses
le_rfl· intro h have := h 2 (by norm_num) le_rfl {0, 1, 2} (by decide) ⟨3, by decide, by decide⟩ revert this; decide
droop_monroe_score_le- For any approval profile A and Droop-valid assignment π with parameters n and k, the Droop-Monroe score of π plus ⌊n / (k + 1)⌋ is at most n.
le_rfl- Inequality on a preorder is reflexive: every element is less than or equal to itself (a ≤ a).
- Because the voter set and candidate set are small and finite, several steps (evaluating set sizes, checking assignment validity, and evaluating scores) rely on Lean's `decide` tactic for mechanical boolean evaluation.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
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.
theorem droop_monroe_violates_droop_pjr_plus_of_not_dvd : ¬ (2 + 1) ∣ 4 ∧ is_droop_monroe_committee (![{1, 3}, {1, 3}, {3}, {2}] : Fin 4 → Finset (Fin 4)) 2 {1, 2} ∧ ¬ is_droop_pjr_plus (![{1, 3}, {1, 3}, {3}, {2}] : Fin 4 → Finset (Fin 4)) 2 {1, 2} := by refine ⟨by decide, ⟨![some 1, some 1, none, some 2], ?_, ?_⟩, ?_⟩ · unfold is_droop_valid_assignment; decide · intro W' π' hv' have h := droop_monroe_score_le (![{1, 3}, {1, 3}, {3}, {2}] : Fin 4 → Finset (Fin 4)) 2 W' π' hv' have h2 : droop_monroe_score (![{1, 3}, {1, 3}, {3}, {2}] : Fin 4 → Finset (Fin 4)) ![some 1, some 1, none, some 2] = 3 := by unfold droop_monroe_score; decide rw [h2]; norm_num at h; omega · intro h have := h 2 (by norm_num) le_rfl {0, 1, 2} (by decide) ⟨3, by decide, by decide⟩ revert this; decide