is_ejr_committee
def
A committee W with |W| = k satisfies EJR if for every ℓ ≥ 1 and every ℓ-cohesive group G some voter i ∈ G has |A_i ∩ W| ≥ ℓ.
Statement
def is_ejr_committee {n m : ℕ} (A : Fin n → Finset (Fin m)) (k : ℕ) (W : Finset (Fin m)) : Prop
- Defined in
- arXiv:2007.01795 (Multi-Winner Voting with Approval Preferences), definition of EJR
- Verified
- 06 Oct 2026
- Axioms
- none listed
- Built on 1
- 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 21
- ejr_chain_exists_of_support_density_boundA permutation whose every prefix satisfies the proposed density bound yields an EJR committee chain.
- ejr_chain_of_low_support_candidateIf candidate c is approved by fewer than n/m voters and the profile with c deleted (transported along e) admits an EJR chain, then so does…
- is_ejr_committee_iff_candidate_subsetsEJR is equivalent to the correct committee size together with the underrepresented-supporter inequality for every nonempty candidate…
- ejr_chain_two_votersFor every approval profile with two voters and any number of candidates, there is an ordering of the candidates every prefix of which is…
- ejr_good_of_low_support_candidateIf candidate c is approved by fewer than n/m voters (m times its supporter count is below n), then for any k-committee P with c not in P,…
- is_ejr_committee_zeroFor every approval profile with at least one voter, the empty committee is an EJR committee of size 0.
- ejr_chain_of_deletable_voterIf a voter's ballot is empty or misses at most one candidate, deleting that voter preserves the existence of an EJR chain: the same…
- ejr_committee_nine_without_three_subsetThere is an approval profile with nine voters and eleven candidates and an EJR committee of size nine that contains no EJR committee of…
- 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…
- ejr_chain_iff_level_supportersA permutation whose every prefix of length k is an EJR committee exists if and only if there is a permutation such that for every k ≤ m…
- not_ejr_committee_two_voters_ignoredIf two voters both approve only candidate 0, the committee {1} of size 1 violates EJR.
- ejr_two_voters_criterionFor two voters, a committee W of size k satisfies EJR whenever: (1) if k ≤ |A 0 ∩ A 1| then W ⊆ A 0 ∩ A 1; (2) if |A 0 ∩ A 1| ≤ k then A 0…
- ejr_committee_univFor every approval profile with at least one voter, the committee consisting of all m candidates satisfies EJR at committee size m.
- ejr_of_support_density_boundFor a nonempty electorate, the density bound with q=k+1 implies EJR for any committee of size k.
- 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_singleton_ballotsIf every voter approves at most one candidate, then there is an ordering of the candidates every prefix of which is an EJR committee of…
- 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_nested_committees_iffAn approval profile admits an EJR committee chain if and only if it admits an increasing sequence of EJR committees of sizes 0 through m.
- ejr_chain_one_voterEvery approval profile with exactly one voter admits an EJR committee chain.
- ejr_chain_candidates_le_threeEvery approval profile on at most three candidates 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
/-- Extended justified representation of a committee `W` of size `k`: for every `ℓ ≥ 1`, every `ℓ`-cohesive group has a member who approves at least `ℓ` members of `W`. -/ def is_ejr_committee {n m : ℕ} (A : Fin n → Finset (Fin m)) (k : ℕ) (W : Finset (Fin m)) : Prop := W.card = k ∧ ∀ ℓ, 1 ≤ ℓ → ∀ G : Finset (Fin n), is_ejr_cohesive_group A k ℓ G → ∃ i ∈ G, ℓ ≤ (A i ∩ W).card