The Core of Approval-Based Committee Elections with Few Seats

Abstract

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\le 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\le 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\le 15$ candidates, for any committee size $k\le m$ and any number of voters $n$. These results are obtained with the help of computer search using linear programs.

Full version of the paper to appear in the proceedings of IJCAI 2025. The title has changed to be more descriptive