PaperlayerView exact revision on arXiv

Source-linked AI summary

The Complexity of Justified Representation with Additive Utilities

Carmel Baharav, Jakob de Raaij, Agnès Totschnig

arXiv:2609.02030v1cs.GT

TL;DR

The paper asks where computational tractability ends for PJR, EJR, and FJR with additive utilities in participatory budgeting and committee elections. It analyzes restricted voter populations, extends the Expanding Approvals Rule, and studies sequential-rule limits, finding strong FJR hardness and boundaries that sequential rules cannot surpass.

  • Problem

    The paper addresses the incomplete complexity landscape for satisfying justified-representation axioms with additive utilities, including whether sequential rules can achieve stronger proportionality.

  • Method

    The paper characterizes tractability and hardness across voter, utility, and cost restrictions, extends the Expanding Approvals Rule, and analyzes sequential voting rules with bounded lookahead.

  • Results

    The paper proves strong NP-hardness for FJR with bounded integer utilities, gives an additive-utility rule satisfying PJR, and proves sequential rules cannot attain stronger guarantees in the stated settings.

  • Takeaways & Limitations

    The sequential-rule limitations indicate that surpassing these proportionality boundaries requires voting rules substantially different from existing sequential rules.

  • Takeaways & Limitations

    The sequential-rule impossibility results apply to rules whose decisions use only the current outcome and at most β additional alternatives.

Abstract

from arXiv · show

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.

1 Introduction

The paper maps the computational complexity of PJR, EJR, and FJR for additive utilities, focusing on intermediate settings between approval-based committee elections and general participatory budgeting. It establishes tractability and hardness boundaries for restricted voter populations, bounded utilities, and sequential rules.

  • The work studies justified representation with additive utilities between approval-based committee elections and general participatory budgeting.
  • For a constant number of voters or voter types, the paper gives a complete complexity account for finding outcomes satisfying PJR, EJR, and FJR.
  • Strong NP-hardness holds for finding an FJR outcome with unbounded voters, unit costs, and utilities in {0, 1, ..., 5}.
  • The Expanding Approvals Rule is extended to additive-utility committee elections and proved to satisfy PJR.
  • Sequential voting rules cannot improve the positive boundary: no such rule satisfies EJR for unit costs and utilities in {0, 1, 2, 3}.The paper also gives an analogous impossibility for PJR with cost-utilities whose costs lie in {0, 1, 2, 3}.

2 Preliminaries

The paper models participatory budgeting and committee elections with additive utilities, then defines proportional representation through coalition demands and three increasingly strong justified-representation axioms. FJR implies EJR, which implies PJR, and FJR outcomes always exist.

  • A participatory budgeting instance contains voters, alternatives, costs, a budget, and additive utility functions; feasible outcomes respect the budget.
  • Unit costs produce committee elections, while approval preferences restrict utilities to {0, 1} and cost utilities restrict them to {0, cost(c)}.
  • Proportional representation requires sufficiently cohesive voter coalitions to receive utility from alternatives proportional to their population and budget shares.
  • PJR, EJR, and FJR differ in how coalition cohesion and voter attachment to the outcome are formalized.
  • FJR implies EJR, EJR implies PJR, and every participatory budgeting instance has an outcome satisfying FJR.

3 Constant Number of Voters

For a constant number of voters, polynomially bounded utilities permit efficient FJR computation, whereas general utilities make FJR intractable even with two voters and unit costs. Polynomially bounded costs support efficient EJR computation under a logarithmic voter bound, but not general FJR.

  • A single-voter Knapsack reduction makes finding PJR, EJR, or FJR outcomes intractable for general utilities and costs unless P = NP.
  • When the number of voters is constant and utilities are polynomially bounded, GCR can find an FJR outcome in polynomial time with general costs.
  • GCR computes coalition-alternative tuples by dynamic programming over voter subsets and utility values.
  • No polynomial-time voting rule can guarantee FJR for all instances with two voters, general utilities, and unit costs.
  • mGCR satisfies EJR and is polynomial-time computable for logarithmically many voters, general utilities, and polynomially bounded costs.
  • Together, these results give a complete complexity picture for PJR, EJR, and FJR with a constant number of voters.

4 FJR Hardness

