ejr_support_density_bound
def
The finite supporter-density bound: for every candidate subset T, its undersatisfied supporter count times q is at most |T| times the number of voters. The proposed size-k invariant uses q=k+1.
Statement
def ejr_support_density_bound {n m : ℕ} (A : Fin n → Finset (Fin m)) (q : ℕ) (W : Finset (Fin m)) : Prop
- Source
- Supporting work for OP-22, arXiv:2007.01795, Q2, and the proposed max-group-density invariant in memory attempt 4342. These helpers neither settle full-chain existence nor refute the actual greedy rule. No research advance is claimed.
- Verified
- 25 Oct 2026
- Axioms
- none listed
- Used by 6
- ejr_support_density_bound_supported_trapEven when every candidate has approval support, a committee satisfying the stronger density bound can have no next-size extension…
- ejr_chain_exists_of_support_density_boundA permutation whose every prefix satisfies the proposed density bound yields an EJR committee chain.
- ejr_support_density_bound_two_voter_trapThe two-voter private-approval profile has a size-one committee satisfying the stronger density bound, but no size-two extension…
- ejr_of_support_density_boundFor a nonempty electorate, the density bound with q=k+1 implies EJR for any committee of size k.
- ejr_support_density_bound_emptyEvery approval profile satisfies the initial density bound q=1 at the empty committee.
- ejr_support_density_bound_iff_groupsThe finite supporter bound is equivalent to the corresponding bound on every commonly approving group whose members all have utility below…
Lean source view module on GitHub
def ejr_support_density_bound {n m : ℕ} (A : Fin n → Finset (Fin m)) (q : ℕ) (W : Finset (Fin m)) : Prop := ∀ T : Finset (Fin m), (Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ W).card < T.card).card * q ≤ T.card * n