On the Computation of Fully Proportional Representation

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