Approximation Algorithms for BalancedCC Multiwinner Rules

M. Brill, P. Faliszewski, F. Sommer, N. Talmon
AAMAS 2019
Abstract
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 GreedyMonroe 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.

Experiments:

Election type Culture Candidates Voters Instances Parameters
Ordinal Impartial Culture {100} {100} 150 None
Ordinal Urn Model {100} {100} 150 \alpha \in \{0, 0.1, 0.25, 0.5\}