CS Paper Radar

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

Piotr Skowron

cs.GT ·submitted 2026-09-14 17:36 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Strengthening Proportionality in Participatory Budgeting with Additive Utilities

cs.GT ·2026-09-08 ·Tzeh Yuan Neoh, Nicholas Teh
similarity 0.72
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.40

Robust Proportionality Axioms for Additive Utilities

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

The Complexity of Justified Representation with Additive Utilities

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

Strengthening Full Justified Representation: Efficient Verification and Computation

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

Optimally Curating an Event

cs.GT ·2026-10-16 ·MohammadTaghi Hajiaghayi, Sebastien Lahaie, Mohammad Mahdavi, Suho Shin
top venue similarity 0.55
Abstract · Appeared at IJCAI 2026

We study the optimal design of a self-financing event, a problem that requires balancing the recruitment of costly, positive-value participants with revenue-generating agents who may impose negative values on the event. We introduce a novel two-sided mechanism design framework with plus agents equipped with private costs and positive impact, and minus agents with private values and negative impact upon inclusion in the event, to maximize the overall quality of the event under a budget-balanced (BB) constraint so that the designer does not run a deficit. We conduct a comprehensive study on the theory of optimal event curation on various utility functions. For additive utility, we fully characterize the optimal incentive-compatible Bayesian mechanism under both the ex-ante and ex-post BB constraints. For submodular utility, we propose an ex-ante BB mechanism that achieves a constant-factor approximation to the optimal Bayesian mechanism.

0.36

Sharing the Gains of Aggregation: Cooperative Imbalance Cost Allocation

eess.SY ·2026-09-30 ·Asmus Winther Eriksen, Jalal Kazempour
benchmark similarity 0.54
Abstract

A facilitator is an intermediary that offers renewable producers and consumers fixed-price contracts and, acting as their balance responsible party, manages the residual imbalances in the market. Pooling imperfectly correlated residuals nets consumers' imbalances and reduces the portfolio's total imbalance cost, but raises an allocation question: how should these savings be divided among heterogeneous consumers? We formulate this as a cooperative game, the imbalance netting game, and compare six allocation mechanisms under a two-price imbalance settlement in terms of computational requirements, budget balance, group rationality, and additivity. We establish three analytical results: a necessary and sufficient condition for budget balance of the marginal cost contribution mechanism, group rationality of the marginal cost contribution and Vickrey-Clarke-Groves mechanisms, and a necessary and sufficient condition for when the Gately point is well-defined. On Danish 2024 data for 19 consumers, aggregation reduces imbalance cost by 10%, but how these savings are shared depends strongly on the allocation rule. A flat-rate allocation proportional to consumption, used as a benchmark for socialized imbalance pricing, charges some consumers more than twice their standalone cost, whereas all the game-theoretic mechanisms studied produce stable allocations in practice.

0.45

Approximating Optimal Welfare in Complementary Allocation under Decentralized Information

cs.GT cs.DSecon.TH ·2026-09-13 ·Meryem Essaidi
benchmark similarity 0.54
Abstract · 16 pages, 1 table; includes full proofs

Complementary resources are often allocated by agencies that see different coordinates of an individual's needs. If an intervention requires complementary resources, an agency may know if said person lacks its own resource; yet not know if supplying completes a useful bundle. We study allocation of $m$ divisible complementary goods when each agency observes only its own coordinate of a baseline-access profile. To isolate information from incentives, we measure the welfare cost of this split against a generous decentralized benchmark DEC: the best rule that acts on local information alone, with cooperative agencies and known population distribution and capacities. Even so, local observation alone can make optimally coordinated policies arbitrarily inefficient: a factor linear in $m$ (even with equal capacities), and a factor inverse in OPT (with but three agencies). Threshold referrals recover much of this loss: an agency reports if its value lies below a public threshold, and a clearing rule uses only the joint reports. Aggregating types by their reports captures a rectangle under the optimal half-utility survival curve. Our main tool is a profile-level charging certificate: if optimal utility is at least twice a threshold, OPT pays at least that on every deficient coordinate. This yields welfare at least ${\rm OPT}/[4(1+\ln(2/{\rm OPT}))]$ with one bit per agency; and an equal-revenue family shows this log-loss tight for one threshold. A geometric threshold ladder improves this to a constant fraction of OPT with doubly-logarithmic messages: a staircase recovers ${\rm OPT}/8$ with $Θ(\log\log(1/{\rm OPT}))$ bits, and this is necessary within the class. The results isolate how a simple reporting language turns large local-info losses into constant-factor recovery. In short: One threshold gets a log-approximation. A staircase, with log-of-log bits, a constant-factor.

0.38

Sequential Contract Design for Budgeted Crowdsourcing

cs.GT ·2026-11-19 ·Michal Feldman, Vasilis Gkatzelis, Shaul Rosner, Inbal Talgam-Cohen
benchmark similarity 0.53
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