Source-linked AI summary
Properties of Multiwinner Voting Rules
Edith Elkind, Piotr Faliszewski, Piotr Skowron, Arkadii Slinko
TL;DR
Multiwinner voting rules select committees for applications including representation, product promotion, web search, and short-listing, but their desirable properties depend on the task. This paper studies scoring-based multiwinner rules, identifies two natural rule families, and evaluates prominent rules against formalized properties, finding that SNTV satisfies all defined properties except strong unanimity while Greedy-CC fails several properties.
Problem
Multiwinner selection requires formal rules for choosing committees, while the desirable properties of those rules may depend on the application.
Method
The paper studies ten scoring-based multiwinner rules, identifies best-k and committee scoring rules, and introduces and adapts axioms for evaluating them.
Results
SNTV satisfies all defined properties among the considered rules, with unanimity only in the weak sense; Greedy-CC fails solid coalitions, consensus committee, and candidate monotonicity.
Takeaways & Limitations
The framework organizes scoring-based multiwinner rules and shows that property desirability must be assessed in the context of a specific application.
Takeaways & Limitations
Greedy-CC, an approximation algorithm for ℓ1-CC, fails the solid coalitions and consensus committee properties and candidate monotonicity.
Abstract
from arXiv · showhide
The goal of this paper is to propose and study properties of multiwinner voting rules which can be consider as generalisations of single-winner scoring voting rules. We consider SNTV, Bloc, k-Borda, STV, and several variants of Chamberlin--Courant's and Monroe's rules and their approximations. We identify two broad natural classes of multiwinner score-based rules, and show that many of the existing rules can be captured by one or both of these approaches. We then formulate a number of desirable properties of multiwinner rules, and evaluate the rules we consider with respect to these properties.
1 Introduction
Multiwinner voting rules select fixed-size committees for applications ranging from representation and shortlisting to product or movie selection. The paper develops a scoring-based framework, introduces properties, and compares ten rules while leaving Condorcet-based rules for future work.
- Applications: Multiwinner rules select small groups from larger populations in representative democracy, product promotion, web search, and job shortlisting.The appropriate desirable properties depend on the application.
- Scope: The paper focuses on preference-based rules that extend positional scoring rules, complementing approval-based and Condorcet-based research.The authors note that multiwinner elections are less studied and encompass several distinct models.
- Rules studied: The study examines STV, SNTV, k-Borda, Bloc, three Chamberlin–Courant variants, and three Monroe variants, including approximation-based rules.These rules represent different scoring-based approaches and include proportional-representation methods.
- Properties: The authors introduce committee monotonicity, solid coalitions, consensus committee, unanimity, and multiwinner adaptations of monotonicity, homogeneity, and consistency.They evaluate the selected rules against these properties.
- Scope: The framework is explicitly preliminary and excludes Condorcet-based rules, which the authors identify as future work.The paper uses “axiom” without necessarily implying a normative requirement.
2 Preliminaries
The preliminaries define elections as candidate sets with voters’ preference rankings and formalize rules that return tied-winning committees of exactly a requested size. This fixed-size requirement is useful for applications such as constitutionally sized parliaments but can force Pareto-dominated candidates.
- Elections: An election consists of candidates and voters, with each voter represented by a linear ranking of the candidates.The notation records candidate positions and supports concatenating voter sequences.
- Multiwinner rules: A multiwinner rule takes an election and target size k, returning all tied-winning committees that contain exactly k candidates.Tie-breaking is largely set aside in favor of representing all tied outcomes.
- Committee size: The fixed-size formulation suits settings where committee size is predetermined, such as a parliament whose size is constitutionally fixed.The alternative is to allow committees with up to k members, which the paper does not adopt.
- Committee size: Requiring exactly k winners can force Pareto-dominated candidates when voters unanimously share an ordering and k exceeds one.The paper accepts this consequence for simplicity and applicability.
3 Multiwinner Voting Rules
The paper defines common multiwinner rules and organizes them through best-k and committee-scoring perspectives. These classes capture rules ranging from simple score selection to representation-focused and computationally hard procedures.
- Common rules: STV iteratively elects candidates meeting a Droop quota, transfers or deletes votes, and eliminates low-plurality candidates when no quota is met.The paper notes that STV has multiple variants.
- Common rules: SNTV, Bloc, and k-Borda select k candidates using plurality, k-approval, and Borda scores, respectively.SNTV is equivalent to k-Plurality, while k-Borda has an axiomatic characterization.
- Representation rules: Chamberlin–Courant and Monroe rules optimize voter-to-committee assignments using satisfaction functions, with Monroe additionally imposing balanced representation constraints.The Borda satisfaction function is the paper’s focus.
- Approximation rules: Greedy-CC and Greedy-Monroe construct committees in k iterations by adding candidates that maximize the relevant utilitarian Borda satisfaction objective.They are efficiently computable for producing some winning committee, although parallel-universes tie-breaking complexity is unresolved.
- Best-k rules: SNTV and k-Borda are best-k rules, while Greedy-CC is also a best-k rule and Bloc is not.Best-k rules select the top k alternatives under a social preference or welfare ordering.
- Committee scoring rules: Separable committee-scoring rules are k-best rules, whereas weakly separable rules permit score functions that depend on committee size and remain polynomial-time computable under polynomial-time function families.The paper identifies committee scoring rules as generalizations of single-winner scoring rules.
4 Axioms
The paper introduces multiwinner axioms adapted from single-winner rules and designed for preference-based rules close to scoring rules. It emphasizes that their desirability depends on the application.
- Nonimposition requires every size-k candidate set to win, and all rules considered satisfy it.
- Monotonicity: Candidate monotonicity preserves a candidate in some winning committee after it moves forward, while non-crossing monotonicity can preserve the original committee under a restricted move.
- Committee monotonicity: Committee monotonicity requires winning committees at adjacent sizes to contain one another through suitable extensions and restrictions.
- Representation properties: Solid coalitions, consensus committee, and unanimity formalize increasingly structured forms of proportional or unanimous representation, while fixed majority requires a majority-supported committee to be uniquely selected.
- Fixed majority: Most considered rules fail fixed majority, but Bloc satisfies it; the authors caution that axiom desirability depends on the application.
5 Committee Monotonicity
Committee monotonicity is application-dependent: it is useful for expanding finalist sets but may conflict with proportional representation. The paper characterizes committee-monotone rules as best-k rules and evaluates the studied rules.
- Committee monotonicity is imperative for finalist selection but may be undesirable when proportional representation is the goal.
- A k-committee selection rule is committee monotonic if and only if it is a best-k rule.
- Rules satisfying the axiom: SNTV, k-Borda, separable committee scoring rules, and Greedy-CC satisfy committee monotonicity.
- Rules violating the axiom: STV, Bloc, ℓ1-CC, ℓmin-CC, ℓ1-Monroe, ℓmin-Monroe, and Greedy-Monroe do not satisfy committee monotonicity.
- Counterexamples: For ℓ1-CC, ℓmin-CC, ℓ1-Monroe, ℓmin-Monroe, and Greedy-Monroe, one example changes the unique winner from {c} at k = 1 to {a, b} at k = 2.
- Counterexamples: For Bloc, the unique winner changes from {a} at k = 1 to {b, c} at k = 2.
6 Dummett’s Proportionality
The paper evaluates proportionality properties based on Dummett’s condition, including solid coalitions, consensus committee, and unanimity. The rules differ substantially, with trade-offs between proportional representation and committee monotonicity.
- Solid coalitions: SNTV always satisfies solid coalitions, while STV satisfies it when n ≥ k(k + 1).
- Solid coalitions: ℓ1-CC, ℓmin-CC, ℓ1-Monroe, and ℓmin-Monroe fail solid coalitions, whereas Greedy-Monroe satisfies it.
- Consensus committee: When k divides n, every rule with solid coalitions satisfies consensus committee; this includes SNTV, sufficiently large-voter STV, and Greedy-Monroe.
- Consensus committee: Bloc, k-Borda, and Greedy-CC fail consensus committee and solid coalitions; Greedy-CC includes c in every winning committee although {a, b} is the consensus committee.
- Scoring-rule characterization: For separable committee scoring rules, consensus committee holds when γ(1) > kγ(2) with sufficiently many voters and fails when 0 < γ(1) ≤ kγ(2).
- Unanimity: Every committee scoring rule satisfies weak unanimity, while STV, Bloc, k-Borda, and the Monroe variants listed satisfy strong unanimity.
7 Monotonicity
The paper distinguishes candidate and non-crossing monotonicity and studies which multiwinner rules satisfy them. Committee scoring rules guarantee candidate monotonicity, while weakly separable rules guarantee non-crossing monotonicity, but several Monroe and greedy variants fail these criteria.
- Committee scoring rules: Every committee scoring rule satisfies candidate monotonicity, and every weakly separable committee scoring rule satisfies non-crossing monotonicity.The result follows by comparing how a forward shift changes scores for committees containing the moved candidate and for committees containing the overtaken candidate.
- Committee scoring rules: Non-separable committee scoring rules such as ℓ1-CC generally fail non-crossing monotonicity, because a shift can improve another committee while leaving the original committee unchanged.The paper gives an ℓ1-CC construction where shifting c increases {b,c}'s satisfaction while {a,c} remains tied before the shift.
- Specific rules: ℓmin-CC satisfies candidate monotonicity, whereas ℓmin-Monroe fails it; both rules fail non-crossing monotonicity.For ℓmin-CC, the candidate shift weakly improves committees containing c and weakly harms committees excluding c, but this argument does not extend to ℓmin-Monroe.
- Specific rules: ℓ1-Monroe, Greedy-Monroe, and Greedy-CC fail candidate monotonicity, while the remaining studied rules fail each monotonicity criterion.The greedy counterexamples show that shifting a candidate forward can change the winning committees so that the shifted candidate is no longer represented.
8 Consistency and Homogeneity
The paper relates consistency and homogeneity to the structure of multiwinner rules. Committee scoring rules satisfy consistency, while several Monroe and greedy variants fail consistency or homogeneity, with Monroe homogeneity recovered under a divisibility condition.
- Consistency: Every committee scoring rule satisfies consistency, whereas rules that are not scoring rules can fail it; STV, ℓmin-CC, and ℓmin-Monroe are excluded by their k = 1 behavior.For k = 1, these rules are not scoring rules, so Young’s result rules out consistency.
- Consistency: ℓ1-Monroe, Greedy-CC, and Greedy-Monroe are not consistent, despite each being equivalent to Borda when k = 1.The paper supplies separate election-combination counterexamples: ℓ1-Monroe changes from {a,c} to {a,b}, while Greedy-Monroe and Greedy-CC produce different combined-election winners.
- Homogeneity: ℓmin-CC and Greedy-CC satisfy homogeneity, while Monroe variants are generally not homogeneous.The paper attributes Monroe failures to rounding in the Monroe criterion rather than to the divisibility-respecting case.
- Homogeneity: ℓ1-Monroe and ℓmin-Monroe satisfy homogeneity when the number of voters n is divisible by committee size k.The proof transforms assignments across repeated copies of an election while preserving satisfaction and equal representation.
- Homogeneity: Greedy-Monroe fails homogeneity even when k divides the number of voters, although a refined intermediate tie-breaking procedure can restore homogeneity in that case.The negative result relies heavily on parallel-universes tie-breaking, and the paper notes that an alternative refinement is possible.
9 Related Literature
The related literature on multiwinner-rule properties is sparse and distributed across several fields. The paper is closest to Felsenthal and Maoz but differs in its rule set and stronger emphasis on proportional representation, while also connecting to characterization, approval-based, paradox, and computational work.
- Research landscape: Research on multiwinner-rule properties remains relatively sparse and scattered across behavioral science, political science, social choice theory, and computer science.This dispersion makes comparisons across models and properties difficult.
- Closest related work: Felsenthal and Maoz study SNTV, Approval, k-Borda, and STV, whereas this paper studies Bloc and several proportional-representation-focused rules instead of Approval.Both papers adapt single-winner properties, including monotonicity, to multiwinner elections.
- Closest related work: This paper introduces axioms aimed at proportional representation, including consensus committee and solid coalitions, and omits Condorcet-related axioms considered by Felsenthal and Maoz.The difference reflects a distinct choice of normative emphasis rather than a complete separation from prior work.
- Characterization results: Prior work extends Young’s consistency characterizations to multiwinner settings, including Debord’s characterization of k-Borda using neutrality, faithfulness, consistency, and cancellation.Consistency is also central in related studies of consensus-based multiwinner rules.
- Approval, paradoxes, and computation: Other literature studies approval-based committee rules, committee-size paradoxes, and computational hardness, including NP-hardness for STV with parallel-universes tie-breaking.Approximation rules such as Greedy-CC and Greedy-Monroe arose partly in response to computational difficulty.
10 Conclusions
The paper establishes a framework for comparing multiwinner voting rules through formal properties and identifies application-specific strengths, limitations, and research directions. It finds SNTV broadly satisfies the defined properties, while different rules suit finalist selection, recommendation, or proportional representation.
- The study formalizes natural properties and compares ten multiwinner rules, identifying best-k and committee scoring rules as two broad families.Committee scoring rules include both computationally easy rules such as k-Borda, SNTV, and Bloc and hard winner-determination rules such as ℓ1-CC.
- Best-k rules are well-suited to selecting competition finalists, whereas Monroe-based rules and STV seem more appropriate for proportional representation.The paper specifically connects these application choices to finalist selection and parliamentary elections.
- ℓ1-CC and ℓmin-CC seem better suited to movie selection than parliamentary elections because they may assign different numbers of voters to winning candidates.Using these rules for a parliament would require weighted voting, while recommendation systems only need users to find at least one satisfying item.
- Greedy-CC does not perform well in the comparison: it fails the solid coalitions property and the consensus committee property.The latter failure contrasts with every other rule considered that focuses on some form of proportional representation.
- A proposed research direction is modifying Greedy-Monroe to abandon Monroe’s criterion while optimizing the numbers of voters considered in each iteration.The paper presents this as a possible alternative to simply replacing Greedy-CC with Greedy-Monroe.
- SNTV satisfies all defined properties among the considered rules, though only weakly satisfies unanimity, while ignoring preferences beyond each voter’s top candidate.The authors relate its properties to an approximation of selecting every candidate ranked first by at least one voter, but note that it inherits Plurality’s negative features.