Proceedings Abstracts of the Twenty-Third International Joint Conference on Artificial Intelligence

Fully Proportional Representation as Resource Allocation: Approximability Results / 353
Piotr Skowron, Piotr Faliszewski, Arkadii Slinko

We study the complexity of (approximate) winner determination under Monroe's and Chamberlin-Courant's multiwinner voting rules, where we focus on the total (dis)satisfaction of the voters (the utilitarian case) or the (dis)satisfaction of the worst-off voter (the egalitarian case). We show good approximation algorithms for the satisfaction-based utilitarian cases, and inapproximability results for the remaining settings.