Source-linked AI summary
Justified Representation in Approval-Based Committee Voting
Haris Aziz, Markus Brill, Vincent Conitzer, Edith Elkind, Rupert Freeman, Toby Walsh
TL;DR
Approval-based committee voting needs representation guarantees when voters approve candidate subsets and committees must contain a fixed number of winners. This paper introduces and analyzes JR and EJR, showing that JR committees always exist but prominent rules can fail it, while PAV satisfies both properties.
Problem
Approval-based committee voting has had limited axiomatic analysis from the perspective of representation.
Method
The paper introduces JR and EJR and studies their existence, computation, voting-rule satisfaction, relationship to core stability, and algorithmic complexity.
Results
PAV satisfies JR and EJR, while RAV and several other prominent approval-based rules can fail JR; EJR characterizes PAV among weighted PAV rules.
Takeaways & Limitations
JR is always achievable by some efficiently computable committee, whereas EJR provides a stronger property that distinguishes PAV within weighted PAV rules.
Takeaways & Limitations
Whether the associated core is non-empty for every election and committee size remains open, and no considered rule is known to guarantee core stability whenever the core is non-empty.
Abstract
from arXiv · showhide
We consider approval-based committee voting, i.e. the setting where each voter approves a subset of candidates, and these votes are then used to select a fixed-size set of winners (committee). We propose a natural axiom for this setting, which we call justified representation (JR). This axiom requires that if a large enough group of voters exhibits agreement by supporting the same candidate, then at least one voter in this group has an approved candidate in the winning committee. We show that for every list of ballots it is possible to select a committee that provides JR. However, it turns out that several prominent approval-based voting rules may fail to output such a committee. In particular, while Proportional Approval Voting (PAV) always outputs a committee that provides JR, Reweighted Approval Voting (RAV), a tractable approximation to PAV, does not have this property. We then introduce a stronger version of the JR axiom, which we call extended justified representation (EJR), and show that PAV satisfies EJR, while other rules we consider do not; indeed, EJR can be used to characterize PAV within the class of weighted PAV rules. We also consider several other questions related to JR and EJR, including the relationship between JR/EJR and core stability, and the complexity of the associated algorithmic problems.
1 Introduction
This paper studies approval-based committee rules from a representation perspective, introducing justified representation and stronger variants while analyzing their existence, computation, and compatibility with voting rules.
- Setting: Approval-based committee voting selects a fixed-size winner set from voters’ approved candidate subsets.The paper situates this setting in applications including parliamentary elections, faculty hiring, and selecting plans or agents.
- Motivation: Representation has received less axiomatic analysis than the relative merits and computational complexity of approval-based rules.
- Contributions: Justified representation requires every sufficiently large group sharing a supported candidate to have at least one voter approving a committee member.
- Contributions: Every ballot profile admits a JR committee, which can be computed efficiently, and JR verification is polynomial-time.
- Contributions: Several prominent rules fail JR, whereas some weighted PAV rules satisfy it; PAV satisfies stronger EJR, while other strengthenings may be impossible to satisfy.The paper also relates JR and EJR to core stability and studies associated algorithmic questions.
2 Preliminaries
The paper formalizes approval-based multi-winner elections and defines the principal approval-based rules considered, including PAV, RAV, SAV, MAV, and related variants.
- Formal setting: An election consists of voters’ approval ballots, candidates, and a target committee size k; a voting rule returns a size-k winning set.
- Other rules: SAV maximizes the sum of fractions of approved candidates elected, while MAV minimizes the maximum Hamming distance between the committee and ballots.Approval adaptations of Chamberlin–Courant and Monroe use approval-based satisfaction, with Monroe additionally balancing voter assignments across committee members.
- PAV and weighted variants: PAV maximizes total voter utility with diminishing returns as voters receive more approved candidates in the committee.Its canonical utility uses marginal values 1, 1/2, 1/3, and so on.
- PAV and weighted variants: Weighted PAV replaces the canonical score sequence with a nonnegative weight vector, typically normalized to w1 = 1 and nonincreasing.The paper studies the resulting weighted PAV family without analyzing its algorithmic properties.
- Sequential rules: RAV converts PAV into a sequential rule that selects one candidate per round and reweights approvals for subsequent rounds.The canonical procedure uses each voter’s current representation count to determine later approval weights and was proposed as a tractable approximation to PAV.
- Sequential rules: Weighted RAV generalizes the sequential procedure through an arbitrary weight vector, while GAV selects candidates to cover as many currently uncovered voters as possible.GAV is the (1, 0, ...)-RAV variant; GAVT removes only a quota-sized subset of voters after each selection and adapts STV to approval ballots.
3 Justified Representation
Justified representation requires every sufficiently large group sharing an approved candidate to have at least one voter represented in the committee. Such committees always exist and can be found and checked efficiently, although JR differs from unanimity and several rules fail it.
- Definition and motivation: JR requires that no group of at least n/k voters sharing an approved candidate remains entirely unrepresented.Equivalently, every sufficiently large cohesive group must include a voter who approves at least one committee member.
- Existence and computation: For every ballot profile and committee size k, a committee providing JR exists and can be computed efficiently.GAV and GAVT both output committees that provide JR.
- Existence and computation: A polynomial-time algorithm decides whether a given committee provides JR.The test can focus on candidates and count voters approving each candidate who have no approved committee member.
- JR and unanimity: JR is strictly weaker than unanimity when k = 1.Unanimity implies JR, but a rule can satisfy JR while selecting a candidate outside the common approval set.
4 Justified Representation under Approval-Based Rules
The section tests justified representation across prominent approval-based rules, identifying both guarantees and failures under different committee sizes, assumptions, and tie-breaking conditions. PAV and MonAV always satisfy JR, whereas SAV, MAV, AV, and RAV can fail it in specified settings.
- AV satisfies JR for k = 2 only with JR-favoring tie-breaking, but fails JR for k ≥3.The k ≥3 construction has one voter approving c0 while the others approve c1 through ck, causing AV to omit c0.
- SAV and MAV fail JR even when k = 2.For SAV, the construction leaves a voter unrepresented; MAV has a separate construction in which every JR committee must contain z, but MAV does not select z.
- MAV satisfies JR under the restriction |Ai| = k for every voter and tie-breaking favoring JR-providing committees.The result is explicitly qualified by both the approval-set-size restriction and the tailored tie-breaking rule.
- PAV satisfies JR for every ballot profile, irrespective of the tie-breaking rule.
- RAV satisfies JR for k = 2 but fails it for k ≥10, and every w-RAV with w1 = 1 and w2 > 0 eventually fails JR.Theorem 8 guarantees a threshold k0 beyond which each such weighted RAV rule fails JR.
- MonAV satisfies JR.
5 Extended Justified Representation
EJR strengthens JR by requiring cohesive groups entitled to multiple representatives to give at least one member that many representatives. The paper proves PAV satisfies EJR, shows weighted-PAV uniqueness, relates EJR to core stability, and identifies computational barriers.
- Voting-rule guarantees: GAVT can violate EJR under some tie-breaking, and finding a tie-breaking rule that always avoids this may require exploring all intermediate ties.The authors conjecture suitable tie-breaking may always exist but do not provide a succinct formulation.
- Voting-rule guarantees: PAV satisfies EJR irrespective of tie-breaking, whereas MAV can fail EJR even when every voter approves exactly k candidates.An MAV example selects one candidate from each of four groups although one group deserves two representatives.
- Voting-rule guarantees: Every weighted-PAV rule other than canonical PAV fails EJR; some weighted-PAV rules also fail JR when a later weight is below its proportional threshold.The paper characterizes PAV as essentially the unique w-PAV rule satisfying EJR.
- JR, EJR, and core stability: EJR is equivalent to excluding profitable deviations by cohesive coalitions, but it is strictly weaker than full core stability.PAV can output an EJR committee whose payoff vector is outside the core, even when the core is non-empty.
- Computational issues: EJR computation is difficult: checking a committee is coNP-complete, while ℓ-JR can be computed in time polynomial in n and |C|^ℓ.The coNP-completeness proof reduces Balanced Biclique to the complement problem.
6 Variants of Justified Representation
The paper examines stronger variants of JR that demand broader or more uniform representation within cohesive groups. These variants form a hierarchy, but the strongest requirements can be infeasible and strong JR does not imply EJR.
- Definitions: Semi-strong JR requires every voter in a sufficiently large cohesive group to approve a committee member, while strong JR requires a common approved committee candidate.Both variants strengthen standard JR by imposing more uniform representation within the group.
- Definitions: Strong JR implies semi-strong JR, which implies standard JR.The hierarchy follows directly from the definitions.
- Feasibility: Some ballot profiles admit no committee providing semi-strong JR, so no approval-based rule can always find a committee satisfying strong or semi-strong JR.For k = 3 and n = 9, the illustrated profile would require four candidates although committees contain only three.
- Relationships: Strong JR does not imply EJR: with k = n = 4, {a, c, d, e} provides strong JR, but EJR requires selecting both a and b.The two axioms prioritize different forms of representation in this example.
7 Related Work
The paper places JR and EJR alongside probabilistic representativeness and proportional justified representation, emphasizing that these criteria address different notions of fair representation.
- Representativeness: Duddy’s probabilistic representativeness is incomparable with JR because it can require positive-probability selection of a candidate that JR need not select.The example contrasts JR’s requirement to select one of y or z with representativeness’s requirement to select x with positive probability.
- Proportional justified representation: Proportional justified representation (PJR) requires ℓ approved committee candidates across a cohesive group, possibly approved by different group members, rather than ℓ representatives for one voter.PJR is presented as an alternative to EJR and coincides with JR when ℓ = 1.
- Proportional justified representation: Many EJR results extend to PJR: every w-RAV rule violates PJR, while w-PAV satisfies PJR only for the canonical weight vector.This parallels the paper’s uniqueness result for EJR within weighted-PAV rules.
8 Conclusions
The paper identifies PAV as the prominent rule satisfying both JR and EJR, while highlighting computational complexity and open questions for EJR and related properties.
- PAV satisfies JR and the stronger EJR property, whereas many well-known approval-based rules fail JR.
- EJR characterizes PAV within the class of weighted PAV rules, subject to the stated qualification about tie-breaking.
- Open questions include efficiently finding EJR committees, selecting suitable GAVT tie-breaks, and testing JR's compatibility with strategyproofness.
- JR can define utilitarian and egalitarian rules that optimize AV score or the least-represented voter among committees satisfying JR or EJR.
- Winner determination for the introduced rules remains an interesting computational-complexity problem, and PAV is NP-hard to compute.