Utilitarian Welfare and Representation Guarantees of Approval-Based Multiwinner Rules
This work addresses the ambiguous task of choosing multiwinner voting rules for decision-making contexts, providing fundamental insights into tradeoffs between representation and welfare.
The paper tackles the problem of selecting optimal multiwinner voting rules by quantitatively analyzing how well they approximate two opposing objectives: representation via Approval Chamberlin-Courant and utilitarian welfare via Multiwinner Approval Voting, using theoretical and experimental methods to classify rules and reveal necessary tradeoffs.
To choose a suitable multiwinner voting rule is a hard and ambiguous task. Depending on the context, it varies widely what constitutes the choice of an ``optimal'' subset of alternatives. In this paper, we provide a quantitative analysis of multiwinner voting rules using methods from the theory of approximation algorithms---we estimate how well multiwinner rules approximate two extreme objectives: a representation criterion defined via the Approval Chamberlin--Courant rule and a utilitarian criterion defined via Multiwinner Approval Voting. With both theoretical and experimental methods, we classify multiwinner rules in terms of their quantitative alignment with these two opposing objectives. Our results provide fundamental information about the nature of multiwinner rules and, in particular, about the necessary tradeoffs when choosing such a rule.