Improving fair project funding in participatory budgeting processes
Strengthening Proportionality in Participatory Budgeting with Additive Utilities
Computer Science and Game Theory
Summary
Participatory budgeting lets people vote on which public projects get funded within a budget. The authors study how to make this funding as fair as possible when different people value projects differently. They find a way to guarantee a near-perfect fair outcome in reasonable time, even when calculating a fully fair result is very hard. Their method also allows flexibility in how leftover budget is spent, keeping fairness intact. This work is especially effective when projects cost the same or when voters simply approve projects they like.
participatory budgetingproportional representationfull justified representationadditive utilitiesNP-hardnessgreedy algorithmsapproval votingpriceabilityDroop quota
Authors
Tzeh Yuan Neoh, Nicholas Teh
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.