CS Paper Radar

The Complexity of Justified Representation with Additive Utilities

Carmel Baharav, Jakob de Raaij, Agnès Totschnig

cs.GT ·submitted 2026-09-02 02:59 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Robust Proportionality Axioms for Additive Utilities

cs.GT ·2026-10-11 ·Piotr Skowron
similarity 0.84
Abstract

We study the model of participatory budgeting, in which a subset of candidates is selected subject to a budget constraint. Voters express their preferences by assigning a numerical utility to each candidate. Our focus is on formal analysis of proportionality, a central notion of fairness in multi-winner elections. Intuitively, proportionality means that each group of voters should influence the election outcome roughly in proportion to its size. Recent "plus" axioms of proportionality are particularly appealing notions: they are verifiable in polynomial time, and they provide strong representation guarantees without requiring groups of voters to have cohesive preferences. However, their existing formulations are restricted to approval-based preferences. We generalise extended justified representation plus (EJR+), and Core plus (Core+) to general additive utilities. Our approach builds on a payment-based interpretation of proportionality: candidates' costs are shared among their supporters, with the aim of balancing voters' total payments.

0.33

Strengthening Proportionality in Participatory Budgeting with Additive Utilities

cs.GT ·2026-09-08 ·Tzeh Yuan Neoh, Nicholas Teh
similarity 0.81
Abstract

Proportional representation is a central goal in participatory budgeting, where voters select public projects subject to a shared budget. Full justified representation (FJR) accounts for groups whose members may value different projects, but computing an FJR outcome is strongly NP-hard for additive utilities. We show that FJR up to one project can be achieved in polynomial time for arbitrary nonnegative additive utilities and project costs. Our approach extends Residual-Budget Greedy and satisfies a stronger fractional axiom that can also be verified in polynomial time. For approval utilities, this axiom coincides with FJR+, providing exact FJR in that setting. We further show that every feasible completion of the algorithm's selected set preserves the representation guarantee, providing flexibility in allocating the remaining budget. In particular, we give a completion that ensures priceability at the original budget. For unit-cost projects, we strengthen the representation guarantee to the Droop quota and combine it with priceability whenever there are enough positively valued projects to fill the budget.

0.41

Strengthening Full Justified Representation: Efficient Verification and Computation

cs.GT cs.AIecon.TH ·2026-08-11 ·Nicholas Teh
highly cited similarity 0.81
Abstract

Full justified representation (FJR) is among the strongest known satisfiable proportionality axioms for approval-based committee elections. Recent work has shown that an FJR committee can be found in polynomial time, but verifying whether a given committee satisfies FJR remains coNP-complete. We introduce FJR+, a strict strengthening of FJR and EJR+ that can be verified and satisfied in polynomial time. We then analyze the Residual-Budget Greedy (RBG) algorithm and prove that it selects a partial committee such that every size-$k$ completion satisfies FJR+. This freedom allows us to use sequential Phragmén to obtain a priceable completion. The resulting rule always satisfies FJR+ and the sub-core, and it is priceable whenever at least $k$ candidates receive an approval. We also obtain a Droop-quota version of FJR+. Finally, we extend FJR+ to approval-based participatory budgeting with arbitrary project costs. A project-specific version of RBG computes this property in polynomial time and can be continued to a priceable outcome satisfying a cost-based version of the sub-core.

0.43

Full Justified Representation in Temporal Voting: Efficient Computation and Verification

cs.GT ·2026-09-22 ·Nicholas Teh
highly cited similarity 0.78
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

Proportional Representation in Temporal Voting with Ranked Preferences

cs.GT cs.AI ·2026-09-24 ·Noam Hazon, Leora Schmerler, Nicholas Teh
similarity 0.73
Abstract

We study proportional representation in temporal voting, where one candidate is selected in each round. While prior work has focused on approval ballots, we consider ranked preferences, which may change over time. A natural approach treats each voter's top candidates as approved, but the right cutoff may differ across voters and rounds. We therefore require proportionality to hold for every admissible choice of cutoffs, whether fixed and common, common but varying across rounds, or set individually for each voter in each round. Combining these interpretations with temporal versions of justified representation (JR), proportional JR (PJR), extended JR (EJR), and proportionality for solid coalitions (PSC) gives us a hierarchy of axioms. We ask which of these axioms can be guaranteed, and with how much knowledge of the future. Unlike with approval ballots, no version of EJR can be guaranteed, and for the other axioms, flexibility in the cutoffs comes at a price. With a fixed common cutoff, JR, PJR, and PSC can be guaranteed, but only by rules that see all preferences in advance. Once the cutoff may vary across rounds, even such rules cannot guarantee JR or PSC for groups that agree in only some rounds. For groups that agree in every round, however, knowing only the number of rounds suffices for PJR in polynomial time, and PSC needs no knowledge of the future at all. Under individual cutoffs, no version of JR or PJR can be guaranteed, yet a rule as simple as serial dictatorship achieves PJR up to an additive loss that no rule can improve on, however much it knows. Natural preference restrictions restore exact guarantees. Finally, we show that checking our axioms is often coNP-complete; but perhaps surprisingly, a stronger axiom can be easier to check.

0.27

Diverse Representation in Approval-Based Committee Voting

cs.GT ·2026-09-24 ·Julian Chingoma, Davide Grossi, Feline Lindeboom, Jan Maly
similarity 0.71
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

Multi-Winner Voting with Argumentative Ballots

cs.GT cs.AI ·2026-08-24 ·Ryuta Arisaka, Hirotaka Ono
similarity 0.71
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

Approval-Based Apportionment: Like Portioning, Approximately like Committee Voting

cs.GT ·2026-08-27 ·Paul Gölz, Hannane Yaghoubizade
similarity 0.71
Abstract

We study approval-based apportionment, a variant of committee elections in which candidates ("parties") can be selected several times. We show that the proportionality axioms EJR, EJR+, and FJR coincide, and so do PJR, PJR+, and FPJR; that Lindahl priceability, an axiom implying core stability, is equivalent to a notion of approximate optimality with respect to the proportional approval voting (PAV) score; and that locally PAV-optimal committees are priceable. Approval-based apportionment (where a candidate receives an integer number of seats) lies between committee elections (zero or one seat) and portioning (a fractional number of seats). We formally connect portioning and apportionment by giving a construction that lifts axioms from apportionment to portioning and preserves implications between them. Several of our new implications between apportionment axioms are natural from a portioning perspective, leading us to believe that apportionment sits closer to portioning than to committee elections. None of them holds in committee elections, but several extend approximately, which makes apportionment a fruitful setting for conjecturing approximate relationships in approval-based committee elections.

0.44