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:
- 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.
- 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.
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