The section establishes strong intractability for satisfying FJR even with utilities bounded by 5, using reductions from PartialTripleCover, while EJR hardness remains conditional on an unresolved promise problem.

  • Motivation: Verifying justified representation is coNP-complete, but finding an outcome satisfying PJR, EJR, or FJR has had few known hardness results.The prior finding concerned general utilities and costs with one voter, where finding a PJR committee solves Knapsack.
  • FJR hardness: Unless P = NP, no polynomial-time voting rule satisfies FJR for committee elections with utilities in {0, 1, ..., 5}.The constructed selfish committee fails FJR when a partial triple cover exists and is uniquely FJR-satisfying otherwise.
  • Reduction: PartialTripleCover is NP-hard and asks whether equally sized nonempty vertex sets have at least three neighbors in T for every vertex in S.The reduction encodes graph vertices as voters and alternatives, with edge-based utilities and selfish alternatives valued at 5.
  • FJR hardness: The same reduction pattern yields FJR hardness for cost-utilities whose costs lie in.The result is stated as a modification using a bounded cost range, with the proof deferred to an appendix.
  • EJR boundary: EJR hardness is reduced to the promise problem Bb-Pmc, but its NP-hardness is unknown, so the corresponding bounded-utility impossibility remains conditional.If Bb-Pmc were NP-hard, no polynomial-time rule would satisfy EJR for utilities bounded above by 2n unless P = NP.

5 PJR for Committee Elections

The section extends the Expanding Approvals Rule to additive-utility committee elections and proves that the resulting rule satisfies PJR, regardless of budget deductions or tie-breaking.

  • Rule and guarantee: EAR is extended from ordinal committee preferences to additive utilities, where it is shown to imply PJR.The original ordinal version is known to satisfy rankPJR.
  • Rule and guarantee: EAR starts with empty W, threshold t equal to the maximum utility, and each voter’s budget k/n.It adds an alternative when voters valuing it at least t have total budget at least 1, deducting one unit and lowering t when necessary.
  • Robustness: The PJR guarantee holds for every way of deducting one unit of total budget and every tie-breaking rule.This makes the guarantee independent of how the budget reduction is distributed among qualifying voters.
  • Boundary: No budget-splitting choice gives EJR, although EAR’s additive-utility extension satisfies PJR.The stronger EJR guarantee is explicitly ruled out for all choices of how the budget is split.
  • Proof idea: For each ordered group of demanded alternatives, the proof constructs distinct selected alternatives whose utilities meet the corresponding minimum utility thresholds.The argument examines the algorithm before lowering the threshold below each group’s minimum and uses the remaining group budget to derive a contradiction.

6 The Limitations of Sequential Voting Rules

The section formalizes sequential rules with bounded lookahead and proves that they cannot guarantee EJR or PJR, showing that surpassing these boundaries requires structurally different rules.

  • Model: A sequential rule with β-lookahead selects each next alternative or termination option using a marginal score based on the current outcome and at most β additional alternatives.Zero lookahead gives ordinary sequential voting rules, and tie-breaking is consistent across stages.
  • EJR limitation: No sequential voting rule with β-lookahead guarantees EJR, even with n = β + 2, unit costs, and utilities in {0, ..., 2β + 3}.The proof uses two elections indistinguishable at the first choice but having disjoint unique EJR committees.
  • Model: The impossibility applies to the instance-independent tie-breaking orders allowed in the model.The order may depend on costs and utility vectors but not on the instance itself.
  • PJR limitation: No sequential voting rule with β-lookahead guarantees PJR, even for n = 1 and cost-utilities in {0, ..., β + 3}.Two instances have disjoint unique PJR outcomes while appearing identical to the rule when selecting the first alternative.
  • Implications: Known polynomial-time justified-representation rules are almost all sequential, while local-search PAV is restricted to approval preferences and unit costs and does not extend naturally to the general setting.The paper leaves open whether a different polynomial-time local-search method can overcome the sequential barriers.
  • Implications: Rules that overcome both boundaries must be structurally different from the polynomial-time voting rules considered so far.The conclusion follows from the barriers for sequential rules and the limited scope of the known non-sequential alternative.

7 Discussion

The paper advances understanding of justified representation by narrowing computational boundaries and identifying limitations of sequential voting rules. It also emphasizes that satisfying a representation axiom alone does not ensure a generally desirable voting rule.

  • The results move closer to fully understanding computational boundaries for justified representation with additive utilities.
  • Strong NP-hardness for FJR and sequential-rule limitations address open questions about efficient representation guarantees.
  • FJR satisfaction alone does not guarantee desirable behavior, since GCR fails laminar proportionality.
  • Whether more natural FJR rules or practical rules stronger than MES and EAR exist remains open.

A.1 Proof of Efficient GCR DP Subroutine for Lemma 1

The appendix specifies a dynamic program that computes minimum-cost alternative subsets meeting prescribed utility conditions for each voter subset. Its correctness follows by induction over prefixes of the alternatives.

  • The recurrence compares excluding and including the current alternative, adding its cost when all resulting utility requirements remain nonnegative.
  • The resulting table supports extracting the largest achievable common utility level under the budget constraint.
  • The DP processes alternatives prefix by prefix and stores minimum costs for exact utility vectors across voters in S.For each prefix j and utility vector, A[j][x1,...,xℓ] records the minimum cost among feasible subsets.
  • The table is initialized with zero cost for the empty set at the all-zero utility vector and infinity elsewhere.
  • Induction proves that no cheaper feasible subset can arise through either excluding or including the current alternative.

