1 Introduction
Participatory budgeting (PB) is a paradigm which empowers residents to directly decide how a portion of the public budget is spent. Specifically, residents deliberate over spending priorities and vote over how the budget should be allocated to different public projects. Projects which receive broad support from the community are then funded through the process.
This process was initiated as a radical democratic project in the city of Porto Alegre, Brazil, led by the leftist Workers’ Party (Cabannes, 2004). Over the next few decades, it quickly spread across the world; it has been implemented by over 1,500 municipalities (Röcke, 2014) and in locations as diverse as Guatemala, Peru, Romania and South Africa (Shah, 2007). The nonprofit organization Participatory Budgeting Project^{1}^{1}1http://www.participatorybudgeting.org alone has helped allocate more than US$300 million of public budget in 29 cities across the US and Canada. In Europe, the effort is led by Paris and Madrid, each spending at least $100 million a year on public projects through participatory budgeting (Legendre et al., 2017; Gutiérrez, 2017)
. In particular, Madrid developed an online opensource platform,
Decide Madrid, which has been used by more than 30 local governments (Samir, 2018). PB is still spreading in more regions across the world. For example, Toronto recently completed its threeyear pilot of PB (Murray, 2019), and the state of New South Wales in Australia recently started PB under the name My Community Project.^{2}^{2}2https://www.nsw.gov.au/improvingnsw/projectsandinitiatives/mycommunityproject/Participatory budgeting is typically a long process; in many municipalities, one PB cycle takes one full year. While the exact implementation details differ from one PB instance to another, at a high level the process is composed of the following stages, which allow residents to come up with effective project proposals and provide their preferences over budget allocation (Shah, 2007).

First, the geographical region may be divided into several subregions (e.g. districts), and one PB process may be conducted in each district separately. The goal of this stage is to allow residents to focus on the projects in their own neighborhood and community. The total available budget for each district is also typically decided at this stage.

Next, residents share and discuss ideas through neighborhood meetings and online tools. This allows them to come up with preliminary project proposals.

These initial proposals are then developed into feasible proposals by focus groups and vetted by experts. Often, this is the stage where a proposal may be broken into distinct stages of implementation, and a cost estimate may be derived for each implementation stage. Projects may also be classified into categories such as recreation, infrastructure, health, education, transportation, etc.

This may be followed by several rounds of deliberation through which residents finalize a small number of proposals to be included in the final vote.

The final stage of the PB process is the voting stage. In this stage, eligible residents vote over how the public budget should be spent across the finalized proposals, and these votes are aggregated into a final budget allocation.
Additional effort is often required to make PB a success. For example, advertisement and promotion through various channels, including social media, can be the key to increasing civic engagement. This can be crucial in encouraging various minorities to participate and ensuring that their preferences are incorporated into the decisionmaking. See the edited volumne by Shah (2007) for a detailed survey of the entire PB process.
In this chapter, we limit our attention to the final voting stage of the process. That is, we assume that the project proposals have been detailed and finalized, and projects to be included on the final ballot have been filtered. We also assume that project costs have been estimated and the total available budget is known. Research on the voting stage of the PB process focuses on four important considerations:

Decision space: Is the space of possible outcomes discrete (e.g. because a project can only be “funded” or “not funded”)? Or is it continuous (e.g. because a project can be allocated different amounts of funds to implement it to different degrees of effectiveness)?

Preference modeling: How will residents’ preferences over the projects be represented for the purpose of mathematical analysis?

Ballot design (aka preference elicitation): It is often desirable for the modeling to allow complex preferences. However, it may be infeasible to ask residents to report such complex preferences. What should the ballot ask from residents which will serve as a proxy for their preferences and allow them to effectively convey their preferences?

Vote aggregation: How will the votes cast by residents be aggregated into a final allocation of the available public budget? How should this process fairly incorporate aggregation the preferences of different communities of residents and efficiently allocate the public budget?
The need for systematic modeling and study of these considerations has recently inspired a body of research in the computational social choice literature Brandt et al. (2016); Endriss (2017). This body of research sits at the intersection of computer science, social science, and economics, and aims to use mathematical modeling and algorithmic techniques to design different approaches to the voting stage of the PB process.^{3}^{3}3In several PB programs, the final decision of budgets is entirely done by deliberation by a small subset of residents. Deliberation has its advantages and disadvantages. While it allows an indepth discussion of possible outcomes from different perspectives, it also poses the danger of the process being dominated by an unrepresentative subset of the residents, thus thwarting the democratic objective. The goal of this chapter is to present a comprehensive overview of the research on PB in computational social choice. Some of the original contributions of this chapter include providing a unifying theoretical framework which allows viewing the different research works through a single lens, and providing a taxonomy of the different PB models which highlights their unique modeling choices.
Outline:
The organization of this chapter is as follows. In Section 2, we present a general mathematical formulation of PB, and list several prominent features that distinguish different implementations of PB. Next, we focus on popular PB models that make specific design choices in terms of these features, and present a taxonomy of these models. We pay special attention to the representation and elicitation of preferences, and popular desiderata underlying the vote aggregation methods.
In Section 3, we survey the research on the “integral model” of PB, in which each project can only be fully funded or not funded. In Section 4, we survey the research on the “continuous model” of PB, in which the funding level of each project can lie on a continuum. We highlight the differences between motivations and results under both discrete and continuous models. Finally, in Section 5, we discuss possible extensions and directions for future research.
2 Mathematical Formulation
We begin by reviewing various parameters which play a key role in formulating the participatory budgeting problem. Later, we consider specific choices of these parameters, which give rise to popular PB models.

Residents: There is a set of residents (a.k.a. agents or voters) . In some applications of PB, residents are divided across different geographical regions (e.g. districts or wards), and each region conducts a separate PB election, in which residents of that region vote.

Resources and budgets: There is a set of resources, denoted . The available budget is , where denotes the amount of resource available. In most applications of PB, money is the only limiting resource. Thus, much of the work on PB in computational social choice has focused on the case of a single resource, in which case the available budget is denoted by the scalar .

