AFTD Auto-Formalizing Theoretical Domains

droop_monroe_satisfies_droop_jr

theoremverifiedoriginal

Every committee W of size k selected by the Droop Monroe rule satisfies Droop-JR: every voter group S of size strictly greater than n/(k+1) that jointly approves some candidate contains a voter who approves at least one candidate in W.

Statement

theorem droop_monroe_satisfies_droop_jr (n m : ℕ) (A : Fin n → Finset (Fin m)) (k : ℕ)
    (W : Finset (Fin m)) (hW : is_droop_monroe_committee A k W) :
    is_droop_jr A k W
Related work
arXiv:2508.00811, Table 1
Verified
20 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • 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_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.
  • droop_monroe_scoreMonroe score of a Droop assignment: the number of voters sent to a non-dummy candidate they approve.
  • droop_monroe_exchangeExchange step for Droop assignments: swapping c₀ ∈ W for c ∉ W approved by all of S (no member of S satisfied) gives a Droop-valid…

Read back from the Lean

For any number of voters n and candidates m, any approval voting profile A (assigning to each voter i : Fin n a finite set of approved candidates A(i) ⊆ Fin m), any committee size k, and any candidate subset W ⊆ Fin m: if W is a Droop-Monroe committee of size k for profile A, then W satisfies Droop Justified Representation (Droop JR) for A and k.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof proceeds by contradiction: suppose a voter group S of size strictly greater than the Droop quota n/(k+1) jointly approves a candidate c, yet no voter in S approves any candidate in the optimal Droop-Monroe committee W. Since the number of unassigned voters under any valid Droop-Monroe assignment π is at most ⌊n/(k+1)⌋ < |S|, some voter i₀ ∈ S must be assigned to a committee member c₀ ∈ W. Exchanging c₀ for c yields a new valid assignment π' whose score improvement is bounded below by the exchange lemma, and because the cluster size of c₀ is at most the quota upper bound ⌊(n+k)/(k+1)⌋ ≤ |S|, this exchange strictly increases the Monroe score, contradicting the optimality of W.

  1. Assume for contradiction that Droop-JR is violated for a Droop-Monroe committee W.

    We introduce a voter group S with (k + 1) * |S| > n jointly approving a candidate c, and suppose for contradiction that no voter in S approves any candidate in W. We unpack the hypothesis that W is a Droop-Monroe committee to obtain a valid assignment π whose Monroe score is maximal among all valid committees and assignments.

    lines 5–8

      intro S hS ⟨c, hc⟩
      by_contra hno
      push Not at hno
      obtain ⟨π, hv, hopt⟩ := hW
  2. The group S is nonempty.

    Since (k + 1) * |S| > n ≥ 0, |S| cannot be zero. A finite set with positive cardinality is nonempty.

    lines 9–13

    uses Finset.card_pos, Nat.eq_zero_or_pos

      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
  3. The jointly approved candidate c is not in W.

    If c were in W, then every voter in S (and S is nonempty) would approve a candidate in W, contradicting the assumption that Droop-JR is violated.

    lines 14–17

      have hcW : c ∉ W := by
        intro hcW
        obtain ⟨i, hi⟩ := hSne
        exact hno i hi c hcW (hc i hi)
  4. No voter in S is assigned to an approved candidate under π.

    Every candidate assigned under a valid assignment belongs to W. Since voters in S approve no candidate in W, they cannot approve their assigned candidates.

    lines 18–21

      have hun : ∀ i ∈ S, ¬ ∃ d, π i = some d ∧ d ∈ A i := by
        intro i hi ⟨d, hd, hdA⟩
        have hdW : d ∈ W := hv.2.1 i d hd
        exact hno i hi d hdW hdA
  5. At least one voter in S is assigned to a candidate under π.

    Suppose for contradiction that all voters in S were unassigned (π(i) = none). Then S would be a subset of the unassigned voters. By definition of a valid Droop-Monroe assignment, the number of unassigned voters is exactly ⌊n / (k + 1)⌋, which implies (k + 1) * |S| ≤ (k + 1) * ⌊n / (k + 1)⌋ ≤ n, contradicting the hypothesis that (k + 1) * |S| > n.

    lines 22–32

    uses Finset.card_le_card, Nat.mul_le_mul_left, Nat.mul_div_le

      have hS_not_all_none : ∃ i ∈ S, π i ≠ none := by
        by_contra hall
        push Not at hall
        have hsub : S ⊆ Finset.univ.filter fun i => π i = none := by
          intro i hi
          simp [hall i hi]
        have hle := Finset.card_le_card hsub
        rw [hv.2.2.2] at hle
        have : (k + 1) * S.card ≤ (k + 1) * (n / (k + 1)) := Nat.mul_le_mul_left (k + 1) hle
        have : (k + 1) * (n / (k + 1)) ≤ n := Nat.mul_div_le n (k + 1)
        omega
  6. There exist a voter i₀ ∈ S and a committee candidate c₀ ∈ W such that π(i₀) = c₀.

    Since not all voters in S are unassigned, some i₀ ∈ S has π(i₀) ≠ none, so π(i₀) = some c₀. By the validity of assignment π, any assigned candidate c₀ must be in W.

    lines 33–35

    uses Option.ne_none_iff_exists'

      obtain ⟨i₀, hi₀, hni₀⟩ := hS_not_all_none
      obtain ⟨c₀, hc₀⟩ := Option.ne_none_iff_exists'.1 hni₀
      have hc₀W : c₀ ∈ W := hv.2.1 i₀ c₀ hc₀
  7. Exchanging c₀ for c produces a valid assignment π' on (W \ {c₀}) ∪ {c} satisfying the exchange score inequality.

    Applying droop_monroe_exchange with c₀ ∈ W, c ∉ W, and voter set S yields a valid assignment π' for the updated committee, satisfying score(π) + min(|R|, |S|) ≤ score(π') + |R \ S|, where R is the set of voters assigned to c₀ under π.

    line 36

    uses droop_monroe_exchange

      obtain ⟨π', hv', hsc⟩ := droop_monroe_exchange A k W π hv c₀ c hc₀W hcW S hc hun
  8. The score of the new assignment cannot exceed that of π.

    By the optimality of W and π under the Droop-Monroe rule, any valid assignment π' has score(π') ≤ score(π).

    line 37

      have hopt_le := hopt _ π' hv'
  9. Let R = {i | π(i) = c₀}; then |R| ≤ ⌊(n + k) / (k + 1)⌋ and ⌊n / (k + 1)⌋ < |S|.

    Validity of π imposes the upper quota constraint |R| ≤ ⌊(n + k) / (k + 1)⌋ on candidate c₀ ∈ W. Furthermore, the condition n < (k + 1) * |S| is equivalent to ⌊n / (k + 1)⌋ < |S| by integer division properties.

    lines 38–42

    uses Nat.div_lt_iff_lt_mul, Nat.succ_pos, mul_comm

      set R := Finset.univ.filter fun i => π i = some c₀ with hR
      have hR_le_ceil : R.card ≤ (n + k) / (k + 1) := (hv.2.2.1 c₀ hc₀W).2
      have hfloor_lt : n / (k + 1) < S.card := by
        rw [Nat.div_lt_iff_lt_mul (Nat.succ_pos k), mul_comm]
        exact hS
  10. The upper quota bound satisfies ⌊(n + k) / (k + 1)⌋ ≤ |S|.

    Since n + k ≤ n + k + 1, we have ⌊(n + k) / (k + 1)⌋ ≤ ⌊(n + k + 1) / (k + 1)⌋ = ⌊n / (k + 1)⌋ + 1. Because ⌊n / (k + 1)⌋ < |S|, the strict inequality implies ⌊n / (k + 1)⌋ + 1 ≤ |S|.

    lines 43–48

    uses Nat.div_le_div_right, Nat.add_div_right, Nat.succ_pos

      have hceil_le_S : (n + k) / (k + 1) ≤ S.card := by
        have h1 : n + k ≤ n + (k + 1) := by omega
        have h2 : (n + k) / (k + 1) ≤ (n + (k + 1)) / (k + 1) := Nat.div_le_div_right h1
        have h3 : (n + (k + 1)) / (k + 1) = n / (k + 1) + 1 := Nat.add_div_right n (Nat.succ_pos k)
        rw [h3] at h2
        omega
  11. |R| ≤ |S|, so min(|R|, |S|) = |R| in the exchange inequality.

    Chaining |R| ≤ ⌊(n + k) / (k + 1)⌋ and ⌊(n + k) / (k + 1)⌋ ≤ |S| gives |R| ≤ |S|, which simplifies min(|R|, |S|) to |R| in the exchange score inequality.

    lines 49–51

    uses min_eq_left

      have hR_le_S : R.card ≤ S.card := hR_le_ceil.trans hceil_le_S
      have hmin : min R.card S.card = R.card := min_eq_left hR_le_S
      rw [hmin] at hsc
  12. The size of R partitions as |R| = |R \ S| + |R ∩ S|.

    Splitting R into the voters outside S and those inside S, the size of R is the sum of the cardinalities of these disjoint subsets.

    lines 52–55

    uses Finset.card_filter_add_card_filter_not, add_comm

      have hsplit : R.card = (R.filter fun i => i ∉ S).card + (R.filter fun i => i ∈ S).card := by
        have := (Finset.card_filter_add_card_filter_not (s := R) (p := fun i => i ∈ S)).symm
        rw [add_comm] at this
        exact this
  13. The intersection R ∩ S contains i₀, so |R ∩ S| > 0.

    Because i₀ ∈ S and π(i₀) = c₀ (so i₀ ∈ R), voter i₀ belongs to R ∩ S, making the set nonempty and its cardinality strictly positive.

    lines 56–58

    uses Finset.card_pos

      have hin : i₀ ∈ R.filter fun i => i ∈ S := by
        simp [hR, hc₀, hi₀]
      have hpos : 0 < (R.filter fun i => i ∈ S).card := Finset.card_pos.2 ⟨i₀, hin⟩
  14. The score bounds yield a contradiction, completing the proof.

    Combining score(π') ≤ score(π) with score(π) + |R \ S| + |R ∩ S| ≤ score(π') + |R \ S| implies |R ∩ S| ≤ 0, contradicting |R ∩ S| > 0.

    line 59

      omega
