AFTD Auto-Formalizing Theoretical Domains

droop_monroe_violates_droop_pjr_plus_of_not_dvd

theoremverifiedformalization

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.

  1. 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+.

    line 5

      refine ⟨by decide, ⟨![some 1, some 1, none, some 2], ?_, ?_⟩, ?_⟩
  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.

    line 6

      · unfold is_droop_valid_assignment; decide
  3. 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, π).

    lines 7–13

    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
  4. 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.

    lines 14–16

    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).

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

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