Projects: There is a set of projects . In some applications, projects are categorized into various domains (e.g. infrastructure, security, education, health & wellness, etc).

Degree of completion: Some projects can be completed to different degrees. For example, completing of a project proposing neighborhood cleanup may mean a part of the neighborhood being cleaned up. Some projects may have discrete milestones, and only the first few milestones may be achieved; e.g., a project proposing the creation of a public park may include construction of the park as the first milestone and construction of a children’s playground within the park as the second milestone. For other projects, the degree of completion may be binary; they must be either fully implemented or not implemented at all (e.g. installing a fountain in a park). For project , let denote the set of its possible degrees of completion and denote its actual degree of completion in an outcome. In some models of PB, which we refer to as bounded models, there is an upper bound (a.k.a. cap) on the degree of completion of each project , denoted by . In unbounded models, there are no such caps.^{4}^{4}4Note that the cost function of a project and the total available budget may still induce an effective upper bound on its degree of completion. We discuss popular choices of in Section 2.1. We assume for all projects . Let . Various models of PB studied in the literature crucially differ in this key choice; we elaborate on this in Section 2.1.

Costs: Each project has an associated cost function
, where the vector
gives the amount of each resource required to complete project to degree . We assume that and is monotonically nondecreasing. 
Budget Allocations: An outcome is characterized by the degree of completion of each project . Note that this also specifies the amounts of different resources that will be devoted to each project. The outcome is feasible if , where addition is componentwise. We refer to feasible outcomes as (budget) allocations. Let denote the space of allocations.

Resident Preferences: Each resident has preferences over which projects should be implemented and to what degree. These can be represented through an ordinal preference relation or a cardinal utility function over the space of allocations . We elaborate on this later in Section 2.2.1.
2.1 Decision Space and Popular PB Models
Figure 1 presents a taxonomy of the popular PB models in the literature, which crucially differ in their modeling of the possible degrees of completion of projects. We review each model in further detail.
Bounded Discrete PB (Combinatorial PB):
This is perhaps the most widely studied and applied model of PB. In this model, projects must be either fully implemented or not implemented at all. Hence, the set of possible degrees of completion is for each project . Note that this model has unit caps (). Consequently, the cost function of project is effectively a vector, which indicates the amounts of different resources needed to fully implement project . Feasible allocations in are subsets of projects which can be implemented simultaneously subject to budget constraints. In essence, this is a multiagent variant of a multidimensional knapsack problem.
Discrete PB:
In this model, each project has discrete possible degrees of completion. However, unlike combinatorial PB, there may be more than two possible degrees of completion. These degrees of completion can also mathematically capture funding of multiple of units of the same project. For example installing 10 units of public toilets can be viewed as having a single project with 10 different degrees of completion. Typically, we assume that for each project . Note that this model has no cap on the degree of completion, but limited availability of resources may still place a natural upper bound on the degree of completion of each project in any feasible allocation. This model is applicable when each project is ambitious, and its full implementation can potentially use up all the available resources.
Divisible PB:
In this model, it is assumed that projects can be implemented to any fractional degree. In the version with caps, we can assume without loss of generality that the cap is , i.e., for each project ; in this case, denotes the fraction of project that is completed. In practice, projects often cannot be executed to arbitrary fractional degrees. However, in cases of sufficient granularity, assuming divisible PB can help for computational reasons; more details are provided in Section 4.
Unbounded Divisible PB (Portioning):
In this model of divisible PB, there are no caps on the degrees of completion. Thus, for each project . When there is a single resource type (e.g. money), under mild assumptions^{5}^{5}5E.g., if the cost function of each project is strictly increasing, then there is a onetoone correspondence between the amount of money allocated to the project and its degree of completion., deciding the degrees of completion of different projects is equivalent to deciding how the available budget will be divided among the projects. This setting is known as portioning in the literature (Airiau et al., 2019).
Example 1.
Example Suppose there is a set of residents , a set of four projects , and a single resource (money) with a total budget of $ million. Suppose the cost functions of the projects are as follows.

$ million

$ million

$ million