Finset.card_pos
A finite set has strictly positive cardinality if and only if it is nonempty.
Nat.eq_zero_or_pos
Every natural number is either equal to zero or strictly positive.
Finset.card_le_card
A subset of a finite set has cardinality at most that of the superset.
Nat.mul_le_mul_left
Multiplying both sides of an inequality by a natural number preserves the inequality.
Nat.mul_div_le
For natural numbers m and n, the product n * ⌊m / n⌋ is at most m.
Option.ne_none_iff_exists'
An optional value is not none if and only if it is some x for some element x.
droop_monroe_exchange
Given an optimal Droop-Monroe committee and assignment, swapping a member c₀ with an external candidate c approved by S yields a valid assignment π' whose score satisfies score(π) + min(|R|, |S|) ≤ score(π') + |R \ S|, where R is the set of voters assigned to c₀.
Nat.div_lt_iff_lt_mul
For positive k, ⌊x / k⌋ < y is equivalent to x < y * k.
Nat.succ_pos
The successor of any natural number is strictly positive (0 < n + 1).
mul_comm
Multiplication of natural numbers is commutative.
Nat.div_le_div_right
Dividing both sides of an inequality by a common divisor preserves the inequality in integer division.
Nat.add_div_right
For positive z, integer division satisfies (x + z) / z = x / z + 1.
min_eq_left
If a ≤ b, then min a b = a.
Finset.card_filter_add_card_filter_not
The cardinality of a finite set equals the sum of the cardinalities of the elements satisfying a predicate and those satisfying its negation.
add_comm
Addition of natural numbers is commutative.

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

