ejr_committee_exists
For every approval profile with at least one voter and every committee size k ≤ m, some committee of size k satisfies EJR (for instance the PAV committee).
Statement
theorem ejr_committee_exists :
∀ (n m : ℕ) (A : Fin n → Finset (Fin m)), 0 < n → ∀ k, k ≤ m →
∃ W, is_ejr_committee A k W- Formalizes
- Justified Representation in Approval-Based Committee Voting (arXiv:1407.8269), theorem that PAV satisfies EJR; recalled in arXiv:2007.01795; the one-size-at-a-time part of the committee-monotonicity question
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- is_ejr_committeeA committee W with |W| = k satisfies EJR if for every ℓ ≥ 1 and every ℓ-cohesive group G some voter i ∈ G has |A_i ∩ W| ≥ ℓ.
- is_ejr_cohesive_groupFor committee size k, a group G of the n voters is ℓ-cohesive if |G| ≥ ℓ·n/k and |∩_{i∈G} A_i| ≥ ℓ.
- Used by 1
- ejr_chain_candidates_le_threeEvery approval profile on at most three candidates admits an EJR committee chain.
The proof, explained
The theorem is established using a greedy cohesive group argument by strong induction on the voter set. For any set of voters S, one selects a cohesive subgroup G with maximum cohesion parameter ℓ, awards it ℓ unanimously approved candidates, and recursively solves the remaining voters S \ G. Applying this construction to the entire electorate yields a candidate set of size at most k satisfying Extended Justified Representation, which is then extended to a committee of size exactly k.
We set up strong induction on the voter set S with respect to strict inclusion.
The proof of the greedy cohesive auxiliary lemma proceeds by strong induction on the finite set of voters S using `Finset.strongInduction`. In the induction step, we assume the claim holds for all strict subsets t ⊂ S.
uses
Finset.strongInductionclassical induction S using Finset.strongInduction with | H S ih =>
Every cohesive group has parameter ℓ ≤ m, and we define the finite set P of all valid cohesive pairs (ℓ, G) with G ⊆ S.
Since candidates are elements of Fin m, the total candidate count is m, so any group unanimously approving ℓ candidates satisfies ℓ ≤ m by `Finset.card_le_univ`. We define P as the set of pairs (ℓ, G) in {1, ..., m} × 𝒫(S) such that G is an ℓ-cohesive group, and verify the membership condition `hmemP` for P.
uses
Finset.card_le_univ,Finset.mem_filter,Finset.mem_product,Finset.mem_Icc,Finset.mem_powersethave hle_m : ∀ ℓ G, is_ejr_cohesive_group A k ℓ G → ℓ ≤ m := fun ℓ G h => h.2.trans ((Finset.card_le_univ _).trans (by simp)) let P : Finset (ℕ × Finset (Fin n)) := ((Finset.Icc 1 m) ×ˢ S.powerset).filter fun p => is_ejr_cohesive_group A k p.1 p.2 have hmemP : ∀ ℓ G, (ℓ, G) ∈ P ↔ (1 ≤ ℓ ∧ G ⊆ S ∧ is_ejr_cohesive_group A k ℓ G) := by intro ℓ G simp only [P, Finset.mem_filter, Finset.mem_product, Finset.mem_Icc, Finset.mem_powerset] constructor · rintro ⟨⟨⟨h1, -⟩, h2⟩, h3⟩; exact ⟨h1, h2, h3⟩ · rintro ⟨h1, h2, h3⟩; exact ⟨⟨⟨h1, hle_m ℓ G h3⟩, h2⟩, h3⟩
Assuming P is non-empty, we choose a pair (ℓ, G) ∈ P maximizing ℓ, and establish that G is non-empty.
We split on whether P is non-empty. When P is non-empty, we pick a pair (ℓ, G) ∈ P maximizing ℓ. The group G cannot be empty: if G were empty, the cohesion bound ℓ * n ≤ |G| * k would imply ℓ * n ≤ 0, which contradicts ℓ ≥ 1 and n > 0 by linear arithmetic.
uses
Finset.nonempty_iff_ne_empty,Finset.card_empty,zero_mul,Nat.mul_posby_cases hP : P.Nonempty · obtain ⟨⟨ℓ, G⟩, hpP, hmax⟩ := P.exists_max_image Prod.fst hP obtain ⟨hℓ1, hGS, hcoh⟩ := (hmemP ℓ G).1 hpP have hGne : G.Nonempty := by rw [Finset.nonempty_iff_ne_empty] rintro rfl have h := hcoh.1 simp only [Finset.card_empty, zero_mul] at h have : 0 < ℓ * n := Nat.mul_pos hℓ1 hn omega
Applying the induction hypothesis to S \ G yields W', and choosing ℓ unanimously approved candidates C gives candidate set W' ∪ C for S.
Since G is non-empty and G ⊆ S, the remainder S \ G is a strict subset of S by `Finset.sdiff_ssubset`. By the induction hypothesis, there is a candidate set W' satisfying the bound and cohesive groups for S \ G. Since G is ℓ-cohesive, there is a set C of ℓ candidates unanimously approved by G (`Finset.exists_subset_card_eq`). We propose W' ∪ C as the witness for S.
uses
Finset.sdiff_ssubset,Finset.exists_subset_card_eqobtain ⟨W', hW'card, hW'⟩ := ih (S \ G) (Finset.sdiff_ssubset hGS hGne) obtain ⟨C, hCsub, hCcard⟩ := Finset.exists_subset_card_eq hcoh.2 refine ⟨W' ∪ C, ?_, ?_⟩
The candidate set W' ∪ C satisfies the quota bound |W' ∪ C| * n ≤ |S| * k.
By subadditivity of set size, |W' ∪ C| ≤ |W'| + ℓ. Multiplying by n and using the induction hypothesis |W'| * n ≤ |S \ G| * k together with the cohesion bound ℓ * n ≤ |G| * k, we obtain (|W'| + ℓ) * n ≤ (|S \ G| + |G|) * k. Since |S \ G| + |G| = |S|, this equals |S| * k.
uses
Finset.card_union_le,Finset.card_sdiff_add_card_eq_card,Nat.mul_le_mul_right,Nat.add_le_add,Nat.add_mul· have h1 : (W' ∪ C).card ≤ W'.card + ℓ := (Finset.card_union_le _ _).trans (by rw [hCcard]) have h2 : (S \ G).card + G.card = S.card := Finset.card_sdiff_add_card_eq_card hGS have hc := hcoh.1 calc (W' ∪ C).card * n ≤ (W'.card + ℓ) * n := Nat.mul_le_mul_right _ h1 _ = W'.card * n + ℓ * n := by ring _ ≤ (S \ G).card * k + G.card * k := Nat.add_le_add hW'card hc _ = S.card * k := by rw [← Nat.add_mul, h2]
Any ℓ'-cohesive group H ⊆ S disjoint from G has a member approving at least ℓ' candidates in W' ∪ C.
If an ℓ'-cohesive group H ⊆ S is disjoint from G, then H ⊆ S \ G. By the induction hypothesis for W', some voter i ∈ H approves at least ℓ' candidates in W', and hence at least ℓ' candidates in W' ∪ C.
uses
Finset.card_le_card,Finset.inter_subset_inter_left,Finset.subset_union_left· intro ℓ' hℓ' H hHS hHcoh by_cases hHG : Disjoint H G · have hHsub : H ⊆ S \ G := fun x hx => Finset.mem_sdiff.2 ⟨hHS hx, Finset.disjoint_left.1 hHG hx⟩ obtain ⟨i, hi, hle⟩ := hW' ℓ' hℓ' H hHsub hHcoh exact ⟨i, hi, hle.trans (Finset.card_le_card (Finset.inter_subset_inter_left Finset.subset_union_left))⟩
Any ℓ'-cohesive group H ⊆ S intersecting G has a member approving at least ℓ' candidates in W' ∪ C.
If H intersects G, take any voter i ∈ H ∩ G. By maximality of ℓ among cohesive groups in P, ℓ' ≤ ℓ. Since i ∈ G and all candidates in C are approved by G, voter i approves every candidate in C, so C ⊆ A(i) ∩ (W' ∪ C). Thus |A(i) ∩ (W' ∪ C)| ≥ |C| = ℓ ≥ ℓ'.
uses
Finset.card_le_card,Finset.mem_union_right· obtain ⟨i, hiH, hiG⟩ := Finset.not_disjoint_iff.1 hHG have hℓ'le : ℓ' ≤ ℓ := hmax (ℓ', H) ((hmemP ℓ' H).2 ⟨hℓ', hHS, hHcoh⟩) refine ⟨i, hiH, hℓ'le.trans ?_⟩ rw [← hCcard] apply Finset.card_le_card intro c hc exact Finset.mem_inter.2 ⟨(Finset.mem_filter.1 (hCsub hc)).2 i hiG, Finset.mem_union_right _ hc⟩
When P is empty, the empty candidate set vacuously satisfies the auxiliary lemma.
If P is empty, W = ∅ satisfies |W| * n = 0 ≤ |S| * k. Any ℓ-cohesive group G ⊆ S with ℓ ≥ 1 would give an element of P, so the condition holds vacuously by contradiction.
· refine ⟨∅, by simp, ?_⟩ intro ℓ hℓ G hGS hcoh exact absurd ⟨(ℓ, G), (hmemP ℓ G).2 ⟨hℓ, hGS, hcoh⟩⟩ hP
Applying the auxiliary lemma to the universal voter set yields a candidate set W of size at most k satisfying EJR.
Instantiating `ejr_greedy_cohesive_aux` with the universal set S = Finset.univ of all n voters gives a set W with |W| * n ≤ n * k. Because n > 0, this implies |W| ≤ k by `Nat.le_of_mul_le_mul_right`. Every cohesive group in the electorate is satisfied by W.
uses
ejr_greedy_cohesive_aux,Finset.univ,Finset.card_univ,Fintype.card_fin,Nat.le_of_mul_le_mul_right,mul_commintro n m A hn k hk classical obtain ⟨W, hWc, hW⟩ := ejr_greedy_cohesive_aux A k hn Finset.univ have hWk : W.card ≤ k := by rw [Finset.card_univ, Fintype.card_fin] at hWc exact Nat.le_of_mul_le_mul_right (by rw [mul_comm k n]; exact hWc) hn
Extending W to a superset W2 of size exactly k produces the desired EJR committee.
Since |W| ≤ k ≤ m, `Finset.exists_superset_card_eq` yields a superset W2 ⊇ W of cardinality exactly k. Any voter approving at least ℓ candidates in W also approves at least ℓ candidates in W2, completing the proof that W2 is an EJR committee.
uses
Finset.exists_superset_card_eq,Finset.subset_univ,Finset.card_le_card,Finset.inter_subset_inter_leftobtain ⟨W2, hsub, hcard⟩ := Finset.exists_superset_card_eq hWk (by simpa using hk) refine ⟨W2, hcard, fun ℓ hℓ G hG => ?_⟩ obtain ⟨i, hi, hle⟩ := hW ℓ hℓ G (Finset.subset_univ _) hG exact ⟨i, hi, hle.trans (Finset.card_le_card (Finset.inter_subset_inter_left hsub))⟩
Finset.strongInduction- Strong induction on finite sets: to prove a statement for all finite sets, it suffices to prove it for any set assuming it holds for all its proper subsets.
Finset.card_le_univ- The cardinality of any subset of a finite type is at most the total number of elements in that type.
Finset.mem_filter- An element belongs to a filtered set if and only if it belongs to the original set and satisfies the predicate.
Finset.mem_product- An ordered pair belongs to the Cartesian product of two sets if and only if its first component is in the first set and its second component is in the second set.
Finset.mem_Icc- An element belongs to the closed interval [a, b] if and only if it is between a and b inclusive.
Finset.mem_powerset- A set belongs to the powerset of another set if and only if it is a subset of that set.
Finset.nonempty_iff_ne_empty- A finite set is non-empty if and only if it is not equal to the empty set.
Finset.card_empty- The empty set has cardinality 0.
zero_mul- Zero multiplied by any element is zero.
Nat.mul_pos- The product of two strictly positive natural numbers is strictly positive.
Finset.sdiff_ssubset- Removing a non-empty subset from a set leaves a strictly smaller subset.
Finset.exists_subset_card_eq- Any finite set has a subset of size n whenever n is at most the cardinality of the set.
Finset.card_union_le- The cardinality of the union of two finite sets is at most the sum of their cardinalities.
Finset.card_sdiff_add_card_eq_card- For a subset s ⊆ t of finite sets, the size of t \ s plus the size of s equals the size of t.
Nat.mul_le_mul_right- Multiplying both sides of an inequality of natural numbers on the right by a constant preserves the inequality.
Nat.add_le_add- Adding two inequalities of natural numbers preserves the inequality.
Nat.add_mul- Distributivity of multiplication over addition: (n + m) * k = n * k + m * k.
Finset.card_le_card- A subset has cardinality less than or equal to that of the ambient finite set.
Finset.inter_subset_inter_left- Intersection with a fixed set preserves inclusion: if t ⊆ u, then s ∩ t ⊆ s ∩ u.
Finset.subset_union_left- Every set is a subset of its union with another set.
Finset.mem_union_right- An element of t belongs to s ∪ t.
ejr_greedy_cohesive_aux- For every voter subset S, there exists a candidate set W with |W| * n ≤ |S| * k such that every ℓ-cohesive group in S has a member approving at least ℓ candidates in W.
Finset.univ- The set of all elements of a finite type.
Finset.card_univ- The cardinality of the universal set of a finite type equals the number of elements in the type.
Fintype.card_fin- The cardinality of Fin n is n.
Nat.le_of_mul_le_mul_right- If a * c ≤ b * c and c > 0 for natural numbers, then a ≤ b.
mul_comm- Multiplication of natural numbers is commutative: a * b = b * a.
Finset.exists_superset_card_eq- A finite subset can be extended to a superset of any size between its cardinality and the total number of elements.
Finset.subset_univ- Every subset of a finite type is contained in the universal set.
- The proof constructs an EJR committee via an inductive greedy cohesive selection lemma rather than by optimizing the Proportional Approval Voting (PAV) objective score.
- The greedy selection may produce a candidate set of size strictly smaller than k, which is then arbitrarily padded to size k to satisfy the equality condition in the definition of an EJR committee.
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.
/-- The greedy cohesive argument: for every set `S` of voters there is a set `W` of at most`|S| k / n` candidates such that every `ℓ`-cohesive group inside `S` has a member approving atleast `ℓ` members of `W`. (Take a cohesive group `G ⊆ S` with the largest `ℓ`, give it `ℓ`commonly approved candidates and recurse on `S \ G`.) -/theorem ejr_greedy_cohesive_aux {n m : ℕ} (A : Fin n → Finset (Fin m)) (k : ℕ) (hn : 0 < n) (S : Finset (Fin n)) : ∃ W : Finset (Fin m), W.card * n ≤ S.card * k ∧ ∀ ℓ, 1 ≤ ℓ → ∀ G ⊆ S, is_ejr_cohesive_group A k ℓ G → ∃ i ∈ G, ℓ ≤ (A i ∩ W).card := by classical induction S using Finset.strongInduction with | H S ih => have hle_m : ∀ ℓ G, is_ejr_cohesive_group A k ℓ G → ℓ ≤ m := fun ℓ G h => h.2.trans ((Finset.card_le_univ _).trans (by simp)) let P : Finset (ℕ × Finset (Fin n)) := ((Finset.Icc 1 m) ×ˢ S.powerset).filter fun p => is_ejr_cohesive_group A k p.1 p.2 have hmemP : ∀ ℓ G, (ℓ, G) ∈ P ↔ (1 ≤ ℓ ∧ G ⊆ S ∧ is_ejr_cohesive_group A k ℓ G) := by intro ℓ G simp only [P, Finset.mem_filter, Finset.mem_product, Finset.mem_Icc, Finset.mem_powerset] constructor · rintro ⟨⟨⟨h1, -⟩, h2⟩, h3⟩; exact ⟨h1, h2, h3⟩ · rintro ⟨h1, h2, h3⟩; exact ⟨⟨⟨h1, hle_m ℓ G h3⟩, h2⟩, h3⟩ by_cases hP : P.Nonempty · obtain ⟨⟨ℓ, G⟩, hpP, hmax⟩ := P.exists_max_image Prod.fst hP obtain ⟨hℓ1, hGS, hcoh⟩ := (hmemP ℓ G).1 hpP have hGne : G.Nonempty := by rw [Finset.nonempty_iff_ne_empty] rintro rfl have h := hcoh.1 simp only [Finset.card_empty, zero_mul] at h have : 0 < ℓ * n := Nat.mul_pos hℓ1 hn omega obtain ⟨W', hW'card, hW'⟩ := ih (S \ G) (Finset.sdiff_ssubset hGS hGne) obtain ⟨C, hCsub, hCcard⟩ := Finset.exists_subset_card_eq hcoh.2 refine ⟨W' ∪ C, ?_, ?_⟩ · have h1 : (W' ∪ C).card ≤ W'.card + ℓ := (Finset.card_union_le _ _).trans (by rw [hCcard]) have h2 : (S \ G).card + G.card = S.card := Finset.card_sdiff_add_card_eq_card hGS have hc := hcoh.1 calc (W' ∪ C).card * n ≤ (W'.card + ℓ) * n := Nat.mul_le_mul_right _ h1 _ = W'.card * n + ℓ * n := by ring _ ≤ (S \ G).card * k + G.card * k := Nat.add_le_add hW'card hc _ = S.card * k := by rw [← Nat.add_mul, h2] · intro ℓ' hℓ' H hHS hHcoh by_cases hHG : Disjoint H G · have hHsub : H ⊆ S \ G := fun x hx => Finset.mem_sdiff.2 ⟨hHS hx, Finset.disjoint_left.1 hHG hx⟩ obtain ⟨i, hi, hle⟩ := hW' ℓ' hℓ' H hHsub hHcoh exact ⟨i, hi, hle.trans (Finset.card_le_card (Finset.inter_subset_inter_left Finset.subset_union_left))⟩ · obtain ⟨i, hiH, hiG⟩ := Finset.not_disjoint_iff.1 hHG have hℓ'le : ℓ' ≤ ℓ := hmax (ℓ', H) ((hmemP ℓ' H).2 ⟨hℓ', hHS, hHcoh⟩) refine ⟨i, hiH, hℓ'le.trans ?_⟩ rw [← hCcard] apply Finset.card_le_card intro c hc exact Finset.mem_inter.2 ⟨(Finset.mem_filter.1 (hCsub hc)).2 i hiG, Finset.mem_union_right _ hc⟩ · refine ⟨∅, by simp, ?_⟩ intro ℓ hℓ G hGS hcoh exact absurd ⟨(ℓ, G), (hmemP ℓ G).2 ⟨hℓ, hGS, hcoh⟩⟩ hPtheorem ejr_committee_exists : ∀ (n m : ℕ) (A : Fin n → Finset (Fin m)), 0 < n → ∀ k, k ≤ m → ∃ W, is_ejr_committee A k W := by intro n m A hn k hk classical obtain ⟨W, hWc, hW⟩ := ejr_greedy_cohesive_aux A k hn Finset.univ have hWk : W.card ≤ k := by rw [Finset.card_univ, Fintype.card_fin] at hWc exact Nat.le_of_mul_le_mul_right (by rw [mul_comm k n]; exact hWc) hn obtain ⟨W2, hsub, hcard⟩ := Finset.exists_superset_card_eq hWk (by simpa using hk) refine ⟨W2, hcard, fun ℓ hℓ G hG => ?_⟩ obtain ⟨i, hi, hle⟩ := hW ℓ hℓ G (Finset.subset_univ _) hG exact ⟨i, hi, hle.trans (Finset.card_le_card (Finset.inter_subset_inter_left hsub))⟩