$ million
Suppose residents like projects and equally, but derive no value from or . residents derive value only from , and the remaining only from .
In the divisible PB model with unit caps (i.e. for each project ), we have numerous choices. For instance, we could implement fraction of each project. Or we could implement fraction of and each, and fully implement and .
In the combinatorial PB model (i.e. for each project ), given the budget of $ million, we can implement and , which would make residents very happy but residents very unhappy, or we can implement one of and together with both and , which would make residents partially happy and residents very happy.
How do we quantify how happy the residents are? How do we make tradeoffs between such decisions? To understand this better, we need to understand modeling of resident preferences and goals of the PB process, which we review below.
2.2 Preference Modeling and Ballot Design
Two important decisions in the PB process are the modeling of residents’ preferences (which helps in the mathematical analysis of the effectiveness of the process) and the format in which the residents cast their votes.
2.2.1 Preference Modeling
Recall that is the set of feasible allocations. In an expressive model, each resident has a cardinal utility function .^{6}^{6}6We note that in this case, much of the existing research on PB in computational social choice, inspired from classical research on voting, implicitly assumes that and satisfies monotonicity (i.e. for ). In words, implementing more projects or implementing projects to a greater degree cannot bring less happiness. In the PB context, implementing projects requires spending costly resources, which makes this assumption questionable. See Section 5 for further discussion. If only comparisons among allocations are required, one may work instead with an ordinal preference relation over .^{7}^{7}7The ordinal preference relation is typically assumed to be transitive and complete.
While such an expressive modeling allows capturing all possible preferences, it does not utilize the structure that is often present in the preferences. Below, we discuss three common approaches to modeling such structure.
The first approach is to directly impose a structural assumption on the utility function or the preference relation. For example, in combinatorial PB, where allocations are effectively feasible subsets of projects and a utility function can be represented as , one may impose that satisfies subadditivity or submodularity (when projects are substitutes of each other), or superadditivity or supermodularity (when projects are complements of each other).
The second approach is to use spatial models, where allocations are embedded in a metric space, each resident has a preferred allocation, and her utility for another allocation is a (typically nonincreasing) function of its distance to her preferred allocation. For example, Garg et al. (2019) study normed utilities, under which the utility of resident (with preferred allocation ) for allocation is , where is the norm.
The third — and perhaps the most popular — approach is to model residents’ preferences over individual projects and use a natural rule to extend them to preferences over allocations. Below, we review common ways to achieve this for both cardinal utility functions and ordinal preference relations.
Cardinal extensions:
Fain et al. (2016a) study the class of scalar separable utility functions, whereby resident derives utility from each project ,^{8}^{8}8Note that is a residentindependent function. Typically, it is assumed to be nondecreasing, and when is continuous, smooth and concave as well. and her utility for an allocation is simply additive across projects, i.e., . This is a reasonable assumption when the different project proposals are completely independent of each other. In case of combinatorial PB, where for each project , this effectively reduces to for each ; this is commonly known as an additive utility function (Benade et al., 2017; Fain et al., 2018; Bhaskar et al., 2018). A further restriction of for each resident and project gives rise to dichotomous preferences (Aziz et al., 2018; Faliszewski and Talmon, 2019), under which each resident approves or disapproves each project and only cares about the number of her approved projects that are implemented. In combinatorial PB, another common extension is the max set extension (Caragiannis et al., 2017), whereby the utility of a resident for an allocation is her utility for her most favorite project that is funded: for each . This is applicable when the projects are substitutes of each other, and the resident will derive value from only one of the implemented projects.
Ordinal extensions:
When residents are assumed to have ordinal preferences over projects, we use the following notation. Each resident has a weak order preference relation over . We denote by the strict part and by the indifference part of the relation . We denote by the equivalence classes of the relation in decreasing order of preferences; thus, each set is a maximal equivalence class of objects among which agent is indifferent, and is the number of equivalence classes. Given an ordinal preference relation , one can induce resident ’s preference relation over the set of allocations in several natural ways.
The (first order) stochastic dominance (SD) extension is defined as follows (see, e.g., Brandl et al. (2016)). For allocations , we say that iff Since this extension requires adding the degrees of completion of different projects, it makes more sense in models where the degrees of completion of different projects are comparable (e.g. in combinatorial PB or divisible PB with unit caps). The desirable aspect of the SD extension is that is equivalent to saying that yields at least as much utility to resident as does, for all additive utilities over projects that are consistent with preference relation . However, the SD relation is not complete (i.e. it does not compare every pair of allocations).
One popular complete extension is the lexicographic extension , under which resident is assumed to care significantly more about project than about project whenever . Formally, iff for the smallest (if any) with , we have . Once again, since this requires adding the degrees of completion of different projects, it makes more sense when the degrees of completion of different projects are comparable. However, if each resident submits a strict ordering over the projects, the equivalence classes become singletons and the definition makes sense for other models of PB too. For combinatorial PB, under the lexicographic extension, resident compares two allocations by comparing her most favorite project that implemented in each allocation, breaking ties by her next most favorite project, and so on. This is similar to the max set extension mentioned above for cardinal utility functions, and is a reasonable assumption when projects are substitutes of each other.^{9}^{9}9For instance, the projects may propose to build public parks in different locations, but a resident may only be interested in using a single park that is built closest to her home. Klamler et al. (2012) study a broader class of preference extensions that includes the lexicographic extension.
Another complete extension is derived by converting ordinal preferences to cardinal preferences using scoring rules. A scoring vector is denoted by , where . Given a ranking over projects, it is assumed that resident has utility for project , where is the rank of project under . Then, any of the cardinal extensions mentioned above can be used to induce the resident’s preferences over allocations.
2.2.2 Ballot Design
Even in the simplest case of combinatorial PB, there can be exponentially many allocations. This makes it infeasible to ask residents to communicate their full preferences, thus motivating the use of more restrictive preference elicitation techniques.
For example, even when residents’ preferences over allocations are induced from their ranked preferences over individual projects, asking residents to rank as many as projects^{10}^{10}10The 2018 PB in Cambridge, USA involved 20 projects: https://pb.cambridgema.gov/pbcycle5 can be tiresome, and the cognitive burden can lead to fewer residents voting or residents making poor choices (Iyengar and Lepper, 2000). Hence, most realworld applications of PB use easier ballot formats such as approval voting (where residents approve the projects they like the most), approval voting (where residents approve all projects that they like), range voting (where residents rate projects), or knapsack voting (where residents provide the ideal allocation according to their preferences) (Goel et al., 2019).
2.3 Vote Aggregation
Once the representation of residents’ preferences and the format in which they cast their votes are decided, the next challenge is to decide how to aggregate their votes into a collective outcome, which can be a single allocation or a distribution over allocations (if randomization is permitted).
This is perhaps the most wellstudied aspect of the entire PB process. We review several prominent approaches to vote aggregation in computational social choice.
2.3.1 Welfare Maximization
This approach is applicable when individual preferences are represented as cardinal utility functions. It uses a social welfare function, which combines individual utility functions of residents into a societal utility function, and finds an allocation maximizing this societal utility function. There are three popular social welfare functions:

The utilitarian welfare of an allocation is the sum of utilities it gives to residents: for .

The egalitarian welfare of an allocation is the minimum utility it gives to any resident: for . Maximizing this welfare function is seen as an extreme form of one interpretation of fairness.

