is_ejr_cohesive_group
def
For committee size k, a group G of the n voters is ℓ-cohesive if |G| ≥ ℓ·n/k and |∩_{i∈G} A_i| ≥ ℓ.
Statement
def is_ejr_cohesive_group {n m : ℕ} (A : Fin n → Finset (Fin m)) (k ℓ : ℕ) (G : Finset (Fin n)) : Prop
- Defined in
- arXiv:2007.01795 (Multi-Winner Voting with Approval Preferences), definition of ℓ-cohesive groups (Sec. on proportionality axioms); division cleared as ℓ·n ≤ |G|·k
- Verified
- 06 Oct 2026
- Axioms
- none listed
- Used by 9
- is_ejr_committee_zeroFor every approval profile with at least one voter, the empty committee is an EJR committee of size 0.
- 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| ≥ ℓ.
- ejr_adjacent_committees_existsFor every approval profile with at least one voter and every k smaller than the candidate count, there exist nested committees W subset V…
- not_ejr_committee_two_voters_ignoredIf two voters both approve only candidate 0, the committee {1} of size 1 violates EJR.
- 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_committee_iff_undersatisfied_supportersA committee W of size k satisfies EJR exactly when, for each positive ell and each ell-element candidate set T, fewer than ell*n/k voters…
- ejr_chain_of_nested_committeesIf there are committees W_0 ⊆ W_1 ⊆ ... ⊆ W_m with W_0 empty and W_k an EJR committee of size k for every k ≤ m, then there is a…
- ejr_chain_one_voterEvery approval profile with exactly one voter admits an EJR committee chain.
- ejr_committee_existsFor every approval profile with at least one voter and every committee size k ≤ m, some committee of size k satisfies EJR (for instance…
Lean source view module on GitHub
/-- A group `G` of voters is `ℓ`-cohesive for committee size `k` in the approval profile `A` (voters `Fin n`, candidates `Fin m`): `|G| ≥ ℓ n / k` and the members of `G` jointly approve at least `ℓ` candidates. -/ def is_ejr_cohesive_group {n m : ℕ} (A : Fin n → Finset (Fin m)) (k ℓ : ℕ) (G : Finset (Fin n)) : Prop := ℓ * n ≤ G.card * k ∧ ℓ ≤ (Finset.univ.filter fun c => ∀ i ∈ G, c ∈ A i).card