AFTD Auto-Formalizing Theoretical Domains

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
See it in the graphDiscuss this resultChallenge it