# On the Computation of Fully Proportional Representation

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Feb 2014.

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

- [Generative Social Choice](https://mlsanity.com/paper/2309.01291/) (2023)
- [Temporal Fairness in Multiwinner Voting](https://mlsanity.com/paper/2312.04417/) (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)
- [Multi-Group Proportional Representation in Retrieval](https://mlsanity.com/paper/2407.08571/) (2024)
- [Diversity of Structured Domains via k-Kemeny Scores](https://mlsanity.com/paper/2509.15812/) (2025)
- [Polynomial-Time Algorithm for Thiele Voting Rules with Voter Interval Preferences](https://mlsanity.com/paper/2604.05953/) (2026)
- [Bribery as a Measure of Candidate Success: Complexity Results for Approval-Based Multiwinner Rules](https://mlsanity.com/paper/2104.09130/) (2021)
- [The Complexity of Learning Approval-Based Multiwinner Voting Rules](https://mlsanity.com/paper/2110.00254/) (2021)
- [Parameterized Intractability for Multi-Winner Election under the Chamberlin-Courant Rule and the Monroe Rule](https://mlsanity.com/paper/2202.12006/) (2022)
- [Indivisible Participatory Budgeting under Weak Rankings](https://mlsanity.com/paper/2207.07981/) (2022)
- [Fine-Grained Complexity and Algorithms for the Schulze Voting Method](https://mlsanity.com/paper/2103.03959/) (2021)
- [Efficient Algorithms for Electing Successive Committees](https://mlsanity.com/paper/2505.18287/) (2025)
- [Algorithms for Structured Elections under Thiele Voting Rules](https://mlsanity.com/paper/2607.28575/) (2026)

## Abstract (arXiv)

We investigate two systems of fully proportional representation suggested by Chamberlin Courant and Monroe. Both systems assign a representative to each voter so that the "sum of misrepresentations" is minimized. The winner determination problem for both systems is known to be NP-hard, hence this work aims at investigating whether there are variants of the proposed rules and/or specific electorates for which these problems can be solved efficiently. As a variation of these rules, instead of minimizing the sum of misrepresentations, we considered minimizing the maximal misrepresentation introducing effectively two new rules. In the general case these "minimax" versions of classical rules appeared to be still NP-hard. We investigated the parameterized complexity of winner determination of the two classical and two new rules with respect to several parameters. Here we have a mixture of positive and negative results: e.g., we proved fixed-parameter tractability for the parameter the number of candidates but fixed-parameter intractability for the number of winners. For single-peaked electorates our results are overwhelmingly positive: we provide polynomial-time algorithms for most of the considered problems. The only rule that remains NP-hard for single-peaked electorates is the classical Monroe rule.