The Nash welfare of an allocation is the product of utilities it gives to residents: for . Maximizing this welfare function is seen as a compromise between utilitarianism and egalitrianism.
2.3.2 The Axiomatic Approach
This approach entails specifying intuitive normative axioms that the vote aggregation rule must satisfy and searching for rules that satisfy as many of the axioms as possible. Many compelling axioms have been proposed for PB (see, e.g., Aziz et al. (2018); Faliszewski and Talmon (2019)); the two examples given below are selected because they apply to all the models of PB we described above.
Definition 1 (Exhaustiveness (Aziz et al., 2018)).
A feasible outcome (i.e. allocation) is called exhaustive if an outcome is not feasible whenever for all projects and a strict inequality holds for at least one project. In words, it should not be possible to implement any more projects or any projects to a greater degree with the leftover budget. A vote aggregation rule is exhaustive if it always outputs an exhaustive allocation. A similar axiom is termed budget monotonicity by Faliszewski and Talmon (2019).
Definition 2 (Discount Monotonicity (Faliszewski and Talmon, 2019)).
Suppose a vote aggregation rule outputs allocation . Suppose project receives a revised cost function such that for all , and, all else being equal, the vote aggregation rule now outputs allocation . Then, . In words, if a project becomes more affordable, it should not be implemented to a lesser degree.
Faliszewski and Talmon (2019) study a number of additional axioms that are specifically applicable to settings where residents have dichotomous preferences.
2.3.3 Fairness
Finally, an important consideration in democratic decision making is to fairly take into account the preferences of all residents when making the collective decision. We review one fairness axiom that is applicable in our general PB framework. For other axioms that are applicable in more specific environments (e.g. with dichotomous preferences), we refer interested readers to the work of Aziz et al. (2018).
Definition 3 (Core (Fain et al., 2016a, 2018)).
An allocation is said to be in the core if no subset of residents can find an outcome that is feasible given a budget of such that for every resident and a strict inequality holds for at least one .
The notion of the core is based on the idea that a group of residents collectively deserve at least fraction of the budget spent on their needs. This is formalized by requiring that they not be able to allocate this fraction of the budget in a way that they prefer more.
3 Discrete Participatory Budgeting
We are now ready to review how these approaches have been applied to different models of PB. Recall that in the discrete model, the decision space is discrete. This model is applicable when projects can only be executed up to discrete levels. For example, a project that proposes to build public toilets in the community can have degree of completion , where may denote the number of public toilets that are actually built; the assumption here is that each individual toilet is either built fully or not built at all. This discrete aspect affects the modeling of residents’ preferences as well as the design of ballots and vote aggregation procedures.
This model is a natural generalization of multiwinner voting (alternatively known as committee selection), which has been widely studied in social choice theory (Aziz et al., 2017; Faliszewski et al., 2017). In multiwinner voting, there are candidates, and of them are to be selected based on voters’ preferences. This is a special case of discrete PB (more specifically, of combinatorial PB) where each candidate is a project with unit cap () and unit cost (), and the budget limit is . We first review prior literature on multiwinner voting and other similar models of decisionmaking, and then provide an overview of various approaches to discrete PB.
3.1 Review of the Literature on Settings Related to Discrete PB
The simplest special case of combinatorial PB is multiwinner voting. As explained above, this is where each project has unit cost. A natural goal in this setting is to maximize the utilitarian welfare. In this case, each voter approves a subset of candidates, and the goal is to select candidates with the highest number of total approvals. This can be accomplished efficiently by a greedy algorithm which selects candidates onebyone in the decreasing order of the number of approvals they receive. However, when we replace the selection of candidates by a knapsack constraint to extend this to combinatorial PB with dichotomous preferences, the problem becomes NPhard even for a single agent (Karp, 1972). The greedy algorithm is still welldefined in this setting; it selects projects onebyone in the decreasing order of the number of approvals they receive, skipping any project if its inclusion exceeds the budget limit. This aggregation rule is often used in practice.^{11}^{11}11See, for example, the PB process in Toronto (Murray, 2019) and in Cambridge (Mundt, 2017). The literature also focuses on several other objectives in multiwinner voting; an excellent overview is given by Faliszewski et al. (2017).
Klamler et al. (2012) also focus on committee selection under knapsack constraints. However, in their model, there is a single agent with a ranking over individual candidates (projects). They explore different ways to extend this to a ranking over sets of candidates, and then select a committee of candidates subject to a knapsack constraint. A similar model has been considered by Delort et al. (2011).
Another model related to PB is combinatorial public projects (CPP) (Papadimitriou et al., 2008). In this model, a set of public projects are to be selected subject to a resource constraint, similarly to PB. However, research on CPP focuses on designing truthful mechanisms by charging payments to agents (Dughmi et al., 2016), which is unrealistic in the PB setting.
Conitzer et al. (2017) propose the public decision making model, in which there are a finite number of issues, and for each issue, there is a set of alternatives which can be implemented. A feasible outcome consists of choosing a single alternative corresponding to each issue. One can view this as a special case of discrete PB, where each issue corresponds to a unique type of resource of which one unit is available and implementing any alternative of an issue requires the full one unit of the corresponding resource. One of the fairness definitions they propose is proportionality up to one issue, which is a relaxation of the core defined in Section 2.3.3.
Lu and Boutilier (2011) introduce budgeted social choice. In this framework, each alternative has a cost and the goal is to select a set of alternatives subject to budget constraint. This framework generalizes the PB model we discuss as it allows the cost of an alternative to be dependent on the number of voters who derive utility from that alternative. However, they work with a limited modeling of preferences wherein there is a common positional scoring rule which maps an alternative’s rank in a voter’s preference ranking to the voter’s utility for the alternative. This is also a common approach in the resource allocation literature (Bouveret and Lang, 2011).
3.2 Approaches to Discrete PB
We now provide an overview of various approaches to PB in the discrete model.
Welfare maximization:
This is a natural approach when residents have cardinal utilities. Maximizing the utilitarian welfare subject to the budget constraint is the classic knapsack problem. While the problem is NPhard (Karp, 1972), there exists a pseudopolynomial time dynamic programming algorithm and a fully polynomial time approximation scheme (FPTAS) (Vazirani, 2013).
Fluschnik et al. (2017) consider the combinatorial PB model and study the computational complexity of maximizing (1) the utilitarian social welfare with respect to additive utilities, (2) the utilitarian social welfare with respect to the max extension, and (3) the Nash social welfare with respect to additive utilities. All of these problems are NPhard except under severe restrictions on residents’ utility functions.
Elicitation:
Eliciting cardinal utilities in the PB context can be challenging and may impose high cognitive burden on the voters, potentially even deterring them from voting in the first place (Garg et al., 2019). This has inspired a line of research that aims to propose simpler ballot formats. Goel et al. (2019) introduce knapsack voting, under which residents simply report their favorite allocation. They suggest aggregating knapsack votes using a greedy approach. In combinatorial PB, the number of “approvals” that a project receives is the number of residents who include the project in their favorite allocation, and projects are selected in the decreasing order of their number of approvals subject to the budget constraint. In discrete PB, the algorithm starts by setting the degree of completion of each project to zero. Then, at each step, it considers increasing the degree of completion of each project to its next possible value, and among the feasible improvements, selects the one which is part of the favorite allocation of most voters. They show that this approach has compelling welfare and incentive guarantees under restrictive models of resident preferences.
Benade et al. (2017) compare knapsack voting to three other ballot formats: ranking projects by value, ranking projects by valueformoney, and a new format that they call threshold approval voting. They use the implicit utilitarian voting framework (Procaccia and Rosenschein, 2006; Boutilier et al., 2015), in which residents are assumed to have underlying cardinal utilities and the information they provide on the ballot is treated as a proxy for their underlying utilities. They show that in the worst case, knapsack voting leads to an exponentially bad approximation of utilitarian welfare, ranking projects by value or valueformoney leads to a polynomially bad approximation, and threshold approval voting leads to a logarithmic approximation.
Incentives:
Another line of research studies residents’ incentive to misreport their preferences in order to induce an outcome that is better than what would be implemented had they reported their honest preferences. While all reasonable deterministic aggregation rules are susceptible to such manipulations due to the classic impossibility result by Gibbard (1973) and Satterthwaite (1975), Bhaskar et al. (2018) show that when residents rank projects by value, there exist randomized aggregation rules that are strategyproof (i.e. provide no incentive to residents to misreport) and achieve nearly optimal approximation of utilitarian welfare among all (even nonstrategyproof) aggregation rules, implying that, at least when randomization is allowed, strategyproofness does not impose a significant burden in this setting.
Axiomatic desiderata:
Aziz et al. (2018) begin the formal study of defining axioms for PB that encode principles of proportional representation. They design algorithms for combinatorial PB with dichotomous preferences which satisfy such axioms. Their central result is an algorithm called the generalized Phragmen’s sequential rule, which computes an allocation satisfying a reasonable proportional representation property. An alternative simple method, which is motivated by proportional representation concerns, is discussed by Aziz (2019). Faliszewski and Talmon (2018), in the same model, focus on monotonicitystyle axioms of a range of aggregation rules. The common approach in this line of work is to focus on axioms and algorithms for multiwinner voting (Aziz et al., 2017; Faliszewski et al., 2017) and extend them to combinatorial PB.
Since combinatorial PB is more general than multiwinner voting, the negative existential and computational results from multiwinner voting carry over directly. For example, strategyproofness and any weak notion of proportional representation are inherently incompatible (Peters, 2018), and finding Pareto optimal allocations is typically NPhard (Aziz et al., 2016).
Shapiro and Talmon (2017) generalize Condorcet’s principle (also referred to as popularity in allocation settings) to PB and devise an algorithm to compute allocations satisfying this principle. Since Condorcet’s principle is based on majoritarian comparisons, the approach is not wellsuited for proportional representation of minorities, which is a prime concern in realworld applications of PB (World Bank, 2008; Ganuza and Francés, 2012).
Fairness:
Fain et al. (2018) investigate fairness in a setting that generalizes discrete PB. In particular, they show that allocations in the core may not exist in discrete PB with additive utilities, but allocations that provide a logarithmic approximation of the core are guaranteed to exist and can be computed efficiently. For the special case of discrete PB with binary additive utilities (where each resident has utility or for each project, and utilities are additive across projects), it is an open question whether allocations in the core always exist. Other work on proportional representation for the combinatorial PB model (see e.g. Aziz et al. (2018)) can also be viewed as focussing on fairness.
Other approaches:
4 Divisible Participatory Budgeting
The divisible model of PB applies to scenarios in which funding for a project can lie on a continuum. For instance, recall the example from Section 3, which involved a project proposing to build five public toilets in the neighborhood. We argued that this falls under the discrete model of PB, as one can only provide funding to build an integral number of toilets. In contrast, a project on maintaining the cleanliness of the toilets may be funded partially without any integral restrictions, and thus may fall under the divisible model of PB.
While a divisible model can often be approximated by a discrete model, the divisible model is interesting in its own right as it often leads to better existential and computational results (see, e.g., the work of Fain et al. (2018)).
4.1 Review of the Literature on Settings Related to Divisible PB
A strand of the literature focuses on a multidimensional continuous space, where the dimensions correspond to categories of projects such as defense, health and education (Garg et al., 2019; Freeman et al., 2019). The model is especially relevant when deciding the composition of funding across different categories is more important than deciding particular projects within a category. This literature typically works with the spatial model of resident preferences, in which each resident has an ideal point in the space. The is closely related to spatial voting models studied in political science (Enelow and Hinich, 1984; Arrow, 1990)
Recall that in bounded divisible PB, each project has a cap of (without loss of generality). One might consider a special case of this setting, where the cost function of each project is given by , and the total budget is . Thus, the set of feasible allocations is given by . This can be thought of as portioning (also called fair mixing) (Aziz et al., 2019), where can be thought of as the fraction of budget devoted to project (after appropriate renormalization of cost functions). As noted in Section 2.1, this is equivalent to the unbounded divisible PB model. Alternatively, one can also think of this model as representing probabilistic voting (Gibbard, 1977), where each project is a candidate and
denotes the probability of choosing candidate
as the winner of the election.4.2 Approaches to Divisible PB
Welfare maximization:
Goel et al. (2019) study the divisible model of PB with unit caps. They consider cardinal additive utilities as well as a spatial model of utilities. They point out that a simple greedy algorithm finds an allocation maximizing the utilitarian welfare. This algorithm sorts the projects in decreasing order of their valueformoney (), and fully funds projects in this order until no more projects can be fully funded. The remaining budget is allocated to partially fund the next project in the list.
Garg et al. (2019) consider a model of decisionmaking in continuous spaces that is more general than PB. In their model, each resident has a favorite point in the space, and her utility for an allocation is based on the norm, specifically,
. They study a class of algorithms called iterative local voting (ILV), in which residents are iteratively asked to modify the current allocation by moving it towards their favorite allocation within a local neighborhood until convergence. This approach adopts the classic stochastic gradient descent (SGD) method from optimization to multiagent decisionmaking.
Fairness:
Fain et al. (2016b) study proportional representation in the divisible model of PB with scalar separable utility functions. They argue that a variant of the classic gametheoretic notion of core captures fairness in the setting. Recall that an allocation is in the core if no subset of voters can use of the budget to find an allocation which is no less appealing than to any member of and strictly more appealing than to some member of . They show that in the divisible model, there always exists an allocation in the core, and present a polynomialtime algorithm for computing one.
Recall that in portioning (i.e. unbounded divisible PB), there are no caps on the degrees of completion. Hence, as discussed in Section 2.1, one can normalize the model such that feasible allocations satisfy , and can be thought of as the fraction of budget devoted to project (Airiau et al., 2019). Aziz et al. (2019) consider portioning — they refer to it as fair mixing — with dichotomous preferences, which was originally studied by Bogomolnaia et al. (2005). They consider the relative merits of several rules. They show that maximizing Nash welfare satisfies several strong fairness properties including the fact that it finds an allocation in the core. It also satisfies the average fair share (AFS) guarantee, which requires that for any set of residents , the average utility of residents in is at least . Another rule with several desirable properties that emerges from their study is the conditional utilitarian rule (CUT). In CUT, each resident is assumed to have a ‘personal budget’ that is fraction of the total budget.^{12}^{12}12Note that CUT easily generalizes to the case where agents have unequal personal budgets. Each resident spreads her personal budget among the projects that she likes that are liked by the most number of residents. Unlike the maximum Nash welfare solution, CUT does not satisfy Pareto optimality, AFS, or core fairness.
Airiau et al. (2019)
consider the portioning problem where voters express preferences over individual projects and use the stochastic dominance (SD) relation to reason about their preferences over probability distributions over projects. They find that using a scoring rule as a proxy for utilities consistent with the ordinal preferences and then maximizing the Nash social welfare with respect to these proxy utilities achieves desirable notions of fairness. Another notable example of algorithms for portioning is the egalitarian simultaneous reservation algorithm
(Aziz and Stursberg, 2014) for agents with weak and transitive ordinal preferences over projects.Incentives:
Aziz et al. (2019) prove that for the portioning problem with dichotomous preferences, both CUT and the Nash welfare maximizing rule provide strict incentives for residents to participate in the voting process. Additionally, CUT is strategyproof (i.e. provides voters no incentive to misreport), while maximizing Nash welfare is not.
Freeman et al. (2019) consider the spatial voting model and focus on the setting in which a resident’s disutility for an allocation is its distance from the resident’s ideal allocation (a.k.a. bliss point). They present the independent markets mechanism, which is both strategyproof and satisfies a basic notion of proportional representation.
5 Extensions and Future Directions
We presented a survey of research on participatory budgeting. Specifically, we presented a mathematical model which classifies existing research across different axes, and surveyed computational and axiomatic approaches proposed in the literature.
Research on participatory budgeting within computational social choice is still in its infancy. As such, only limited models of resident preferences and decisionmaking processes have been explored. Further research is required to design better theoretical models and approaches for participatory budgeting, and bridge the gap between theory and practice. To that end, it is crucial to leverage insights from various disciplines such as computer science, social science, microeconomics, and public policy. In this section, we review several directions in which these models can (and should) be extended to bring them closer to reality and for them to inform realworld implementations of PB.

