CS Paper Radar

Jointly Satisfying Pareto Optimality and Justified Representation is NP-Hard in Approval-Based Multiwinner Voting

Chris Dong

cs.GT econ.TH ·submitted 2026-09-08 07:27 UTC · v1

Abstract

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.

Comment
6 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Approval-Based Multiwinner Voting with Candidate Qualities

cs.GT ·2026-09-08 ·Niclas Boehmer, Chris Dong, Luca Kreisel, Markus Utke
similarity 0.71
Abstract · 47 pages

We initiate the study of a new model of approval-based multiwinner voting in which each candidate carries an exogenous quality score, capturing, for instance, the reliability of the candidate or their relevance to the context of the selection. Quality scores break with the standard assumption of approval-based multiwinner voting that candidates are fully defined by the set of their supporters. We rethink what proportional representation means in the presence of quality scores. For this, we introduce a threshold-based and a value-based family of axioms, analyze their relationships, satisfiability, and computational complexity, and present rules that achieve the strongest jointly satisfiable combinations of our proportionality axioms. We then analyze the compatibility of proportionality with the natural goal of maximizing the summed quality of the selected candidates. While imposing standard proportionality notions can lead to an almost complete loss of quality, we show that under a new class of reciprocal axioms, which scale a group's entitlement by the quality of its commonly approved candidate(s), there always exist proportional committees retaining at least 3/4 of the optimal summed quality, and such committees can be computed by our voting rules at no additional computational cost.

0.25

Finding Representative and Approximately Efficient Committees

cs.GT ·2026-09-07 ·Dominik Peters, Rohit Vaish, Jatin Yadav
similarity 0.69
Abstract

In approval-based committee voting, proportional approval voting (PAV) is a well-studied rule that combines proportional representation with Pareto efficiency. However, computing a PAV committee is NP-hard, raising a natural question: Can the proportionality and efficiency properties of PAV be achieved via computationally efficient procedures? We make two contributions toward answering this question. First, building on the known proportionality guarantees of the local-search-based variant of PAV (or local PAV), we systematically study its efficiency properties. We show that local PAV committees are weakly Pareto optimal, meaning that no other committee is strictly preferred by every voter. We also identify limitations: Local PAV guarantees only a $2$-approximation to fractional Pareto optimality ($2$-fPO) and a $2/3$-approximation to the optimal PAV score, and both bounds are tight. In contrast, global PAV is Pareto optimal and satisfies the stronger $α^\star$-fPO guarantee, where $α^\star \approx 1.346$ is the unique solution of $\int_0^{α^\star} \frac{1-e^{-y}}{y} \, dy = 1$, and this approximation is tight. Second, we design a polynomial-time algorithm that combines the best of these guarantees. The committee returned by our algorithm satisfies EJR$+$ (a proportionality guarantee), $α^\star$-fPO, and weak Pareto optimality. It also achieves a $0.79$-approximation to the optimal PAV score, matching the best possible polynomial-time approximation assuming $P \neq NP$. Our algorithm works by pipage rounding a concave relaxation of the PAV objective and using that committee to initialize local PAV, thereby combining global approximation guarantees with local search stability.

0.42

The Complexity of Justified Representation with Additive Utilities

cs.GT ·2026-09-02 ·Carmel Baharav, Jakob de Raaij, Agnès Totschnig
similarity 0.68
Abstract

We study the computational complexity of satisfying proportional representation -- in particular proportional, extended, and fully justified representation (PJR, EJR, and FJR) -- in participatory budgeting and committee elections with additive utilities. First, we give a complete picture of the complexity of the axioms for a constant number of voters or voter types. Second, we show that even for committee elections with integer utilities bounded above by a small constant, satisfying FJR is intractable, giving the first strong NP-hardness result for a justified representation axiom. Third, we extend the Expanding Approvals Rule to committee elections with additive utilities and show that it satisfies PJR. Lastly, we show that no sequential voting rule can improve on the known positive result, thus proving that novel, substantially different voting rules are needed to surpass these boundaries. Beyond their theoretical merit, our results carry practical importance, as multi-winner voting with additive utilities has recently been gaining prominence in online deliberation and real-world participatory budgeting.

0.29

Full Justified Representation in Temporal Voting: Efficient Computation and Verification

cs.GT ·2026-09-22 ·Nicholas Teh
highly cited similarity 0.67
Abstract

In temporal voting, a fixed set of voters makes a collective decision in each of several rounds, and proportionality requires that groups with shared interests be represented across these decisions. Full justified representation (FJR) is among the strongest proportionality axioms known to be satisfiable in this setting, since it allows different members of a group to be satisfied by different selected candidates. However, whether an FJR outcome can be computed in polynomial time has remained open. We resolve this question by introducing temporal FJR+, a strengthening of both FJR and extended justified representation+ (EJR+) that can be computed and verified in polynomial time. The axiom measures a group's agreement in each round by the largest number of its members who approve a common candidate, and requires some member to attain the integer part of the group's proportional share of its best attainable average satisfaction, with a shortfall of at most one unit when this share is an integer. We show that verification reduces to counting approvals among the voters below each satisfaction threshold. For computation, we observe that local search for Proportional Approval Voting (PAV) can stop at an outcome violating FJR. Somewhat counterintuitively, the remedy is to subtract a small multiple of the minimum voter satisfaction from the PAV score: every FJR+ violation then admits a single-round change whose improvement guarantees polynomial running time. We further show that temporal FJR+ is strictly stronger than FJR and EJR+ combined, and coincides with lower quota on party-list preferences. Finally, temporal FJR+ and multiwinner FJR+ are incomparable in general, but coincide when approvals are static and each candidate-round pair is treated as a separate candidate.

