Source-linked AI summary
Jointly Satisfying Pareto Optimality and Justified Representation is NP-Hard in Approval-Based Multiwinner Voting
Chris Dong
TL;DR
The paper asks whether committees satisfying both justified representation and Pareto optimality can be computed efficiently across all approval profiles. It proves that computing such a committee is NP-hard, and that no tractable rule satisfies PJR and PO unless P=NP.
Problem
It was open whether a polynomial-time voting rule could always output a committee satisfying both justified representation and Pareto optimality across all approval profiles.
Source: §1 · pp. 1–2, §2 · p. 2Method
The proof uses an X3C instance and shows that an answer voter's approvals in a committee satisfying JR and PO determine whether the instance is a YES instance.
Source: §3 · p. 4Results
Takeaways & Limitations
There is no tractable rule satisfying PJR and PO unless P=NP.
Source: §3 · p. 3
Abstract
from arXiv · showhide
An open problem in approval-based multiwinner voting concerns whether we can efficiently compute committees that satisfy both justified representation and Pareto optimality. We answer this question negatively by proving that, on the domain of all profiles, outputting a committee satisfying both axioms is NP-hard. An initial proof was found by ChatGPT Astra. This was then verified and rewritten by the author.
1 Introduction
The paper addresses whether committees can be computed in polynomial time while satisfying both justified representation (JR) and Pareto optimality (PO). It proves that computing such a committee is NP-hard, despite prior results on the axioms individually and on restricted domains.
1 Introduction
- Although JR and PO are individually computable in polynomial time and are compatible, no polynomial-time rule achieving both was known.PAV is cited as a rule that always satisfies both axioms.Source: §1 · p. 1
- Computing a committee satisfying both JR and PO is NP-hard.The result applies to any voting rule that always outputs committees satisfying both axioms.Source: §1 · p. 1
- Known polynomial-time results for related guarantees apply to restricted preference domains, not the full domain of approval profiles.Examples include EJR+ with PO on interval domains and PAV on linearly consistent preferences.Source: §1 · p. 2
- Earlier results on JR with fractional PO do not directly settle whether JR and ordinary PO can be jointly computed on all profiles.The paper notes that prior fractional-PO results leave the arbitrary-rule question open or use a weaker fractional variant.Source: §1 · p. 2
2 Preliminaries
The preliminaries define approval-based multiwinner instances, committees, and voting rules, then introduce PO and proportional representation. They frame the open question of polynomial-time computation and state that the paper proves impossibility even using the weaker JR requirement.
2 Preliminaries
- An ABC instance consists of an approval profile and target committee size, and an ABC voting rule maps that instance to a committee.A committee is a subset of candidates of the specified size.Source: §2 · p. 2
- PO excludes committees that another committee can improve for at least one voter without reducing any voter's approved-candidate count.The comparison is based on each voter's number of approved candidates in the committee.Source: §2 · p. 2
- PJR requires each sufficiently large cohesive group to receive representation proportional to the number of candidates its members commonly approve.The definition quantifies over ℓ-cohesive groups for ℓ from 1 to the committee size.Source: §2 · p. 2
- The open question asks whether a polynomial-time ABC rule can combine proportional representation with PO.The cited formulation gives PJR as an example of proportionality.Source: §2 · p. 2
- The paper answers negatively by proving hardness even for JR, a weaker proportionality requirement than PJR.JR requires that each sufficiently large group agreeing on a candidate has at least one member represented.Source: §2 · p. 3
3 Main Result
The paper proves that computing a rule that always returns a committee satisfying both justified representation and Pareto optimality is NP-hard. Its reduction from Exact Cover by 3-Sets reads the answer from one voter’s approvals in any such committee.
3 Main Result
- Any voting rule that always outputs committees satisfying both Pareto optimality and justified representation is NP-hard to compute.The result is stated for all instances.Source: §3 · p. 3
- Lemma 1 decomposes demands summing to 3b into b triples so each voter appears exactly δv times, enabling filler candidates to restore approval counts.The construction uses this decomposition to complete the committee while matching each X3C voter’s target approval count.Source: §3 · pp. 3–4
- The reduction starts from Exact Cover by 3-Sets, builds six copies of the X3C construction plus an answer voter, and sets the committee size to k = 6t + 4.The construction has 18t + 11 X3C voters and one answer voter.Source: §3 · pp. 3–4
- The task is not vacuous: Proportional Approval Voting is known to output committees satisfying both axioms.Source: §3 · p. 3
- For any committee satisfying JR and PO, the X3C instance is a YES-instance exactly when the answer voter approves at least 6t − 2 selected candidates.In the forward direction, a cover yields a committee preserving every X3C voter’s approval count while giving the answer voter at least that many approvals.Source: §3 · pp. 4–5
- Conversely, that approval threshold leaves more than 6(t − 1) pairwise disjoint set candidates; the pigeonhole principle then yields an exact cover in one of the six copies.The proof removes at most three overlapping candidates before applying the pigeonhole principle.Source: §3 · p. 5