/-- Every winning committee under the Droop Monroe rule satisfies Droop-JR for all n and k. -/theorem droop_monroe_satisfies_droop_jr (n m : ℕ) (A : Fin n → Finset (Fin m)) (k : ℕ)    (W : Finset (Fin m)) (hW : is_droop_monroe_committee A k W) :    is_droop_jr A k W := by  intro S hS ⟨c, hc⟩  by_contra hno  push Not at hno  obtain ⟨π, hv, hopt⟩ := hW  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  have hcW : c ∉ W := by    intro hcW    obtain ⟨i, hi⟩ := hSne    exact hno i hi c hcW (hc i hi)  have hun : ∀ i ∈ S, ¬ ∃ d, π i = some d ∧ d ∈ A i := by    intro i hi ⟨d, hd, hdA⟩    have hdW : d ∈ W := hv.2.1 i d hd    exact hno i hi d hdW hdA  have hS_not_all_none : ∃ i ∈ S, π i ≠ none := by    by_contra hall    push Not at hall    have hsub : S ⊆ Finset.univ.filter fun i => π i = none := by      intro i hi      simp [hall i hi]    have hle := Finset.card_le_card hsub    rw [hv.2.2.2] at hle    have : (k + 1) * S.card ≤ (k + 1) * (n / (k + 1)) := Nat.mul_le_mul_left (k + 1) hle    have : (k + 1) * (n / (k + 1)) ≤ n := Nat.mul_div_le n (k + 1)    omega  obtain ⟨i₀, hi₀, hni₀⟩ := hS_not_all_none  obtain ⟨c₀, hc₀⟩ := Option.ne_none_iff_exists'.1 hni₀  have hc₀W : c₀ ∈ W := hv.2.1 i₀ c₀ hc₀  obtain ⟨π', hv', hsc⟩ := droop_monroe_exchange A k W π hv c₀ c hc₀W hcW S hc hun  have hopt_le := hopt _ π' hv'  set R := Finset.univ.filter fun i => π i = some c₀ with hR  have hR_le_ceil : R.card ≤ (n + k) / (k + 1) := (hv.2.2.1 c₀ hc₀W).2  have hfloor_lt : n / (k + 1) < S.card := by    rw [Nat.div_lt_iff_lt_mul (Nat.succ_pos k), mul_comm]    exact hS  have hceil_le_S : (n + k) / (k + 1) ≤ S.card := by    have h1 : n + k ≤ n + (k + 1) := by omega    have h2 : (n + k) / (k + 1) ≤ (n + (k + 1)) / (k + 1) := Nat.div_le_div_right h1    have h3 : (n + (k + 1)) / (k + 1) = n / (k + 1) + 1 := Nat.add_div_right n (Nat.succ_pos k)    rw [h3] at h2    omega  have hR_le_S : R.card ≤ S.card := hR_le_ceil.trans hceil_le_S  have hmin : min R.card S.card = R.card := min_eq_left hR_le_S  rw [hmin] at hsc  have hsplit : R.card = (R.filter fun i => i ∉ S).card + (R.filter fun i => i ∈ S).card := by    have := (Finset.card_filter_add_card_filter_not (s := R) (p := fun i => i ∈ S)).symm    rw [add_comm] at this    exact this  have hin : i₀ ∈ R.filter fun i => i ∈ S := by    simp [hR, hc₀, hi₀]  have hpos : 0 < (R.filter fun i => i ∈ S).card := Finset.card_pos.2 ⟨i₀, hin⟩  omega
See it in the graphDiscuss this resultChallenge it