Skip to content
Preprint

Strengthening Full Justified Representation: Efficient Verification and Computation

Aug 2026 · 6 citations · ⚡ 1 influential · 32 references
Computer Science Economics

TL;DR

This work introduces FJR+, a strict strengthening of FJR and EJR+ that can be verified and satisfied in polynomial time and extends FJR+ to approval-based participatory budgeting with arbitrary project costs.

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\'en 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.

View source

Similar papers

Preprint Sep 2026

Full Justified Representation in Temporal Voting: Efficient Computation and Verification

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

Nicholas J. Teh · 4 citations
Preprint Sep 2026

The Complexity of Justified Representation with Additive Utilities

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

Carmel Baharav, Jakob de Raaij, Agnes Totschnig · 2 citations · ⚡1
Sep 2026

Faster Verification of PJR+ via Mincuts

It is demonstrated how to compute the largest value of $\alpha$ for which a committee still fails the axiom using this mincut formulation, and a direct mincut formulation of the problem on a bipartite graph is given.

Drew Springham · 0 citations
Preprint Aug 2026

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

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

Paul Gölz, Hannane Yaghoubizade · 2 citations
Preprint Sep 2026

Strengthening Proportionality in Participatory Budgeting with Additive Utilities

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

Tzeh Yuan Neoh, Nicholas J. Teh · 2 citations
Preprint Sep 2026

Finding Representative and Approximately Efficient Committees

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

Dominik Peters, Rohit Vaish, Jatin Yadav · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.