A Quantitative Analysis of Multi-Winner Rules

M. Lackner, P. Skowron
IJCAI 2019
Abstract
To choose a suitable multi-winner voting rule is a hard and ambiguous task. Depending on the context, it varies widely what constitutes the choice of an "optimal" subset.In this paper, we offer a new perspective on measuring the quality of such subsets and---consequently---of multi-winner rules. We provide a quantitative analysis using methods from the theory of approximation algorithms and estimate how well multi-winner rules approximate two extreme objectives: diversity as captured by the Approval Chamberlin--Courant rule and individual excellence as captured by Multi-winner Approval Voting. With both theoretical and experimental methods we classify multi-winner rules in terms of their quantitative alignment with these two opposing objectives.

Remarks: Has a journal version: Martin Lackner, Piotr Skowron: Utilitarian welfare and representation guarantees of approval-based multiwinner rules. Artif. Intell. 288: 103366 (2020)

Experiments:

Election type Culture Candidates Voters Instances Parameters
Approval Impartial Culture (Variant) {20} {50} 500 None