Abstract
Multi-winner voting rules are essential for selecting a committee of size $k$ from a set of candidates. However, different applications demand different priorities, ranging from individual excellence to group diversity. This paper provides a quantitative framework to measure these trade-offs using approximation theory. By defining "AV-guarantees" and "CC-guarantees," the authors evaluate how well various rules approximate the gold standards of excellence (Approval Voting) and diversity (Chamberlin-Courant). The analysis reveals that Proportional Approval Voting (PAV) offers a superior balance, and that computationally efficient sequential rules provide high-quality results with significantly lower computational overhead.
The Excellence-Diversity Trade-off
In social choice theory, the "best" committee depends on the context. For instance, selecting an Olympic team requires maximizing individual excellence, typically achieved through Multi-winner Approval Voting (AV). Conversely, choosing locations for public facilities requires diversity to ensure broad representation, a goal represented by the Chamberlin-Courant (CC) rule. Most real-world scenarios, such as search engine result ranking, require a balance of both. Historically, these rules were studied through qualitative axioms; this work introduces quantitative tools to measure these trade-offs precisely.
Quantitative Framework: AV and CC Guarantees
The authors treat multi-winner rules as approximation algorithms, using AV and CC as benchmarks. They define the AV-guarantee and CC-guarantee as worst-case approximation ratios. A CC-guarantee of 0.5, for example, ensures that a rule will satisfy at least 50% as many voters as the optimal CC committee in any scenario.
As shown in the table above, PAV maintains a solid CC-guarantee of 1/2 while providing a respectable AV-guarantee of $\Theta(1/\sqrt{k})$. Interestingly, the Monroe rule, despite its focus on fairness, does not offer a better AV-guarantee than the diversity-centric CC rule.
A significant insight from this research is that "proportionality" is distinct from simply compromising between excellence and diversity. The authors proved that a non-proportional rule (a linear combination of AV and CC) can actually outperform all proportional rules in terms of both guarantees, challenging the assumption that proportional rules are the natural "middle ground."
Experimental Performance
To validate these theoretical bounds, the authors tested the rules against real-world data from Preflib.org and synthetic profiles. The experimental results demonstrate that most rules perform significantly better in practice than their worst-case theoretical limits.
In practice, PAV, seq-PAV, and seq-Phragmén consistently achieved ratios above 0.85 for both excellence and diversity. A key finding is the efficiency of greed: while finding optimal PAV or CC committees is NP-hard, sequential (greedy) versions of these rules (like seq-PAV and seq-CC) perform nearly as well as their exact counterparts in experimental settings.
Conclusion
This quantitative approach shifts the focus from binary axiomatic properties to measurable performance trade-offs. PAV emerges as a robust "all-rounder" rule. Furthermore, the high performance of sequential rules suggests that they are excellent candidates for large-scale applications where computational efficiency is paramount. Future research may extend this framework to ranking-based preferences and explore new benchmarks beyond the AV and CC poles.
Summary updated