ejr_adjacent_committees_exists
For every approval profile with at least one voter and every k smaller than the candidate count, there exist nested committees W subset V satisfying EJR at sizes k and k+1, respectively.
Statement
theorem ejr_adjacent_committees_exists {n m : ℕ}
(A : Fin n → Finset (Fin m)) (hn : 0 < n) (k : ℕ) (hk : k < m) :
∃ W V : Finset (Fin m), W ⊆ V ∧ is_ejr_committee A k W ∧
is_ejr_committee A (k + 1) V- Formalizes
- arXiv:2302.01989, Robust and Verifiable Proportionality Axioms for Multiwinner Voting, Proposition 8: EJR consequence of the published EJR+ nested-pair theorem; this proof uses a strengthened greedy cohesive argument instead of the priceability proof.
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- ejr_greedy_cohesive_pair_auxFor every voter subset S and positive committee parameter K, a greedy cohesive core W has cost at most |S|K/n and satisfies every…
- 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| ≥ ℓ.
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- Used by 1
- ejr_chain_candidates_le_threeEvery approval profile on at most three candidates admits an EJR committee chain.
The proof, explained
The proof applies an auxiliary lemma (ejr_greedy_cohesive_pair_aux) to find an initial committee W₀ with |W₀| ≤ k + 1 that satisfies EJR at size k + 1. If |W₀| ≤ k, we greedily extend W₀ to nested committees W ⊆ V of sizes k and k + 1; the EJR guarantee transfers upward because any group cohesive at size k is also cohesive at size k + 1. If |W₀| = k + 1, the auxiliary lemma provides a candidate c ∈ W₀ whose deletion satisfies EJR at size k, yielding the nested pair W₀ \ {c} ⊆ W₀.
There exists an initial committee W₀ of size at most k + 1 satisfying EJR at committee size k + 1.
We invoke the auxiliary lemma ejr_greedy_cohesive_pair_aux for target committee size k + 1 on the set of all voters. This yields a candidate set W₀ satisfying the budget constraint |W₀| * n ≤ n * (k + 1), an EJR representation guarantee at size k + 1, and a candidate-deletion guarantee if the budget is tight. Since n > 0, dividing by n shows that |W₀| ≤ k + 1.
uses
ejr_greedy_cohesive_pair_auxclassical obtain ⟨W0, hbudget, hrep, hpair⟩ := ejr_greedy_cohesive_pair_aux A (k + 1) hn (by omega) Finset.univ have hbudget' : W0.card * n ≤ n * (k + 1) := by simpa using hbudget have hW0 : W0.card ≤ k + 1 := by nlinarith
In the case where |W₀| ≤ k, there exist nested committees W ⊆ V containing W₀ of sizes k and k + 1.
Assuming |W₀| ≤ k, since k < m, there are at least k + 1 candidates total. By applying Finset.exists_superset_card_eq twice, we first extend W₀ to a committee W of size k, and then extend W to a committee V of size k + 1. We propose W and V as our witnesses, leaving their EJR properties to be verified.
uses
Finset.exists_superset_card_eqby_cases hsmall : W0.card ≤ k · obtain ⟨W, hWsub, hWcard⟩ := Finset.exists_superset_card_eq hsmall (show k ≤ Fintype.card (Fin m) by simpa using hk.le) obtain ⟨V, hVsub, hVcard⟩ := Finset.exists_superset_card_eq (show W.card ≤ k + 1 by omega) (show k + 1 ≤ Fintype.card (Fin m) by simpa using hk) refine ⟨W, V, hVsub, ⟨hWcard, ?_⟩, ⟨hVcard, ?_⟩⟩
W satisfies EJR at committee size k.
Let G be a group cohesive at size k for some ℓ ≥ 1, so ℓ * n ≤ |G| * k. Since k ≤ k + 1, Nat.mul_le_mul_left and Nat.le_succ imply ℓ * n ≤ |G| * (k + 1), so G is also cohesive at size k + 1. By the representation guarantee of W₀, some voter i ∈ G approves at least ℓ candidates in W₀. Since W₀ ⊆ W, the intersection A i ∩ W₀ is contained in A i ∩ W (Finset.inter_subset_inter_left), so by Finset.card_le_card, voter i also approves at least ℓ candidates in W.
uses
Nat.mul_le_mul_left,Nat.le_succ,Finset.subset_univ,Finset.card_le_card,Finset.inter_subset_inter_left· intro ℓ hℓ G hG have hG' : is_ejr_cohesive_group A (k + 1) ℓ G := ⟨hG.1.trans (Nat.mul_le_mul_left G.card (Nat.le_succ k)), hG.2⟩ obtain ⟨i, hi, hu⟩ := hrep ℓ hℓ G (Finset.subset_univ _) hG' exact ⟨i, hi, hu.trans (Finset.card_le_card (Finset.inter_subset_inter_left hWsub))⟩
V satisfies EJR at committee size k + 1.
For any group G cohesive at size k + 1, the representation property of W₀ provides a voter i ∈ G approving at least ℓ candidates in W₀. Because W₀ ⊆ W ⊆ V, we have A i ∩ W₀ ⊆ A i ∩ V by Finset.inter_subset_inter_left, and Finset.card_le_card implies that voter i approves at least ℓ candidates in V.
uses
Finset.subset_univ,Finset.card_le_card,Finset.inter_subset_inter_left· intro ℓ hℓ G hG obtain ⟨i, hi, hu⟩ := hrep ℓ hℓ G (Finset.subset_univ _) hG exact ⟨i, hi, hu.trans (Finset.card_le_card (Finset.inter_subset_inter_left (hWsub.trans hVsub)))⟩
In the case where |W₀| > k, we have |W₀| = k + 1, and deleting some candidate c ∈ W₀ gives nested committees W₀ \ {c} ⊆ W₀ of sizes k and k + 1.
If |W₀| ≤ k does not hold, the upper bound |W₀| ≤ k + 1 forces |W₀| = k + 1. The budget equality |W₀| * n = n * (k + 1) is therefore met, and W₀ is nonempty by Finset.card_pos.mp. The candidate-removal property of ejr_greedy_cohesive_pair_aux then yields a candidate c ∈ W₀ whose removal satisfies EJR at size (k + 1) - 1 = k. We have W₀ \ {c} ⊆ W₀ by Finset.erase_subset, and its size is k by Finset.card_erase_of_mem.
uses
Nat.mul_comm,Finset.card_pos.mp,Finset.erase_subset,Finset.card_erase_of_mem· have hWcard : W0.card = k + 1 := by omega have hfull : W0.card * n = (Finset.univ : Finset (Fin n)).card * (k + 1) := by simp [hWcard, Nat.mul_comm] have hne : W0.Nonempty := Finset.card_pos.mp (by omega) obtain ⟨c, hc, hcpair⟩ := hpair hfull hne refine ⟨W0.erase c, W0, Finset.erase_subset _ _, ⟨?_, ?_⟩, ⟨hWcard, ?_⟩⟩ · rw [Finset.card_erase_of_mem hc, hWcard] omega
W₀ \ {c} satisfies EJR at committee size k.
For any group G cohesive at size k, the candidate-removal property hcpair from the auxiliary lemma directly ensures that some voter in G approves at least ℓ candidates in W₀ \ {c}.
uses
Finset.subset_univ· intro ℓ hℓ G hG have := hcpair ℓ hℓ G (Finset.subset_univ _) simpa using this hG
W₀ satisfies EJR at committee size k + 1.
Any group cohesive at size k + 1 is represented in W₀ by the guarantee hrep from the auxiliary lemma.
uses
Finset.subset_univ· intro ℓ hℓ G hG exact hrep ℓ hℓ G (Finset.subset_univ _) hG
ejr_greedy_cohesive_pair_aux- For an approval profile with n > 0 voters and committee target K > 0, there exists a candidate set W with |W| * n ≤ |S| * K satisfying EJR on voter subset S at size K; if |W| * n = |S| * K and W is nonempty, there exists c ∈ W whose deletion satisfies EJR on S at size K - 1.
Finset.exists_superset_card_eq- A finite set of size at most n in a finite type of cardinality at least n can be extended to a superset of cardinality exactly n.
Nat.mul_le_mul_left- Multiplying both sides of an inequality of natural numbers by a factor on the left preserves the inequality.
Nat.le_succ- Every natural number is less than or equal to its successor.
Finset.subset_univ- Every finite set of a finite type is a subset of the universal finset.
Finset.card_le_card- If one finite set is a subset of another, its cardinality is less than or equal to that of the superset.
Finset.inter_subset_inter_left- If t ⊆ u, then the intersection s ∩ t is a subset of s ∩ u.
Nat.mul_comm- Multiplication of natural numbers is commutative.
Finset.card_pos.mp- A finite set with strictly positive cardinality is nonempty.
Finset.erase_subset- Removing an element from a finite set produces a subset of the original set.
Finset.card_erase_of_mem- Removing an element that belongs to a finite set decreases its cardinality by 1.
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 ejr_adjacent_committees_exists {n m : ℕ} (A : Fin n → Finset (Fin m)) (hn : 0 < n) (k : ℕ) (hk : k < m) : ∃ W V : Finset (Fin m), W ⊆ V ∧ is_ejr_committee A k W ∧ is_ejr_committee A (k + 1) V := by classical obtain ⟨W0, hbudget, hrep, hpair⟩ := ejr_greedy_cohesive_pair_aux A (k + 1) hn (by omega) Finset.univ have hbudget' : W0.card * n ≤ n * (k + 1) := by simpa using hbudget have hW0 : W0.card ≤ k + 1 := by nlinarith by_cases hsmall : W0.card ≤ k · obtain ⟨W, hWsub, hWcard⟩ := Finset.exists_superset_card_eq hsmall (show k ≤ Fintype.card (Fin m) by simpa using hk.le) obtain ⟨V, hVsub, hVcard⟩ := Finset.exists_superset_card_eq (show W.card ≤ k + 1 by omega) (show k + 1 ≤ Fintype.card (Fin m) by simpa using hk) refine ⟨W, V, hVsub, ⟨hWcard, ?_⟩, ⟨hVcard, ?_⟩⟩ · intro ℓ hℓ G hG have hG' : is_ejr_cohesive_group A (k + 1) ℓ G := ⟨hG.1.trans (Nat.mul_le_mul_left G.card (Nat.le_succ k)), hG.2⟩ obtain ⟨i, hi, hu⟩ := hrep ℓ hℓ G (Finset.subset_univ _) hG' exact ⟨i, hi, hu.trans (Finset.card_le_card (Finset.inter_subset_inter_left hWsub))⟩ · intro ℓ hℓ G hG obtain ⟨i, hi, hu⟩ := hrep ℓ hℓ G (Finset.subset_univ _) hG exact ⟨i, hi, hu.trans (Finset.card_le_card (Finset.inter_subset_inter_left (hWsub.trans hVsub)))⟩ · have hWcard : W0.card = k + 1 := by omega have hfull : W0.card * n = (Finset.univ : Finset (Fin n)).card * (k + 1) := by simp [hWcard, Nat.mul_comm] have hne : W0.Nonempty := Finset.card_pos.mp (by omega) obtain ⟨c, hc, hcpair⟩ := hpair hfull hne refine ⟨W0.erase c, W0, Finset.erase_subset _ _, ⟨?_, ?_⟩, ⟨hWcard, ?_⟩⟩ · rw [Finset.card_erase_of_mem hc, hWcard] omega · intro ℓ hℓ G hG have := hcpair ℓ hℓ G (Finset.subset_univ _) simpa using this hG · intro ℓ hℓ G hG exact hrep ℓ hℓ G (Finset.subset_univ _) hG