A Quantitative Analysis of Multi-Winner Rules

Martin Lackner, Piotr Skowron

Introduction

Selecting a committee of $k$ winners from a pool of candidates is a foundational problem in social choice theory. Whether electing a parliament, curating search results, or placing public facilities, the definition of an "optimal" outcome depends heavily on the objective. This paper provides the first comprehensive quantitative analysis of multi-winner voting rules, framing them as approximation algorithms to measure the inherent trade-off between individual excellence and group representation.

The Tug-of-War: Utilitarianism vs. Representation

The authors identify two primary, often conflicting, objectives in multi-winner elections:

  1. Utilitarian Welfare (Excellence): Maximizing the total satisfaction of the electorate. In an approval-based system, this means maximizing the total number of approvals for the committee members. Approval Voting (AV) is the gold standard here.
  2. Representation (Diversity): Ensuring that as many voters as possible are represented by at least one candidate they approve of. The Approval Chamberlin–Courant (CC) rule is the benchmark for this goal.

Historically, these rules were compared qualitatively based on axiomatic properties. This research shifts the focus to quantitative performance, asking: how much utilitarian welfare do we sacrifice for representation, and vice versa?

Methodology

The study bridges social choice theory with the theory of approximation algorithms. By calculating worst-case guarantees (theoretical lower bounds) and average-case performance (empirical ratios), the authors evaluate how well different rules approximate the optimal utilitarian and representation scores.

The analysis covers a wide range of rules, including Thiele methods like Proportional Approval Voting (PAV) and the newly introduced Sainte-Laguë Approval Voting (SLAV), as well as sequential and parametric rules. These were tested against diverse datasets, including real-world preferences from Preflib.org and synthetic models like the Mallows and Pólya’s Urn models.

Key Findings and Theoretical Bounds

The research reveals significant disparities in how rules handle the excellence-diversity trade-off. A central finding is that many popular rules, despite their complexity, do not necessarily offer superior guarantees.

Theoretical guarantees and Pareto efficiency for various multi-winner voting rules.

The "Big Winners": PAV and SLAV

Proportional Approval Voting (PAV) and the new SLAV rule emerge as robust compromises. While AV and CC both suffer from a dismal $1/k$ guarantee in their non-primary objective, PAV achieves a utilitarian guarantee of $\Theta(1/\sqrt{k})$ and a representation guarantee of $1/2$. SLAV further improves the representation guarantee to $3/5$ while maintaining the same class of utilitarian efficiency.

The Complexity Paradox and Pareto Inefficiency

Interestingly, computationally intensive rules like Monroe or leximin-Phragmén do not outperform simpler sequential rules in terms of welfare or representation. Furthermore, the analysis highlights a widespread issue of Pareto inefficiency: many rules, including Phragmén’s and all sequential variants, can produce committees that are "dominated"—meaning another committee exists that would make at least one voter happier without making anyone else worse off.

Conclusion

By quantifying the performance of multi-winner rules, this paper provides a practical guide for mechanism design. PAV and SLAV stand out as highly effective for general-purpose committee selection, offering strong theoretical guarantees and consistently high performance in empirical simulations. The introduction of the $p$-Geometric rule also offers a flexible tool for decision-makers to explicitly weight the importance of excellence versus diversity.

Summary updated

Abstract

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.
BibTeX
@inproceedings{lackner2019quantitative,
  author = {Martin Lackner and Piotr Skowron},
  title = {{A Quantitative Analysis of Multi-Winner Rules}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/58},
}

Loading related content...

Figure