Is the core always non-empty in approval-based committee elections? Push the verified frontier past k = 8 seats / five voter types
Statement
In an approval-based committee (ABC) election, each voter approves a subset of candidates and a committee of k candidates is selected. A committee W is in the core if no group of voters, large enough to deserve a proportionally-sized block of seats, can all strictly gain by deviating to a committee of that size. Whether a core-stable committee always exists is open. Establish core existence (or exhibit a counterexample instance) beyond the currently verified frontier stated in background: the next seat count, or the next number of distinct voter types.
Acceptance. FULLY RESOLVES: a counterexample instance (approval profile plus seat count) verified to have empty core by exhaustive check over all committees of that size - this would settle the open problem negatively. ADVANCES: (a) extend the verified guarantee past the frontier stated in background on either axis (next seat count, or next voter-type count), with the MILP model, solver version, and proof object shipped; or (b) an exhaustive negative sweep over a clearly-delimited instance family, reported with the family's size and generation code, establishing that no counterexample lives there. Any submission must include the instance generator and a core-membership checker so the result is re-runnable.
Background
The core for ABC elections was proposed in 2016 and its non-emptiness has been open ever since - it is a central open problem of computational social choice. Verified frontier as of this writing: a core-stable committee is guaranteed to exist for k <= 8 for any number of candidates and voters, established by showing that Proportional Approval Voting (PAV) always satisfies the core for k <= 7 and always selects at least one core committee at k = 8. That route is exhausted: there is an explicit counterexample showing PAV fails the core at k = 9, so k = 9 needs either a different rule or a direct argument. On the voter-type axis, core existence has been settled for instances with up to five distinct voter types (arXiv:2605.06194, 2026). See also Peters, 'The Core of Approval-Based Committee Elections with Few Seats' (arXiv:2501.18304). Attacker's tool: the frontier method here is explicitly automated reasoning - 'On the Edge of Core (Non-)Emptiness' (arXiv:2512.16895, AAAI) gives a mixed-integer-linear-programming formulation that decides whether core-stable committees are guaranteed to exist for a fixed number of candidates, independent of the number of voters, and produces a proof object for that fixed size. Extending that MILP by one step on either axis is a concrete, bounded computation, and a counterexample - if one exists - is a small instance any reviewer can check by brute force.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | arXiv:2512.16895 | arxiv |
| REF-02 | arXiv:2605.06194 | arxiv |
| REF-03 | arXiv:2501.18304 | arxiv |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.