# Achieving Fully Proportional Representation: Approximability Results

arXiv: https://arxiv.org/abs/1312.4026 · HTML: https://mlsanity.com/paper/1312.4026/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Dec 2013.

## Built on by (most cited first, 7 of 7)

- [Generative Social Choice](https://mlsanity.com/paper/2309.01291/) (2023)
- [Drawing a Map of Elections](https://mlsanity.com/paper/2504.03809/) (2025)
- [DiRe Committee : Diversity and Representation Constraints in Multiwinner Elections](https://mlsanity.com/paper/2107.07356/) (2021)
- [Proportional Representation in Metric Spaces and Low-Distortion Committee Selection](https://mlsanity.com/paper/2312.10369/) (2023)
- [Subset Selection Based On Multiple Rankings in the Presence of Bias: Effectiveness of Fairness Constraints for Multiwinner Voting Score Functions](https://mlsanity.com/paper/2306.09835/) (2023)
- [Parameterized Intractability for Multi-Winner Election under the Chamberlin-Courant Rule and the Monroe Rule](https://mlsanity.com/paper/2202.12006/) (2022)
- [Fairly Allocating Utility in Constrained Multiwinner Elections](https://mlsanity.com/paper/2211.12820/) (2022)

## Abstract (arXiv)

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.