A Quantitative Analysis of Multi-Winner Rules

Martin Lackner, Piotr Skowron

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.

Theoretical AV and CC guarantees for various multi-winner rules.

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.

Experimental performance of voting rules on real-world datasets (Preflib). The top plot shows AV-ratios and the bottom shows CC-ratios.

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

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.
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},
}
Figure