Achieving fully proportional representation: Approximability results

摘要

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 satisfaction or dissatisfaction of the voters with their representatives. The total (dis)satisfaction is calculated either as the sum of individual (dis)satisfactions in the utilitarian case or as the (dis)satisfaction of the worst off voter in 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 these rules 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 preference data. These experiments show that our simple and fast algorithms can, in many cases, find near-perfect solutions.