Source-linked AI summary
Proportional Justified Representation
Luis Sánchez-Fernández, Edith Elkind, Martin Lackner, Norberto Fernández, Jesús A. Fisteus, Pablo Basanta Val, Piotr Skowron
TL;DR
The paper examines how to represent cohesive voter groups while reconciling proportional representation with Perfect Representation. It proposes Proportional Justified Representation as a relaxation of EJR and shows that it is compatible with PR, while EJR offers stronger average-satisfaction guarantees.
Problem
Multi-winner elections need axioms ensuring that large groups of voters with cohesive preferences are adequately represented, but PR and EJR are incompatible.
Method
The paper proposes Proportional Justified Representation, a relaxation of EJR, and studies its compatibility, computational properties, and relationship to voting rules.
Results
PJR is compatible with PR and satisfied by several well-known rules, whereas EJR guarantees higher average satisfaction for members of large cohesive groups than PJR.
Takeaways & Limitations
PJR offers a representation requirement suitable for rules that prioritize compatibility with PR, while EJR may be preferable when average satisfaction of cohesive groups is the priority.
Takeaways & Limitations
Deciding whether a PR committee exists is NP-complete, and FPR is fundamentally incompatible with polynomial-time computability assuming P ≠ NP.
Abstract
from arXiv · showhide
The goal of multi-winner elections is to choose a fixed-size committee based on voters' preferences. An important concern in this setting is representation: large groups of voters with cohesive preferences should be adequately represented by the election winners. In an influential paper, Aziz et al. proposed two axioms that aim to capture this idea: justified representation (JR) and its strengthening extended justified representation (EJR). We observe that EJR is incompatible with the highly desirable Perfect Representation (PR) criterion, and propose a relaxation of EJR, which we call Proportional Justified Representation (PJR). PJR is more demanding than JR, but, unlike EJR, it is compatible with PR, as well as with a stronger variant of this axiom, which we term Fractional Perfect Representation (FPR). Moreover, just like EJR, PJR can be used to characterise the classic Proportional Approval Voting (PAV) rule in the class of weighted PAV rules. On the other hand, we show that EJR provides stronger guarantees with respect to average voter satisfaction than PJR does.
1 Introduction
Multi-winner elections require representation axioms for cohesive voter groups, but EJR conflicts with Perfect Representation. The paper introduces PJR as a compatible relaxation and studies its computational, axiomatic, and satisfaction guarantees.
- 1 Introduction: Multi-winner elections select fixed-size committees intended to represent voters’ differing preferences across political, organizational, and machine-learning applications.Applications include parliaments, committees, recommender systems, dataset construction, and core-set selection.
- 1 Introduction: JR requires a sufficiently large cohesive group to receive at least one representative, while EJR requires several representatives when the group is sufficiently large and cohesive.Aziz et al. showed that an EJR committee always exists, and that PAV is the only considered weighted rule satisfying EJR.
- 1 Introduction: Perfect Representation requires a committee to represent all voters equally whenever such a committee exists, but it is incompatible with EJR.The paper gives an election in which the committees satisfying PR and EJR are disjoint.
- 1 Introduction: PJR is more demanding than JR and, unlike EJR, is compatible with PR and FPR.FPR extends PR to all committee and electorate sizes through fractional vote allocation, and a rule satisfying both FPR and PJR exists.
- 1 Introduction: PJR can be satisfied by several established rules, including Greedy Monroe when k divides n, and characterises PAV within weighted PAV rules.Some of the relevant rules are efficiently computable.
- 1 Introduction: EJR provides much stronger average-satisfaction guarantees for large cohesive groups than PJR, making the two axioms express a representation trade-off.The paper discusses choosing between stronger average satisfaction and compatibility with perfect representation depending on the application.
2 Preliminaries
The paper formalizes approval-based multi-winner elections, representation axioms, and the voting rules used in its analysis. It defines weighted and sequential Thiele rules, Monroe variants, and cohesive-group representation requirements.
- 2 Preliminaries: An approval-based multi-winner election consists of voters, candidates, approval ballots, and a target committee size k; a voting rule returns k winners.Each ballot is a subset of candidates approved by one voter.
- 2 Preliminaries: A w-Thiele rule scores a committee by assigning a voter the cumulative weights w1 + ··· + wp when she approves p committee members.The committee with the highest summed score wins; PAV uses the harmonic weights (1, 1/2, 1/3, ...).
- 2 Preliminaries: Sequential Thiele rules build committees one candidate at a time by selecting the candidate that maximizes the improvement in total weighted approval score.Seq-PAV is the sequential rule associated with the harmonic weight vector.
- 2 Preliminaries: The Monroe rule maximizes approval utility subject to assigning voters to winners through a valid mapping with constrained representation loads.Greedy Monroe instead proceeds in k rounds, assigning approximately n/k unsatisfied voters to each selected candidate while maximizing approvals.
- 2 Preliminaries: The paper’s rule properties generally hold for every tie-breaking mechanism, even when multiple committees or candidate choices maximize the relevant score.This convention applies to both score-maximizing and sequential rules unless stated otherwise.
- 2 Preliminaries: JR and EJR are defined through ℓ-cohesive voter groups: JR requires one representative, while EJR requires that some group member obtain at least ℓ approved winners.EJR implies JR; PAV satisfies EJR, while Monroe satisfies JR but not EJR.
3 Perfect Representation
Perfect Representation (PR) requires a rule to select a committee that represents every voter and assigns the same number of voters to each winner whenever such a committee exists. The paper shows that PR is appealing but computationally difficult, incompatible with EJR, and relevant to how committees make collective decisions.
- PR requires every voter to approve their assigned winner, with each winning candidate assigned the same number of voters, whenever such a committee exists.In parliamentary applications, this captures equal representation and approval-based coverage.
- The Monroe rule satisfies PR, because, when k divides n, a PR committee is exactly a committee with maximum possible Monroe score.
- NP-complete: deciding whether any PR committee exists when k divides n.The membership proof reduces the problem to b-matching, while hardness adapts a reduction from EXACT COVER BY 3-SETS.
- PAV and seq-PAV can fail PR even when a unique PR committee exists, whereas Greedy Monroe can break ties to output a PR committee.
- PR and EJR are incompatible: some elections admit PR committees, but none of those committees provides EJR.Theorem 2 gives an instance with a unique PR committee that fails EJR because a cohesive voter group approves two candidates absent from that committee.
- PR committees can align committee decisions with majority preferences when voters assigned to each winner agree with that winner on every issue.The paper also presents examples where disagreement committees make more majority-consistent decisions than consensus committees, and where EJR committees can vote against a majority.
4 Proportional Justified Representation
PJR relaxes EJR by requiring cohesive voter groups to receive collectively enough approved winners, while remaining stronger than JR. Unlike EJR, PJR is compatible with PR, and it supports polynomial-time and axiomatic results under specified conditions.
- Definition: PJR requires every ℓ-cohesive voter group to have at least ℓ collectively approved candidates in the committee.This collective requirement replaces EJR’s requirement that one group member receive at least ℓ representatives.
- Relationship to JR and EJR: EJR implies PJR, and PJR implies JR.Thus, the proposed axiom lies between the two established representation requirements.
- Compatibility with PR: PR implies PJR, establishing compatibility between perfect representation and proportional justified representation.The result applies to every profile and target committee size whenever a PR committee exists.
- Representation guarantees: At most ⌈n/k⌉−1 voters in a 1-cohesive group can remain unrepresented by a JR committee, and this bound is tight even for EJR committees.Example 4 realizes the bound with voters in N1 remaining unrepresented.
- Computational results: When k divides n, Monroe and Greedy Monroe output committees satisfying PJR; Greedy Monroe is polynomial-time computable.If k does not divide n, both rules may fail PJR, as shown by Example 5.
- Characterization: PJR characterizes PAV within weighted Thiele rules, while every sequential weighted Thiele rule fails PJR.The characterized weight vector is w = (1, 1/2, 1/3, ...).
5 Average Satisfaction
The paper compares average voter satisfaction guarantees for JR, EJR, and PJR. EJR gives stronger general guarantees than PJR, although PJR matches EJR for very cohesive groups.
- Measure: Average satisfaction measures how many approved committee members voters in a specified group receive on average.The measure is introduced for a ballot profile, committee, and voter group.
- JR: JR alone guarantees a lower bound on average satisfaction for every ℓ-cohesive group when k divides n.The analysis assumes k divides n to avoid technical complications.
- EJR: EJR provides a much stronger average-satisfaction guarantee than JR for ℓ-cohesive groups.The proof classifies voters by how many approved committee members they receive and derives the bound from EJR.
- EJR: The lower bound for EJR is obtained by combining satisfaction levels across disjoint groups of voters, yielding an average of at least ℓ−1.The construction uses groups of voters who are j-happy for successive values of j.
- PJR: PJR’s worst-case average-satisfaction guarantee is no stronger than JR’s.Example 6 gives a PJR and PR committee whose n-cohesive group has average satisfaction 1.
- Very cohesive groups: For very cohesive groups, PJR and EJR guarantee average satisfaction at least ℓ, while JR may guarantee only 1.This applies when a group of at least ℓ·n/k voters approves exactly the same candidate set of size at least ℓ.
6 Fractional Perfect Representation
Fractional Perfect Representation generalizes Perfect Representation to elections where k does not divide n by allowing fractional vote allocation. It is compatible with PJR and imposes strong representation constraints, but deciding whether an FPR committee exists is NP-complete.
- Definition: FPR extends PR to all committee and voter counts by allowing non-integer vote allocation.PR only constrains elections where k divides n.
- Relation to PR: When k divides n, a committee provides FPR if and only if it provides PR.For other values of k and n, FPR can apply even when PR does not.
- Computational complexity: NP-complete is the complexity of deciding whether a committee provides FPR or whether any FPR committee exists.The existence problem is stated for a ballot profile and target committee size.
- FPR and Monroe: FPR can conflict with the Monroe rule’s possible outputs, although tie-breaking in favor of FPR committees makes Monroe satisfy FPR.Every FPR committee has the maximum possible Monroe score, equal to n.
- Relations with other axioms: Every FPR committee also provides PJR and PJR+, while FPR is incomparable with strong justified representation and individual representation.The incomparability is established using separate counterexamples in both directions.
- Satisfaction guarantees: FPR guarantees average satisfaction at least 1 for every voter group and at least ℓ for sufficiently large groups approving a common set of size at least ℓ.The bound is tight: Example 6 shows that stronger worst-case guarantees are impossible for FPR or PR.
- Apportionment: FPR committees correspond exactly to committees priceable with price p = n, and FPR-satisfying rules induce weakly proportional apportionment methods.The apportionment construction forces exactly S_j selected candidates from each candidate set C_j.
- Laminar proportionality: Laminar proportionality implies FPR for laminar elections, but the converse fails, making the two notions incomparable overall.The paper gives an FPR committee that is not laminar proportional and notes that FPR applies to some non-laminar elections.
7 Discussion
The discussion presents PJR as a PR-compatible alternative to EJR, while recognizing that EJR gives stronger average-satisfaction guarantees. It also highlights computational limits of perfect representation and application-dependent trade-offs between fairness properties.
- Contributions: EJR is incompatible with perfect and fractional perfect representation, whereas PJR is compatible with PR and FPR.The paper motivates PJR as an alternative that still seeks several representatives for large cohesive groups.
- Properties of PJR: PJR is satisfied by several established rules, including efficiently computable rules under some conditions, and characterises PAV within weighted PAV rules.For Greedy Monroe, the stated condition is that k divides n.
- Trade-off with EJR: EJR guarantees substantially higher average satisfaction for large cohesive groups than PJR in general.The paper describes this as a reason to view EJR as a more pragmatic requirement in applications willing to trade off other agents’ satisfaction.
- Applications: MMS offers PJR, polynomial-time evaluation, and a worst-case constant-factor approximation to leximax-Phragmén, which satisfies PR.This combination is presented as useful when selection committees must later vote on issues.
- Scope: PR and FPR impose strong constraints only when achievable, unlike JR variants, which always admit a satisfying committee.The paper notes that many elections do not admit perfect or fractional perfect representation.
- Limitations: PR and FPR are fundamentally incompatible with polynomial-time computability unless P = NP.The paper identifies efficient computation of FPR committees as an open direction.