# The Core of Approval-Based Committee Elections with Few Seats

arXiv: https://arxiv.org/abs/2501.18304 · HTML: https://mlsanity.com/paper/2501.18304/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jan 2025.

## Built on by (most cited first, 2 of 2)

- [A Linear Theory of Multi-Winner Voting](https://mlsanity.com/paper/2503.03082/) (2025)
- [Fair Transit Stop Placement: A Clustering Perspective and Beyond](https://mlsanity.com/paper/2602.06776/) (2026)

## Abstract (arXiv)

In an approval-based committee election, the goal is to select a committee consisting of k out of m candidates, based on n voters who each approve an arbitrary number of the candidates. The core of such an election consists of all committees that satisfy a certain stability property which implies proportional representation. In particular, committees in the core cannot be "objected to" by a coalition of voters who is underrepresented. The notion of the core was proposed in 2016, but it has remained an open problem whether it is always non-empty. We prove that core committees always exist when k ≤ 8, for any number of candidates m and any number of voters n, by showing that the Proportional Approval Voting (PAV) rule due to Thiele [1895] always satisfies the core when k ≤ 7 and always selects at least one committee in the core when k = 8. We also develop an artificial rule based on recursive application of PAV, and use it to show that the core is non-empty whenever there are m ≤ 15 candidates, for any committee size k ≤ m and any number of voters n. These results are obtained with the help of computer search using linear programs.