Multidimensional constraints: Much of the literature focuses on a single, knapsackstyle constraint which stems from a limit on the available money. While current realworld implementations of PB also only deal with money, this is one dimension where further research on practical approaches to conducting PB with multidimensional constraints that capture other types of costs (e.g. costs to the environment) can lead the frontier of novel PB implementations.

Voter or voter group entitlements: In the classic PB setting, giving equal consideration (or weight) to all voters is a normative desideratum. However, one can imagine a more general setting in which different voters or groups of voters bring different resources to the system, and their entitlements need to reflect their contributions. In other words, different voters or groups of voters may have a claim over different parts of the universal budget.

Distributional constraints: Some applications of PB impose lower and upper bounds on the amount of funding which can be allocated to each project or each category of projects (e.g. education or healthcare). Studying the effects of such constraints on the welfare, fairness, and incentives is an interesting direction.

Hybrid models: While our taxonomy (and the literature) partitions PB models into discrete and divisible, there can be hybrid models allowing some projects to be funded only at discrete levels while others on a continuous scale.

Complex resident preferences: Most of the positive axiomatic and algorithmic results in the literature rely on stylized modeling of resident preferences. In practice, residents have complex preferences which stem from intricate synergies between different projects. An important research direction is to extend the existing results to more general classes of utility functions. For example, most utility functions considered in the literature treat projects as independent or substitutes; tackling complementarity in projects remains an interesting challenge.