A.2 Proof of Lemma 2

The modified Greedy Cohesive Rule selects utility-maximizing cohesive groups and satisfies EJR while respecting the budget. The proof rules out any EJR violation by comparing the first deactivated voter with the selected tuple.

  • mGCR repeatedly selects a tuple maximizing β, adds its alternatives, and deactivates the associated voters.
  • mGCR satisfies EJR.
  • Any alleged EJR violation contradicts the choice of the first deactivated voter, because the selected tuple has β′ ≥ β.
  • The contradiction establishes that no EJR violation can occur in an mGCR outcome.
  • The rule respects the budget because each selected bundle deactivates at least n · cost(T)/B voters.

A.3 Proof of Theorem 3

The theorem proves that no polynomial-time voting rule can guarantee FJR even with two voters and unit costs unless P = NP. The reduction encodes Restricted-Knapsack so that FJR satisfaction distinguishes satisfiable from unsatisfiable instances.

  • Unless P = NP, no polynomial-time voting rule guarantees FJR for all two-voter elections with general utilities and unit costs.
  • Restricted-Knapsack is NP-hard, providing the source problem for the reduction.
  • The constructed committee has two voters, size k = 2s, and utilities derived from item values and weights.
  • If Restricted-Knapsack is satisfiable, the seeded committee violates FJR because a cohesive coalition can obtain utility at least vs + 1.
  • If it is unsatisfiable, the seeded committee is the unique committee satisfying FJR among committees of size at most k.
  • For bounded voter types, the earlier tractability results extend because representation definitions depend on voter types and coalition size, not multiplicities within types.
  • With fixed budget B, FJR can be found in O(m2Bn2) time by enumerating bounded-cost outcomes and testing them.

B Partial Triple Cover is NP-hard

PartialTripleCover is NP-hard via a reduction from 3-regularSubgraph. The construction preserves the existence of a suitable regular subgraph through equal-sized vertex and edge selections satisfying the triple-cover constraints.

  • PartialTripleCover asks whether equal-sized nonempty sets S and T exist such that every vertex in S has at least three neighbors in T.
  • The reduction starts from 3-regularSubgraph, which asks whether a bipartite graph contains a nonempty subgraph where every vertex has degree exactly three.
  • For each original vertex r, the construction creates b_r, and for each original vertex ℓ, it creates c_ℓ and d_ℓ; each edge becomes a′_{ℓ,r} adjacent to these three vertices.
  • A 3-regular subgraph yields a partial triple cover by selecting its incident vertices and edge representatives, with |S|=|T| because |E_H|=3|L_H|=3|R_H|.
  • Conversely, any partial triple cover induces a 3-regular subgraph of the original graph, establishing NP-hardness.

C Proof of Theorem 5

Theorem 5 shows that, unless P=NP, no polynomial-time voting rule can always satisfy FJR for participatory-budgeting instances with cost utilities bounded by 5. The proof encodes PartialTripleCover so that a selfish outcome is uniquely FJR-valid exactly when no partial triple cover exists.

  • Unless P=NP, no polynomial-time voting rule satisfies FJR for all cost-utility instances with utilities bounded by 5.
  • The reduction creates five voters per left-side vertex, alternatives of cost 2 for right-side vertices, and selfish alternatives with total budget B=5|L|.
  • The selfish outcome W₀ gives every voter utility 5 and is used to distinguish whether the input graph has a partial triple cover.
  • If a partial triple cover exists, it produces a coalition whose utility from selected alternatives exceeds the utility provided by W₀, so W₀ violates FJR.
  • If no partial triple cover exists, every alternative outcome of cost at most B violates FJR, making W₀ the unique FJR-satisfying outcome.

D Proof of Proposition 3

Proposition 3 reduces Bb-Pmc to finding an EJR-satisfying committee with utilities bounded by 2n. The constructed selfish committee differs from the unique EJR outcome exactly when the graph contains a size-q balanced biclique.

  • If a polynomial-time rule always satisfies EJR with utilities in {0,1,…,2n}, then Bb-Pmc is solvable in polynomial time.
  • The reduction creates one voter and one selfish alternative per left-side vertex, graph alternatives valued at 2, and selfish alternatives valued at 2q−1.
  • The selfish committee W₀ contains all selfish alternatives and has size k=n, with every voter receiving utility 2q−1.
  • A size-q balanced biclique creates voters and alternatives satisfying the EJR proportionality condition, so W₀ does not satisfy EJR.
  • If no partial q-cover exists, every committee other than W₀ violates EJR, making W₀ the unique EJR-satisfying committee.
Loading 2609.02030v1…