Achieving Fully Proportional Representation: Approximability Results
This addresses the problem of achieving proportional representation in voting systems for computational social choice, with incremental algorithmic improvements.
The paper tackles the complexity of winner determination under Monroe and Chamberlin--Courant multiwinner voting rules, providing good approximation algorithms for satisfaction-based utilitarian versions and inapproximability results for dissatisfaction-based utilitarian and all egalitarian cases, with experiments showing near-perfect solutions in many cases.
We study the complexity of (approximate) winner determination under the Monroe and Chamberlin--Courant multiwinner voting rules, which determine the set of representatives by optimizing the total (dis)satisfaction of the voters with their representatives. The total (dis)satisfaction is calculated either as the sum of individual (dis)satisfactions (the utilitarian case) or as the (dis)satisfaction of the worst off voter (the egalitarian case). We provide good approximation algorithms for the satisfaction-based utilitarian versions of the Monroe and Chamberlin--Courant rules, and inapproximability results for the dissatisfaction-based utilitarian versions of them and also for all egalitarian cases. Our algorithms are applicable and particularly appealing when voters submit truncated ballots. We provide experimental evaluation of the algorithms both on real-life preference-aggregation data and on synthetic data. These experiments show that our simple and fast algorithms can in many cases find near-perfect solutions.