Justified Representation in Approval-Based Committee Voting

Haris Aziz, Markus Brill, Vincent Conitzer, Edith Elkind, Rupert Freeman, Toby Walsh

TL;DR

This paper introduces "Justified Representation" (JR) and "Extended Justified Representation" (EJR) as formal fairness axioms for multi-winner approval voting. The authors demonstrate that while many popular voting rules fail these representation standards, Proportional Approval Voting (PAV) uniquely satisfies EJR, providing a powerful theoretical justification for its use despite its computational complexity.

What Problem Does This Paper Address?

In multi-winner approval voting, each voter selects a subset of candidates they approve of, and the goal is to choose a fixed-size committee of $k$ winners. A naive approach like standard Approval Voting (AV)—where you simply pick the $k$ candidates with the most total votes—suffers from a major flaw: a 51% majority of voters can completely sweep the committee, leaving a 49% minority with zero representation.

While various voting rules have been proposed to ensure "proportionality," the social choice community lacked a precise, axiomatic definition of what constitutes fair representation in approval-based systems. This paper addresses this gap by formalizing what a cohesive group of voters "deserves" and evaluating prominent voting rules against these new benchmarks.

Methods

The authors employ axiomatic social choice theory and computational complexity analysis to introduce and evaluate two new properties:

  1. Justified Representation (JR): This axiom states that if a group of voters makes up at least $1/k$ of the electorate ($n/k$) and they all agree on at least one candidate, the winning committee cannot completely ignore them; at least one voter in this group must have an approved candidate elected.
  2. Extended Justified Representation (EJR): A stronger, scaled version of JR. It demands that if a larger cohesive group of voters ($\ge \ell \cdot n/k$) agrees on a set of at least $\ell$ candidates, then at least one voter in that group must see at least $\ell$ of their approved candidates make it onto the committee.

The authors mathematically test several voting rules—including Approval Voting (AV), Satisfaction Approval Voting (SAV), Minimax Approval Voting (MAV), Reweighted Approval Voting (RAV), and Proportional Approval Voting (PAV)—to see if they inherently guarantee JR or EJR.

Datasets

Not discussed in the paper. This is a theoretical and algorithmic paper that relies on mathematical proofs and synthetic counterexample profiles rather than empirical datasets.

Key Insights and Ideas

  • The Flaw in Greedy Approximations: Reweighted Approval Voting (RAV) was designed as a computationally efficient, sequential approximation of PAV. Surprisingly, the authors prove that RAV fails basic Justified Representation for committees of size $k \ge 10$. This reveals a critical tension: optimizing for computational efficiency can inadvertently destroy axiomatic fairness guarantees.
  • PAV’s Unique Excellence: Proportional Approval Voting (PAV) perfectly satisfies both JR and EJR. In fact, the authors show that EJR uniquely characterizes PAV within the entire class of weighted PAV rules.
  • The Complexity Asymmetry: There is a fascinating divide in verification complexity. Checking whether a given committee satisfies basic JR can be done quickly in polynomial time. However, checking if a committee satisfies the stronger EJR property is coNP-complete, mirroring the inherent difficulty of computing PAV itself.

Key Results

The paper maps out a clear taxonomy of which rules provide fair representation:

Rule Satisfies JR? Satisfies EJR? Computational Complexity
Approval Voting (AV) No (fails for $k \ge 3$) No In P
Satisfaction Approval Voting (SAV) No (fails for $k \ge 2$) No In P
Minimax Approval Voting (MAV) No (fails for $k \ge 2$) No NP-hard
Reweighted Approval Voting (RAV) No (fails for $k \ge 10$) No In P
Greedy Approval Voting (GAV) Yes No In P
Monroe Approval Voting (MonAV) Yes No NP-hard
Proportional Approval Voting (PAV) Yes Yes NP-hard
  • Verifying if a committee satisfies EJR is proven to be coNP-complete.
  • While finding an EJR committee is NP-hard, the authors present an algorithm ($\ell$-GAV) that can find a committee satisfying $\ell$-JR in polynomial time when $\ell$ is a constant ($O(n \cdot |C|^{\ell+1})$).

Limitations and Future Work

  • Computational Barriers: Because PAV is NP-hard to compute and EJR is hard to verify, implementing an EJR-compliant voting system at scale remains computationally daunting.
  • Tie-Breaking Anomalies: A sequential rule called $GAV^T$ (a variant of the Single Transferable Vote adapted for approval ballots) can satisfy EJR in some instances, but it fails under certain tie-breaking conditions. The authors note that finding an efficient, deterministic tie-breaking rule that preserves EJR for $GAV^T$ is an open challenge.
  • Game-Theoretic Links: The authors map EJR to "core stability" in cooperative game theory but show that core stability is too demanding—none of the studied rules guarantee a core-stable outcome. Exploring whether a core-stable committee always exists is left as an open question.

Summary updated

Abstract

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.
BibTeX
@inproceedings{aziz2014justified,
  author = {Haris Aziz and Markus Brill and Vincent Conitzer and Edith Elkind and Rupert Freeman and Toby Walsh},
  title = {{Justified Representation in Approval-Based Committee Voting}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2014},
  doi = {10.1609/aaai.v29i1.9324},
}
Figure