Initial endowments: In reality, some projects may already have some funds allocated to them (e.g. through previous iterations of PB). The choice between extending funding to existing projects versus funding new projects can give rise to novel challenges.

Pledges: In some cases, private organizations may be willing to pledge financial support to a project conditional on certain projects receiving at least a minimum level of funding. This can affect the choice of vote aggregation methods.

Marketbased approaches: In recent years, marketbased approaches have been investigated for public decision making (Garg et al., 2018). Extending this line of approach to PB can lead to intuitive mechanisms for PB.

Strategic agent models:
The work on incentives in PB focuses on strategyproofness, which aims to prevent manipulations by rational agents. However, people often do not act like rational agents. An interesting direction is to use insights from behavioral game theory, develop models of realistic manipulations that residents may use in PB, and design algorithms to prevent such manipulations.

The role of information: It requires significant effort to inform residents of the costs, benefits, and complexities of different projects. The manner in which this information is communicated can have significant effect on the preferences of the residents; this is a complex issue which requires a detailed study.

An endtoend model: Finally, as we mentioned at the beginning of this chapter, we only focus on the final stage of voting within the entire PB pipeline. However, the initial stages have a direct impact on the final outcome. For example, the agendasetting phase where projects are proposed by the residents themselves crucially affects the latter stages. Formally modeling the entire PB process and designing endtoend solutions is a complex challenge of paramount importance.
To conclude, participatory budgeting is an important grassroots approach to democracy. Research on models, methods, and axioms for PB will provide insights that will be valuable to both the theory and practice of PB.
6 Acknowledgements
Haris Aziz is supported by a UNSW Scientia Fellowship. Nisarg Shah is supported by an NSERC Discovery grant. The authors thank Aditya Ganguly, Barton Lee and Dominik Peters for very helpful feedback.
References

