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:
- 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.
- 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