---
title: "The Core of Approval-Based Committee Elections with Few Seats"
authors:
  - "Dominik Peters"
doi: "10.24963/ijcai.2025/447"
url: "https://ijcai.org/proceedings/2025/447"
pdf: "https://ijcai.org/proceedings/2025/0447.pdf"
venue: "Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence"
year: 2025
pages: "4014-4022"
track: "Main Track"
keywords:
  - "Game Theory and Economic Paradigms: GTEP: Computational social choice"
---

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

Dominik Peters

*Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence*, pages 4014-4022. DOI: [10.24963/ijcai.2025/447](https://doi.org/10.24963/ijcai.2025/447)

## 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 ≤ 8, for any number of candidates m and any number of voters n, by showing that the Proportional Approval Voting (PAV) rule, proposed by Thiele in 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.