Source-linked AI summary
Participatory Budgeting: Models and Approaches
Haris Aziz, Nisarg Shah
TL;DR
Participatory budgeting research needs models that connect residents’ preferences with feasible public-budget allocations and democratic aggregation. This paper surveys computational social-choice work, supplies a unifying mathematical taxonomy, and reviews preference elicitation, welfare, fairness, and incentives. It concludes that the field remains early-stage, with limited preference and decision-process models and several directions for extending theory toward practice.
Problem
Participatory budgeting requires representing complex resident preferences and aggregating them fairly under budget constraints, but existing computational-social-choice research has explored only limited models of preferences and decision-making.
Method
The paper surveys participatory-budgeting research, presents a mathematical model and taxonomy of existing approaches, and reviews preference elicitation, welfare, fairness, and voter incentives.
Results
The survey organizes participatory-budgeting research across modeling choices and synthesizes computational and axiomatic approaches, including findings on welfare, fairness, and incentive compatibility.
Takeaways & Limitations
Future PB research should extend theoretical models and approaches and connect insights from computer science, social science, microeconomics, and public policy to real-world implementations.
Takeaways & Limitations
The field is still in its infancy, with limited models of residents’ preferences and decision-making processes.
Abstract
from arXiv · showhide
Participatory budgeting is a democratic approach to deciding the funding of public projects, which has been adopted in many cities across the world. We present a survey of research on participatory budgeting emerging from the computational social choice literature, which draws ideas from computer science and microeconomic theory. We present a mathematical model for participatory budgeting, which charts existing models across different axes including whether the projects are treated as "divisible" or "indivisible" and whether there are funding limits on individual projects. We then survey various approaches and methods from the literature, giving special emphasis on issues of preference elicitation, welfare objectives, fairness axioms, and voter incentives. Finally, we discuss several directions in which research on participatory budgeting can be extended in the future.
1. Introduction
Participatory budgeting lets residents deliberate and vote on public-project funding, but its voting stage raises modeling, elicitation, aggregation, and fairness questions. This chapter surveys computational social-choice research and organizes PB models through a unifying framework.
- PB process: Participatory budgeting empowers residents to deliberate over priorities and vote on how part of the public budget is allocated across projects.Projects receiving broad community support are then funded.
- PB process: PB has spread internationally, with implementation in over 1,500 municipalities and substantial public-budget allocations in North America and Europe.The nonprofit Participatory Budgeting Project reports more than US$300 million allocated in 29 cities across the US and Canada.
- PB process: A typical PB cycle moves from regional organization and proposal development through deliberation to a final vote whose results determine the budget allocation.Residents discuss ideas, experts vet feasible proposals and costs, and residents finalize proposals before voting.
- Voting-stage research: The voting-stage literature studies decision spaces, preference modeling, ballot design, and vote aggregation, including how to represent complex preferences feasibly.It also asks how aggregation can fairly incorporate different communities’ preferences while efficiently allocating the budget.
- Chapter scope: The chapter provides a unifying framework and taxonomy for PB models, surveys preference representation and elicitation and aggregation desiderata, and distinguishes integral from continuous models.It also highlights differences between motivations and results under discrete and continuous models and discusses future research directions.
- Scope and caveat: Deliberation can enable in-depth discussion but may let an unrepresentative subset dominate final budget decisions, undermining the democratic objective.This chapter therefore limits attention to the final voting stage after proposals, ballot projects, costs, and the total budget are fixed.
2. Mathematical Formulation
The mathematical formulation represents PB through residents, resources, projects, completion degrees, costs, feasible allocations, and preferences. These parameters provide a common lens for comparing implementations and models.
- Core entities: The formulation begins with residents N={1,...,n}, resources and an available budget, and projects P={p_1,...,p_m}.Applications may divide residents by geographical regions and projects by domains.
- Project completion: Each project has a set of possible completion degrees X_p, while an outcome x specifies the completion degree of every project.Models differ in whether degrees are continuous, discrete, or binary and whether project-specific caps apply.
- Costs and feasibility: Project costs are modeled by a non-decreasing function c_p:X_p→R^d, with c_p(0)=0, and feasible allocations satisfy the available resource constraints.The resulting outcome space A contains the budget allocations that can be implemented simultaneously.
- Preferences: Residents’ preferences over allocations can be represented by ordinal preference relations or cardinal utility functions.The framework uses these representations to support mathematical analysis of PB decision rules.
- Model taxonomy: Figure 1 summarizes the taxonomy of popular PB models, which primarily differ in how they model projects’ possible completion degrees.The taxonomy provides a visual overview of the model choices developed in the formulation.
2.1. Decision Space and Popular PB Models
PB decision spaces range from binary project selection to discrete or fractional completion, with bounded and unbounded variants. These choices determine which allocations are feasible and how funding tradeoffs are represented.
- Model dimensions: Popular PB models are classified by the possible completion degrees assigned to each project, including whether degrees are discrete or divisible and whether caps exist.The cost function and total budget can still impose an effective upper bound even in an unbounded model.
- Combinatorial PB: Combinatorial PB requires every project to be either fully implemented or not implemented, so feasible allocations are budget-constrained subsets of projects.With unit caps, the model is a multi-agent variant of a multidimensional knapsack problem.
- Discrete PB: Discrete PB permits multiple discrete completion levels, which can represent funding several units of the same project.A project involving 10 public-toilet units can be represented with 10 possible completion degrees.
- Divisible PB: Divisible PB permits fractional project completion, and capped versions commonly normalize each project’s cap to 1.The assumption can simplify computation when projects have sufficient granularity, even though arbitrary fractional execution may be impractical.
- Unbounded divisible PB: Unbounded divisible PB has no completion caps; with one resource and mild assumptions, it is equivalent to deciding how the budget is divided among projects.This setting is known as portioning.
- Illustrative tradeoffs: A four-project, $7 million example illustrates how discrete and fractional models permit different combinations of projects and degrees of completion.The example contrasts implementing projects A and B with combining one of them with C and D, motivating preference and welfare modeling.
2.2. Preference Modeling and Ballot Design
Preference modeling represents residents’ views over allocations using cardinal or ordinal preferences, while ballot design seeks simpler elicitation formats because full preference communication can be burdensome. The literature uses structural assumptions, spatial models, and extensions from project-level preferences to allocations.
- Preference representation: PB research distinguishes cardinal utility functions over feasible allocations from ordinal preference relations over projects or allocations.Cardinal models assign numerical utility, whereas ordinal models represent rankings, including indifference classes.
- Preference representation: Structural preference models impose assumptions such as subadditivity, submodularity, superadditivity, or supermodularity on project utilities.These assumptions represent projects as substitutes or complements.
- Modeling assumptions: Much existing research implicitly assumes monotonic utilities, although this is questionable because implementing projects consumes costly resources.The assumption requires more or greater implementation never to reduce utility.
- Preference representation: Spatial models embed allocations in a metric space and make utility depend on distance from each resident’s preferred allocation.Garg et al. study ℓp-norm utilities under this approach.
- Preference representation: Ordinal extensions include stochastic dominance, which may be incomplete, and lexicographic comparison, which gives substantially greater importance to more-preferred projects.Scoring rules provide another route from project rankings to cardinal utilities.
- Ballot design: Full preference elicitation is infeasible when allocations are exponentially numerous, motivating simpler formats such as k-approval, approval, range, and knapsack voting.Ranking even 20 projects can be tiresome and may contribute to fewer votes or poorer choices.
2.3. Vote Aggregation
Vote aggregation converts residents’ preference information into a collective allocation using welfare objectives or normative axioms. The surveyed framework includes utilitarian, egalitarian, and Nash welfare, alongside exhaustiveness, discount monotonicity, and fairness through the core.
- Overview: Vote aggregation selects a single allocation or a distribution over allocations from residents’ reported preferences.The review treats aggregation as a central challenge after preference representation and ballot format are fixed.
- Welfare maximization: Welfare maximization combines individual utilities into a social welfare function and chooses an allocation maximizing it.The main welfare functions are utilitarian, egalitarian, and Nash welfare.
- The axiomatic approach: Exhaustiveness requires that no feasible allocation can increase any project’s implementation while leaving the others unchanged.It rules out leaving budget that could fund additional or greater implementation.
- The axiomatic approach: Discount monotonicity requires a project’s implementation not to decrease when its cost becomes more affordable.The axiom compares the original allocation with the allocation produced after only that project’s costs are reduced.
- Fairness: The core protects groups that could otherwise use their proportional budget share to obtain an allocation they all weakly prefer and at least one strictly prefers.A group of size |S| is evaluated against a budget share of |S|/n.
3. Discrete Participatory Budgeting
Discrete participatory budgeting treats project implementation as discrete and connects naturally to multi-winner voting and related resource-allocation models. Research addresses welfare, elicitation, proportional representation, fairness, and strategic limitations, with several computational and approximation barriers.
- Models: Discrete PB allows only discrete project-completion levels, while bounded combinatorial PB restricts each project to fully implemented or not implemented.Multi-winner voting is a special case with unit project costs and caps and a budget limit of k.
- Welfare maximization: In multi-winner voting, utilitarian welfare is maximized by selecting the k approved candidates with the highest total approval counts.A greedy algorithm can perform this selection efficiently.
- Welfare maximization: Utilitarian welfare maximization under a budget constraint is NP-hard, although pseudo-polynomial dynamic programming and an FPTAS exist.The hardness arises in the knapsack formulation of cardinal-utility welfare maximization.
- Elicitation: Knapsack voting reduces elicitation to reporting a favorite allocation and aggregates votes greedily, with welfare and incentive guarantees under restrictive preference models.The method selects feasible project improvements supported by the most voters’ favorite allocations.
- Elicitation: Worst-case utilitarian-welfare approximation is exponential for knapsack voting, polynomial for value or value-for-money rankings, and logarithmic for threshold approval voting.These results compare four ballot formats under an implicit utilitarian framework.
- Incentives and axioms: Strategyproofness is incompatible with weak proportional representation, and finding Pareto-optimal allocations is typically NP-hard in combinatorial PB.These negative results transfer from multi-winner voting because combinatorial PB is more general.
- Fairness: In discrete PB with additive utilities, core allocations may not exist, but logarithmic approximations to the core are guaranteed and efficiently computable.Core existence remains open for binary additive utilities, while proportional-representation research provides another fairness perspective.
4. Divisible Participatory Budgeting
Divisible PB models allow project funding on a continuum and support research on welfare, fairness, and incentives across several settings. The literature includes portioning, spatial models, and mechanisms with distinct computational and strategic properties.
- Model and applications: Divisible PB permits projects to be implemented to fractional degrees, often improving existential and computational results compared with discrete models.The model is especially relevant when project funding can vary continuously or projects have sufficient granularity.
- Model and applications: Portioning normalizes feasible allocations so each project receives a fraction of the total budget, connecting PB to fair mixing and probabilistic voting.In the normalized formulation, project fractions sum to at most one.
- Welfare: A greedy algorithm maximizes utilitarian welfare in divisible PB with unit caps by ordering projects by value-for-money and partially funding the next project when necessary.The ordering uses aggregate project value divided by project cost.
- Fairness and incentives: Maximizing Nash welfare in portioning with dichotomous preferences satisfies strong fairness properties, including core membership and average fair share.Related work also studies scoring-rule utility proxies and Nash welfare under ordinal preferences.
- Fairness and incentives: For portioning with dichotomous preferences, CUT is strategyproof and both CUT and Nash-welfare maximization provide strict participation incentives.Nash-welfare maximization is not strategyproof.
- Welfare and fairness: The independent markets mechanism is strategyproof and satisfies a basic proportional-representation notion under spatial preferences and ℓ1 disutility.Residents’ disutility is defined by distance from their ideal allocation.
5. Extensions and Future Directions
The chapter frames participatory-budgeting research as a survey and mathematical classification while identifying extensions needed to bring models closer to real-world practice. Future work concerns richer constraints, preferences, entitlements, incentives, information, and the full PB pipeline.
- Scope and motivation: The chapter surveys participatory-budgeting research, classifies existing models across mathematical axes, and reviews computational and axiomatic approaches.Its stated goal is to organize the literature and identify directions for extending it.
- Scope and motivation: Research in computational social choice remains in its infancy, with only limited models of resident preferences and decision-making processes explored.The chapter calls for work spanning computer science, social science, microeconomics, and public policy.
- Model extensions: Future PB models could incorporate multidimensional constraints capturing costs beyond money, such as environmental costs.Most existing work uses a single knapsack-style constraint based on available money.
- Model extensions: Future work could represent unequal entitlements, distributional constraints, hybrid discrete-continuous projects, initial endowments, and complex interactions among projects.These extensions address different claims over budgets, project funding bounds, mixed implementation levels, existing funds, and non-independent preferences.
- Incentives and information: The literature’s strategyproofness focus assumes rational agents, motivating behavioral models of realistic manipulations and algorithms to prevent them.The chapter identifies behavioral game theory as a direction for studying voter behavior more realistically.
- Incentives and information: Informing residents about project costs, benefits, and complexities can affect their preferences, making information communication an important research issue.The chapter treats the effects of communication as requiring detailed study.
- End-to-end PB: Because agenda setting and earlier proposal stages affect final outcomes, an end-to-end model of the entire PB process remains a major challenge.The chapter focuses only on the final voting stage, although earlier stages directly shape it.