0.32

Diverse Representation in Approval-Based Committee Voting

cs.GT ·2026-09-24 ·Julian Chingoma, Davide Grossi, Feline Lindeboom, Jan Maly
similarity 0.66
Abstract

The study of approval-based committee voting has so far focused predominantly on proportional representation. The canonical notion of diverse representation, based on the Chamberlin-Courant score, counts the number of voters with at least one representative in the committee, making it an individualistic notion. We develop a more comprehensive theory that instead requires the representation of many groups of voters, grounding it in the justified representation (JR) axiom, which we strengthen in two directions. First, we study the existing axioms of Strong JR (SJR) and Semi-Strong JR (SSJR), which consider the same cohesive groups as JR but demand stricter representation. We show that neither can be optimized efficiently on general domains (unless P = NP), but both can be on the Candidate Interval and Voter Interval domain. Second, to capture the unique and defining opinions of a group, we introduce Distinctive Representation (DR) and its local optimization variant, Local DR. We address satisfiability and computation time, and show (Local) DR to be distinct from known proportionality and diversity axioms. Experiments on real-world and synthetic data show that Local DR performs well on multiple empirical measures of diversity.

0.05

Nash Core in Multiwinner Election

cs.GT ·2026-08-31 ·Ashish Goel, Zhihao Jiang, Chenghan Zhou
theory similarity 0.66
Abstract

In the approval-based committee selection problem, a committee is said to be in the core if no subset of voters has an incentive to deviate by selecting a \emph{blocking} committee of proportional size, such that every voter in the deviating group strictly prefers the blocking committee. We consider the setting where candidates can be selected fractionally. Under a mild regularity assumption, we show that there always exists a weighting of candidates such that the fractional committee maximizing the candidate-weighted Nash Social Welfare is in the core. We refer to such a solution as being in the \emph{Nash core}. Additionally, we show that a Nash core solution admits a payment assignment between voters and candidates, where each voter pays a candidate they approve in proportion to the weight. For the discrete setting, where each candidate is either included or excluded from the committee, we prove that every approval-based committee election with at most eight equally weighted voters has a core committee by rounding the fractional Nash core solution. Although the non-emptiness of the core in this setting remains an open question and checking core membership is coNP-hard, we extend the notion of the Nash core to the discrete case, yielding a formulation that is efficiently verifiable and offers a promising path toward establishing core existence in discrete settings. Finally, we test our approach on real voting data using a payment-guided heuristic. We empirically show that the Nash core solution can be efficiently computed through an iterative algorithm in both the fractional and discrete settings.

0.38

Proportionality in Elections under Feasibility Constraints and Ranked Ballots: The Solid Coalition Refinement Rule

cs.GT ·2026-11-06 ·Grzegorz Kwacz, Georgios Papasotiropoulos, Piotr Skowron
similarity 0.65
Abstract

We study elections with ranked ballots and general feasibility constraints, which indicate which sets of candidates are allowed as outcomes. We introduce the first proportionality axiom for this general setting and show that it extends the established notions from specific models that fit our general framework. We extend the Solid Coalition Refinement (SCR) rule to general constraints and prove that it satisfies our axiom exactly for matroid constraints. Although the naive implementation of SCR involves a step that is computationally intractable for weak orders, we show that in practical cases it can be implemented in polynomial time or efficiently in FPT time. We also illustrate limitations of this rule for approval ballots and provide its first empirical evaluation.

0.08

Multi-Winner Voting with Argumentative Ballots

cs.GT cs.AI ·2026-08-24 ·Ryuta Arisaka, Hirotaka Ono
similarity 0.65
Abstract · Corrected Example 1, reflected the update to page 6's counts of winner sets proving axioms for the robust h. No definitions, propositions, l…

We introduce multi-winner voting with argumentative ballots (MVArg) and investigate theoretical properties. As our conceptual contribution, we generalise approval ballots to argumentative ballots, thereby allowing voters to express defeasible preferences over candidates. We accordingly generalise voter cohesion and justified representation axioms JR, PJR and EJR. As our theoretical contribution, we establish several key results. First, MVArg is strictly more expressive than multi-winner voting with approval ballots (MV). Second, our notions of cohesion and justified representation are conservative generalisations of their counterparts in MV. Third, the MVArg counterpart of JR can always be satisfied, whereas the counterparts of PJR and EJR cannot always be. Fourth, although verifying whether a winner set satisfies the MVArg counterpart of JR is already coNP-hard, such a winner set can be constructed in polynomial time. All definitions, propositions, auxiliary lemmas and theorems have been formalised and mechanically checked in Lean 4.

0.24