Abstract
Traditional multiwinner voting research typically focuses on selecting a committee of a fixed size. However, many real-world collective decision-making scenarios, such as voting on a series of independent ballot measures, involve a variable number of winners (VNW). This paper investigates how to ensure fairness and proportional representation in these settings. By analyzing both deterministic and randomized voting rules, the authors demonstrate that while deterministic rules face inherent mathematical limitations in providing strong fairness guarantees, a simple randomized approach—the Proportional Random Rule—achieves a high degree of average satisfaction for cohesive groups of voters while remaining strategyproof.
Introduction
In social choice theory, multiwinner voting usually assumes a Fixed Number of Winners (FNW), such as electing exactly ten members to a city council. In such cases, proportionality axioms like "Justified Representation" ensure that a sufficiently large group of voters who agree on certain candidates will see their preferences reflected in the final committee.
However, many democratic processes do not fit this mold. Consider a ballot containing 20 independent "Yes/No" propositions. There is no requirement to pass a specific number of measures; the final set of outcomes depends entirely on voter preferences. This Variable Number of Winners (VNW) setting presents a unique challenge: how do we define and guarantee proportionality when the size of the winning set is not predetermined?
Redefining Satisfaction in VNW Elections
A core contribution of this research is the adaptation of fairness concepts to the VNW setting. In standard committee selection, utility is typically derived from the inclusion of preferred candidates. In VNW elections, however, there is an "Agreement Symmetry": a voter derives utility from the outcome matching their preference, whether that means a candidate they support is included or a candidate they oppose is excluded.
To measure fairness, the authors focus on Average Satisfaction (AS). This metric evaluates how well a voting rule satisfies cohesive groups of voters relative to their size. A group is considered cohesive if they all share the same preferences over a subset of candidates.
The Limits of Deterministic Rules
The authors first examine whether existing deterministic rules from FNW literature can be adapted to provide proportionality in VNW elections. These include:
- Proportional Approval Voting (PAV): A rule that maximizes a utility score based on the number of candidates a voter agrees with.
- Sequential Phragmén: A rule that treats candidates as "loads" to be distributed fairly among voters.
- Rule X: A budget-based rule where voters "spend" their voting power to include or exclude candidates.
The findings are largely negative for the deterministic case. The authors prove that no deterministic rule can guarantee more than a 0.5-approximation of the ideal satisfaction level. This is because deterministic rules can be forced into "all-or-nothing" decisions, where a majority preference completely overrides a minority across all candidates, leaving the minority with zero satisfaction on their specific preferences.
The Proportional Random Rule (PRR)
To overcome the limitations of deterministic rules, the paper analyzes the Proportional Random Rule (PRR). Under this randomized rule, each candidate $c_j$ is included in the winning set independently with a probability $p_j$ equal to the fraction of voters who approved that candidate.
This approach "smooths out" the unfairness inherent in deterministic outcomes. Because each candidate is decided independently based on their approval share, a majority cannot steamroll a minority across every single measure.
Key Advantages of PRR:
- High Proportionality: The headline result of the paper is that PRR satisfies a 29/32-approximation of Average Satisfaction (approximately 90.6%). This is a significant improvement over the 50% limit of deterministic rules.
- Strategyproofness: PRR is strategyproof. Since each candidate's outcome is determined solely by their own approval rating, voters have no incentive to misrepresent their preferences on one candidate to influence the outcome of another.
- Tightness: The authors prove that the 29/32 bound is tight for PRR, meaning it is the best possible guarantee this specific rule can provide.
Conclusion and Future Directions
This research highlights a fundamental trade-off in VNW elections: while deterministic rules provide a single, clear outcome, they struggle to protect minority interests proportionally. Randomization, via the Proportional Random Rule, offers a mathematically superior way to ensure that all cohesive groups receive their "fair share" of representation.
Future work remains in narrowing the gap between the 29/32 bound and a perfect 1-AS approximation. Additionally, the authors suggest exploring asymmetric utilities—where voters might care more about a specific "Yes" vote than a "No" vote—and further refining proportionality axioms like Extended Justified Representation (EJR) for the variable-winner context.
Summary updated