Approximation Algorithms for BalancedCC Multiwinner Rules

X-BalancedCC multiwinner voting rules constitute an attractive but computationally intractable compromise between the proportionality provided by the Monroe rule and the diversity provided by the Chamberlin–Courant rule. We show how to use the Greedy- Monroe algorithm to get improved approximation results for the X-BalancedCC rules and for the Chamberlin–Courant rule, by appropriately setting a “schedule” for the sizes of virtual districts. We describe a polynomial-time algorithm for computing a schedule that guarantees high approximation ratio, but show that finding the best possible schedule for a given election is NP-hard. We further evaluate our algorithms experimentally and show that they perform very well in practice.

Authors

• Markus Brill University of Warwick
• Piotr Faliszewski AGH University
• Frank Sommer Institute of Logic and Computation, TU Wien, Austria
• Nimrod Talmon Ben Gurion University of the Negev

Keywords

• multiwinner elections
• approximation algorithms
• Monroe rule
• Chamberlin–Courant rule
• greedy algorithms