CS Paper Radar

Strengthening Proportionality in Participatory Budgeting with Additive Utilities

Tzeh Yuan Neoh, Nicholas Teh

cs.GT ·submitted 2026-09-08 15:26 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Strengthening Full Justified Representation: Efficient Verification and Computation

cs.GT cs.AIecon.TH ·2026-08-11 ·Nicholas Teh
highly cited similarity 0.85
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

The Complexity of Justified Representation with Additive Utilities

cs.GT ·2026-09-02 ·Carmel Baharav, Jakob de Raaij, Agnès Totschnig
similarity 0.81
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

Robust Proportionality Axioms for Additive Utilities

cs.GT ·2026-10-11 ·Piotr Skowron
similarity 0.80
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

Core Up-To-One for Participatory Budgeting with Additive Utilities

cs.GT ·2026-09-14 ·Piotr Skowron
similarity 0.72
Abstract

We study participatory budgeting with additive utilities. We introduce a selection rule based on utility-weighted harmonic entropy and a cost penalty, and prove that it returns budget-feasible outcomes satisfying core-up-to-one.

0.27

Sequential Contract Design for Budgeted Crowdsourcing

cs.GT ·2026-11-19 ·Michal Feldman, Vasilis Gkatzelis, Shaul Rosner, Inbal Talgam-Cohen
benchmark similarity 0.68
Abstract · 37 pages

A principal wishes to crowdsource a collection of tasks under a fixed compensation budget. The quality of a task's outcome is stochastic and depends on the worker's effort level. Since this effort is unobservable, the principal offers contracts to workers specifying their compensation for each possible outcome. The principal offers these contracts sequentially, using previously observed outcomes and payments to decide whom to approach next and what contract to offer. The objective is to maximize the expected value of the work produced while ensuring that total payments never exceed the budget, regardless of the realized outcomes. Contract design must therefore account both for a worker's incentives and for the budget available to incentivize others. For valuations that are additive across tasks, we characterize how the approximability of the optimal adaptive policy depends on the numbers of workers, effort levels, and outcomes. Polynomial-time constant-factor approximation is possible whenever the number of workers, effort levels per worker, or outcomes per task is constant, but impossible in general when all three are unrestricted, unless $P=NP$. We obtain tight guarantees for every fixed number of workers, establish computational hardness even in restricted settings, and obtain exact algorithms and approximation schemes in more structured settings. We also investigate simple contract structures, demonstrating both the benefits of adapting contracts to previous outcomes and the limitations of local contract rules, while identifying conditions under which a local policy achieves a constant-factor guarantee. Finally, we extend our analysis beyond additive valuations, obtaining constant-factor approximations for monotone submodular valuations with binary outcomes, including guarantees against a stronger full-knowledge benchmark under additional assumptions.

0.27

Full Justified Representation in Temporal Voting: Efficient Computation and Verification

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

Nash Core in Multiwinner Election

cs.GT ·2026-08-31 ·Ashish Goel, Zhihao Jiang, Chenghan Zhou
theory similarity 0.64
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.37

Proportional Representation in Temporal Voting with Ranked Preferences

cs.GT cs.AI ·2026-09-24 ·Noam Hazon, Leora Schmerler, Nicholas Teh
similarity 0.63
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