droop_monroe_satisfies_droop_jr
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.
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.
intro S hS ⟨c, hc⟩ by_contra hno push Not at hno obtain ⟨π, hv, hopt⟩ := hW
The group S is nonempty.
Since (k + 1) * |S| > n ≥ 0, |S| cannot be zero. A finite set with positive cardinality is nonempty.
uses
Finset.card_pos,Nat.eq_zero_or_poshave 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
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.
have hcW : c ∉ W := by intro hcW obtain ⟨i, hi⟩ := hSne exact hno i hi c hcW (hc i hi)
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.
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
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.
uses
Finset.card_le_card,Nat.mul_le_mul_left,Nat.mul_div_lehave 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
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.
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₀
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 π.
uses
droop_monroe_exchangeobtain ⟨π', hv', hsc⟩ := droop_monroe_exchange A k W π hv c₀ c hc₀W hcW S hc hunThe 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(π).
have hopt_le := hopt _ π' hv'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.
uses
Nat.div_lt_iff_lt_mul,Nat.succ_pos,mul_commset 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
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|.
uses
Nat.div_le_div_right,Nat.add_div_right,Nat.succ_poshave 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
|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.
uses
min_eq_lefthave 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
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.
uses
Finset.card_filter_add_card_filter_not,add_commhave 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
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.
uses
Finset.card_poshave 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⟩
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.
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.
- The upper quota constraint on each candidate's assigned voters is written as $(n + k) / (k + 1)$ in Lean natural number division, representing the ceiling $\lceil n / (k + 1) \rceil$.
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.
/-- 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