Airiau et al. (2019)
Airiau, S., Aziz, H., Caragiannis, I., Kruger, J., Lang, J., Peters, D., 2019. Portioning using ordinal preferences: Fairness and efficiency. In: Proceedings of the 28h International Joint Conference on Artificial Intelligence (IJCAI).
 Arrow (1990) Arrow, K., 1990. Advances in the spatial theory of voting. Cambridge University Press.

Aziz (2019)
Aziz, H., 2019. Participatory budgeting: Are we really giving a voice to
everyone?
URL https://medium.com  Aziz et al. (2019) Aziz, H., Bogomolnaia, A., Moulin, H., 2019. Fair mixing: the case of dichotomous preferences. In: Proceedings of the 20th. pp. 753–781.
 Aziz et al. (2017) Aziz, H., Brill, M., Conitzer, V., Elkind, E., Freeman, R., Walsh, T., 2017. Justified representation in approvalbased committee voting. Social Choice and Welfare 48 (2), 461–485.
 Aziz et al. (2016) Aziz, H., Lang, J., Monnot, J., 2016. Computing Pareto optimal committees. In: TwentyFifth International Joint Conference on Artificial Intelligence, IJCAI 2016. pp. 60–66.
 Aziz et al. (2018) Aziz, H., Lee, B. E., Talmon, N., 2018. Proportionally representative participatory budgeting: Axioms and algorithms. In: Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS). IFAAMAS, pp. 23–31.
 Aziz and Stursberg (2014) Aziz, H., Stursberg, P., 2014. A generalization of probabilistic serial to randomized social choice. In: Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI). AAAI Press, pp. 559–565.
 Benade et al. (2017) Benade, G., Nath, S., Procaccia, A. D., Shah, N., 2017. Preference elicitation for participatory budgeting. In: Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI). AAAI Press, pp. 376–382.
 Bhaskar et al. (2018) Bhaskar, U., Dani, V., Ghosh, A., 2018. Truthful and nearoptimal mechanisms for welfare maximization in multiwinner elections. In: Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI). pp. 925–932.
 Bogomolnaia et al. (2005) Bogomolnaia, A., Moulin, H., Stong, R., 2005. Collective choice under dichotomous preferences. Journal of Economic Theory 122 (2), 165–184.
 Boutilier et al. (2015) Boutilier, C., Caragiannis, I., Haber, S., Lu, T., Procaccia, A. D., Sheffet, O., 2015. Optimal social choice functions: A utilitarian view. Artificial Intelligence 227, 190–213.
 Bouveret and Lang (2011) Bouveret, S., Lang, J., 2011. A general elicitationfree protocol for allocating indivisible goods. In: Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI). AAAI Press, pp. 73–78.
 Brandl et al. (2016) Brandl, F., Brandt, F., Suksompong, W., 2016. The impossibility of extending random dictatorship to weak preferences. Economics Letters 141, 44–47.
 Brandt et al. (2016) Brandt, F., Conitzer, V., Endriss, U., Lang, J., Procaccia, A. (Eds.), 2016. Handbook of Computational Social Choice. Cambridge University Press.
 Cabannes (2004) Cabannes, Y., 2004. Participatory budgeting: a significant contribution to participatory democracy. Environment and Urbanization 16 (1), 27–46.
 Caragiannis et al. (2017) Caragiannis, I., Nath, S., Procaccia, A. D., Shah, N., 2017. Subset selection via implicit utilitarian voting. Journal of Artificial Intelligence Research 58, 123–152.
 Conitzer et al. (2017) Conitzer, V., Freeman, R., Shah, N., 2017. Fair public decision making. In: Proceedings of the 18th ACM Conference on Electronic Commerce (EC ’17).
 Delort et al. (2011) Delort, C., Spanjaard, O., Weng, P., 2011. Committee selection with a weight constraint based on a pairwise dominance relation. In: Proceedings of the Second International Conference on Algorithmic Decision Theory (ADT). pp. 28–41.
 Dughmi et al. (2016) Dughmi, S., Roughgarden, T., Yan, Q., 2016. Optimal mechanisms for combinatorial auctions and combinatorial public projects via convex rounding. Journal of the ACM (JACM) 63 (4), 30.
 Endriss (2017) Endriss, U. (Ed.), 2017. Trends in Computational Social Choice. AI Access.
 Enelow and Hinich (1984) Enelow, J. M., Hinich, M. J., 1984. The spatial theory of voting: An introduction. CUP Archive.
 Fain et al. (2016a) Fain, B., Goel, A., Munagala, K., 2016a. The core of the participatory budgeting problem. In: Proceedings of the 12th International Workshop on Internet and Network Economics (WINE). Lecture Notes in Computer Science (LNCS). pp. 384–399.
 Fain et al. (2016b) Fain, B., Goel, A., Munagala, K., 2016b. The core of the participatory budgeting problem. In: Proceedings of the 12th International Conference on Web and Internet Economics (WINE ’16). pp. 384–399.
 Fain et al. (2018) Fain, B., Munagala, K., Shah, N., 2018. Fair allocation of indivisible public goods. In: Proceedings of the 19th ACM Conference on Economics and Computation (ACMEC). pp. 575–592.
 Faliszewski et al. (2017) Faliszewski, P., Skowron, P., Slinko, A., Talmon, N., 2017. Multiwinner voting: A new challenge for social choice theory. In: Endriss, U. (Ed.), Trends in Computational Social Choice. Ch. 2.
 Faliszewski and Talmon (2018) Faliszewski, P., Talmon, N., 2018. A framework for approvalbased budgeting methods. CoRR abs/1809.04382.
 Faliszewski and Talmon (2019) Faliszewski, P., Talmon, N., 2019. A framework for approvalbased budgeting methods. In: Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI).
 Fluschnik et al. (2017) Fluschnik, T., Skowron, P., Triphaus, M., Wilker, K., 2017. Fair knapsack. CoRR abs/1711.04520.
 Freeman et al. (2019) Freeman, R., Pennock, D. M., Peters, D., Vaughan, J. W., 2019. Truthful aggregation of budget proposals. In: Proceedings of the 20th ACM Conference on Electronic Commerce (EC ’19).
 Ganuza and Francés (2012) Ganuza, E., Francés, F., 2012. The deliberative turn in participation: the problem of inclusion and deliberative opportunities in participatory budgeting. European Political Science Review 4 (2), 283–302.
 Garg et al. (2018) Garg, N., Goel, A., Plaut, B., 2018. Markets for public decisionmaking. arXiv:1807.10836.
 Garg et al. (2019) Garg, N., Kamble, V., Goel, A., Marn, D., Munagala, K., 2019. Iterative local voting for collective decisionmaking in continuous spaces. Journal of Artificial Intelligence Research (JAIR).
 Gibbard (1973) Gibbard, A., 1973. Manipulation of voting schemes: A general result. Econometrica 41 (4), 587–601.
 Gibbard (1977) Gibbard, A., 1977. Manipulation of schemes that mix voting with chance. Econometrica 45 (3), 665–681.
 Goel et al. (2019) Goel, A., K., A. K., Sakshuwong, S., Aitamurto, T., 2019. Knapsack voting for participatory budgeting. ACM Transactions on Economics and Computation (TEAC) 7 (2), 8:1–8:27.

