# Parameterized Intractability for Multi-Winner Election under the Chamberlin-Courant Rule and the Monroe Rule

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 8 references that are in the map.
- First posted on arXiv 24 Feb 2022.

## Builds on (most cited first, 2 of 2)

- [On the Computation of Fully Proportional Representation](https://mlsanity.com/paper/1402.0580/) (2014)
- [Achieving Fully Proportional Representation: Approximability Results](https://mlsanity.com/paper/1312.4026/) (2013)

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

- [Efficient Algorithms for Electing Successive Committees](https://mlsanity.com/paper/2505.18287/) (2025)

## Abstract (arXiv)

Answering an open question by Betzler et al. [Betzler et al., JAIR'13], we resolve the parameterized complexity of the multi-winner determination problem under two famous representation voting rules: the Chamberlin-Courant (in short CC) rule [Chamberlin and Courant, APSR'83] and the Monroe rule [Monroe, APSR'95]. We show that under both rules, the problem is W[1]-hard with respect to the sum β of misrepresentations, thereby precluding the existence of any f(β) · |I|O(1) -time algorithm, where |I| denotes the size of the input instance.