Gutiérrez (2017)
Gutiérrez, B., 2017. Madrid as a democracy lab. Accessed: 20180502.
URL https://www.opendemocracy.net/democraciaabierta/bernardogutirrez/madridasdemocracylab  Iyengar and Lepper (2000) Iyengar, S. S., Lepper, M. R., 2000. When choice is demotivating: Can one desire too much of a good thing? Journal of personality and social psychology 79 (6), 995.
 Kalai and Smorodinsky (1975) Kalai, E., Smorodinsky, M., 1975. Other solutions to nash’s bargaining problem. Econometrica 43 (3), 513–518.
 Karp (1972) Karp, R. M., 1972. Reducibility among combinatorial problems. In: Complexity of computer computations. Springer, pp. 85–103.
 Klamler et al. (2012) Klamler, C., Pferschy, U., Ruzika, S., 2012. Committee selection under weight constraints. Mathematical Social Sciences 64 (1), 48–56.

Legendre et al. (2017)
Legendre, J., Madénian, H., Scully, P. L., 2017. Participatory budgeting in
Paris, France. Accessed: 20180502.
URL http://participedia.net/en/cases/participatorybudgetingparisfrance  Lu and Boutilier (2011) Lu, T., Boutilier, C., 2011. Budgeted social choice: From consensus to personalized decision making. In: Proceedings of the 22nd Joint Conference on Artifical Intelligence (IJCAI ’11). pp. 280–286.
 Mundt (2017) Mundt, M., 2017. Participatory budgeting evaluation report. https://pb.cambridgema.gov/read_the_pb3_evaluation, last accessed: Aug 5, 2019.
 Murray (2019) Murray, C., 2019. Toronto’s participatory budgeting pilot evaluation. https://www.toronto.ca/legdocs/mmis/2019/bu/bgrd/backgroundfile124370.pdf, last accessed: Aug 5, 2019.
 Papadimitriou et al. (2008) Papadimitriou, C., Schapira, M., Singer, Y., 2008. On the hardness of being truthful. In: Proceedings of the 49th Symposium on Foundations of Computer Science (FOCS). IEEE, pp. 250–259.
 Peters (2018) Peters, D., 2018. Proportionality and strategyproofness in multiwinner elections. In: Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS). Vol. 1549–1557.
 Procaccia and Rosenschein (2006) Procaccia, A. D., Rosenschein, J. S., 2006. The distortion of cardinal preferences in voting. In: Proceedings of the 10th. pp. 317–331.
 Rios and Insua (2008) Rios, J., Insua, D. R., 2008. A framework for participatory budget elaboration support. Journal of the Operational Research Society 59 (2), 203–212.
 Rios et al. (2005) Rios, J., Insua, D. R., Fernandez, E., Rivero, J. A., 2005. Participatory budget formation through the web. In: EGovernment: Towards Electronic Democracy, International Conference, TCGOV 2005, Bolzano, Italy, March 24, 2005, Proceedings. pp. 268–276.
 Röcke (2014) Röcke, A., 2014. Framing citizen participation: participatory budgeting in France, Germany and the United Kingdom. Springer.

Samir (2018)
Samir, R., 2018. Madrid, part 1: edemocracy hub of europe. Accessed:
20190428.
URL http://netdem.nl/en/articles/madridedemocracyhubeurope/  Satterthwaite (1975) Satterthwaite, M. A., 1975. Strategyproofness and Arrow’s conditions: Existence and correspondence theorems for voting procedures and social welfare functions. Journal of Economic Theory 10 (2), 187–217.
 Shah (2007) Shah, A., 2007. Participatory Budgeting. Public sector governance and accountability series. The World Bank.
 Shapiro and Talmon (2017) Shapiro, E., Talmon, N., 2017. A condorcetoptimal participatory budgeting algorithm. arXiv preprint arXiv:1709.05839.
 Vazirani (2013) Vazirani, V. V., 2013. Approximation algorithms. Springer Science & Business Media.
 World Bank (2008) World Bank, 2008. Brazil: Toward a more inclusive and effective participatory budget in Porto Alegre. World Bank.
Comments
There are no comments yet.