What Should We Optimize in Participatory Budgeting? An Experimental Study

Participatory Budgeting (PB) participatoryBudgeting is a process in which voters decide how to allocate a common budget. It was first implemented in 1989, by the Brazilian municipality of Porto Alegre. Since then, it had widely spread to more than 1,500 municipalities worldwide, including major European capitals such as Madrid, Paris, Berlin, and Warsaw, as well as to other municipalities in Latin and North America, Asia, Australia, South Africa, and the Middle-east participatoryBudgeting ; shah2007participatory ; PBO . PB usually operates as follows: first, the city council declares a portion of its annual budget to be assigned to the PB process. Then, city residents can suggest projects, such as, e.g., bicycle routes, certain renovations, playgrounds, etc. The city then filters the list of all proposals by the residents and assigns a price tag to each of them. Then, in the second phase of the process, residents act as voters by specifying their preferences over the projects, usually by submitting approval ballots (e.g., each resident can choose at most $5$ projects to vote for). Then, an aggregation method (i.e., a voting rule) is used by the city to select a subset of the proposed projects to fund.

From a social choice perspective, PB is usually formulated as follows: given a set of projects $P$ with their associated cost function $C:P\to\mathbb{N}$, a set of voters $V$ with their associated approval ballots, and a budget limit $\ell$; the aggregation task is to output a bundle $B\subseteq P$ satisfying $\sum_{p\in B}C(p)\leq\ell$. For this model, a wide variety of mathematical formulations for PB were proposed, investigated, and addressed through either an axiomatic and/or an algorithmic approach (see aziz2020participatory for a recent survey). Specifically, existing research on PB focuses almost exclusively on designing computationally-efficient aggregation methods that satisfy certain axiomatic properties deemed \sayfair or \saydesirable by the research community. For example, Fain et al. FainGM16 aim at satisfying a proportionality axiom related to the game-theoretic concept of the core (see also their generalization fainMunSha18:core_and_pb ); Flushnik et al. fairknapsack and Peters et al. peters2020proportional consider PB when voters provide cardinal utilities; Aziz et al. aziz2018proportionally propose an aggregation method for PB with approval ballots that satisfies a proportionality axiom related to the axiom of Justified Representation for multiwinner elections mwchapter (see also the related paper regarding ordinal ballots aziz2019proportionally ); Benade et al. benade2017preference choose among different ballot types for PB, based on a notion of distortion (which, roughly speaking, asks how \sayclose an aggregation based on each ballot type is to the best outcome that could be computed if the true utilities were known); Faliszewski and Talmon abpb study various approval-based aggregation methods for PB, concentrating on certain monotonicity axioms; Jain et al. jain2020participatory generalize the model of Faliszewski and Talmon by considering interactions between projects.

To our knowledge, most of the existing PB literature has yet to consider a user study perspective, focusing almost exclusively on axiomatic and/or algorithmic approaches to PB (indeed, we mention some related work that does so below). Our work thus complements the existing PB research through a user study, involving two experimental settings (overall, $N=215$), aimed at identifying what potential voters (i.e., non-experts) deem desirable in simple PB settings. In particular, we seek to offer answers to the following two questions:

1. 1.

   Assuming that voters get some sort of utility from each project, and assuming that these values are known, then what function of these utilities should be optimized when choosing a bundle of projects to fund, according to the views of common people?

2. 2.

   Assuming that voters only provide approval ballots, and assuming that such approval ballots represent some underlying per-project utilities, how shall these utilities be estimated, according to the views of common people?

Indeed, our approach in this study is a utility-based one, following the general utility-based approach commonly used in game theory and decision theory. In the context of PB, we mention the paper of Talmon and Faliszewski abpb , which study several aggregation methods for PB through the definition of several satisfaction functions; these satisfaction functions essentially translate a voter ballot together with a possible output bundle into a numerical value corresponding to the expected satisfaction of the voter for the bundle, which is closely related to our second experiment. In this context, in our first experiment we assume that we are given these per-project satisfaction values explicitly, and some of these are adopted in our second experiment as well.

To this end, we report on set of experiments considering two different settings: First, settings in which the utilities each voter receives from each project are objective, additive, and known; given such utilities, we ask non-experts to choose the most appropriate bundle to fund. Second, settings in which only the approval ballots of voters are known, and we ask non-experts to choose the most appropriate bundle to fund.¹¹1All experiments were authorized by the corresponding IRB. We use the results to identify which aggregation methods common people view as the most appropriate in known-utilities cases and in approval-ballots cases.

Our results show that recently proposed aggregation methods, whose development is in the focus of the research effort on PB, need not necessarily align with what non-experts consider appropriate or desirable. Instead, we identify a few, quite standard approaches that appear to be more adequate. We further identify a few possible discrepancies between what non-experts consider \saydesirable and how they perceive the notion of \sayfairness, between men and women and between people of different economical statuses. Our results can be instrumental in the selection of appropriate PB aggregation methods in practice and highlight various promising avenues for further research for the community.

There are

This study is inspired by a variety of user studies performed in the larger context of computational social choice research, which have helped to better situate and understand the theoretical and computation advances made in various settings. For example, human voting behavior has been the focus of various experimental studies such as that by Scheuerman scheuerman2019heuristic ; scheuerman2020modeling , who has identified different manipulation aspects in human approval voting; Tal et al. tal2015study , who have demonstrated different voting behaviors in various online settings under the Plurality rule; Zou et al. zou2015strategic , who have studied voter behavior in Doodle pools; and Grandi et al. grandi2020voting , who have studied iterative human voting in combinatorial domains. In a very broad context, some studies in experimental economics share a common goal in quantifying justice or fairness (see, e.g., konow2016economics ). In the context of fair division, we mention the work of Herreiner and Puppe herreiner2009envy as well as that of Gal et al. gal2016fairest . Furthermore, in the realm of matching/assignment problems, user studies have helped in understanding non-truthful behaviors in corresponding non-truthful mechanisms (e.g., artemov2017strategic ), \sayalmost truthful mechanisms (e.g., rosenfeld2020too ), and truthful mechanisms (e.g., rees2018experimental ). Common to these and similar works is the understanding that any intelligent automated decision, let alone one that involves potentially millions of dollars, necessitates the understanding of real-world users (in our case, voters/residents) and their judgment (in our case, what people deem appropriate) rosenfeld2018predicting . Closely related to our work is the recent study by Bulteau et al. 9475498 , who have studied theoretically, empirically and through a human study, various notions of justified representation in perpetual voting settings. In the context of PB, we mention several works that deal with user experiments: Goel et al. goel2019knapsack study behavior of voters using Knapsack ballots for PB; Laruelle laruelle2020voting studies a specific PB instance; and Benade et al. benade2018efficiency conducted a user experiment to compare different ballot types for PB.

In this paper, we consider the standard model of PB, also referred to as combinatorial PB aziz2020participatory . We assume a set $P=\{p_{1},\ldots,p_{m}\}$ of projects, with an associated cost function $C:P\to\mathbb{N}$, such that $C(p)$ is the cost of project $p\in P$. For simplicity, we slightly overload notation by defining $C(P^{\prime}):=\sum_{p\in P^{\prime}}C(p)$ where $P^{\prime}\subseteq P$. Furthermore, there is a set $V=\{v_{1},\ldots,v_{n}\}$ of voters, where each voter $v_{i}$ reports her preferences over the projects. Again, we overload notation and refer to the preference of voter $v_{i}$ as $v_{i}$ as well.

In this study we focus on two common preference types:

• •

  Cardinal utilities: here, $v_{i}$ is a utility function, such that $v_{i}(p)$ is the utility gained by voter $i$ if project $p$ were to be funded. As an example, one can consider the expected revenue for a store if a certain project were to be funded. We assume additive utilities (in particular, we assume that no project interactions, like those assumed by Jain et al. jain2020participatory are present).

• •

  Approval ballots: here, each voter specifies a subset of the projects that she \sayaccepts; that is, $v_{i}\subseteq P$, so that $p\in v_{i}$ if $v_{i}$ approves $p$ and $p\notin v_{i}$ if $v_{i}$ disapproves $p$.

Given a budget limit $\ell$, an aggregation method is given a tuple $(P,C,V,\ell)$ and is required to output a winning bundle $B\subseteq P$, with $\sum_{p\in B}c(P)\leq\ell$, containing the projects that should be funded.²²2Ties are broken arbitrarily.

In this experiment, we examine the case of PB with real-valued utilities. (In a way, this experiment relates to general aggregation of utilities; we chose to conduct this experiment as the setting of PB is specific and thus may have different properties; furthermore, we are not aware of experiments in the general setting that are similar enough to the aim of this experiment.) Specifically, we devise a simple yet natural PB scenario where the utilities each voter receives from each project are objective, additive, and known; given such utilities, non-experts are tasked with choosing the most appropriate bundle to fund. Specifically, we use the following motivational scenario in our experiment:

The above scenario was devised following this rationale: by using monetary revenues for stores, which are assessed by an independent third party, we can fairly assume that potential decision makers would consider the utilities as being objective, additive, and known. In addition, since Alice’s utility is not defined at all (she is only introduced as the mall’s manager), we leave it up to the decision maker to decide what she constitutes as appropriate in this generic setting, without introducing potentially biasing terms such as \sayfairness.

Following the motivating scenario’s text, participants were presented with an example instance, as shown in Figure 1.

Experiment 1 (Section 3) has focused on identifying which aggregation method is preferred by common people, given voters’ cardinal utilities. As discussed before, in many real-world settings, obtaining cardinal utilities is impractical or infeasible (also, currently most real-world PB processes use approval ballots and not cardinal utilities; note that other ballot type exist, e.g., Knapsack ballots goel2019knapsack , however we have chosen approval ballots for their simplicity and popularity). Thus, in our second experiment we turn to consider the case where explicit, cardinal utilities are unavailable. Instead, we assume that each voter provides us with a subset of \sayapproved projects $v_{i}$ such that $p\in v_{i}$ if voter $i$ approves project $p$. Indeed, this is the setting of approval-based PB abpb . We focus on the SUM and NASH aggregation methods that, according the results of Experiment 1, favorably compare to the other examined competing methods. Specifically, we seek to investigate how non-experts translate voter preferences, as expressed by approval ballots, into cardinal utilities that can, in turn, be aggregated using either SUM or NASH.

To this end, as was the case in Experiment 1, we devise a simple yet natural PB scenario in which participants are tasked with choosing the most appropriate bundle to fund. We use the following motivational scenario in our experiment⁷⁷7Note that the participants are not aware whether we use SUM or NASH.:

The above scenario was devised following this rationale: by using generic projects we seek to avoid participants casting their own preferences into the decision setting. In addition, since Alice’s utility is not defined at all (she is only introduced as the owner of the management company), we leave it up to the participants to decide what she constitutes as appropriate in this generic setting without introducing potentially biasing terms such as \sayfairness.

Note that in Experiments 1 and 2, we have explicitly encoded several aggregation methods in order to simplify the participants’ task. However, this design may also introduce some bias to the results, specifically, participants could have chosen differently if they were to make their own budget-feasible bundles. In order to examine this issue we replicate Experiments 1 and 2, yet this time, we do not provide the participants’ with pre-computed bundles which correspond to the examined aggregation methods. To that end, we recruited 35 new participants who have not taken part in Experiment 1 or 2. All participants are Israeli Master students who attend the authors’ courses.

In a preliminary investigation with volunteers from our labs we have found that replicating the two experiments without providing the pre-computed bundles was significantly more complex than we thought. Specifically, our volunteers indicated that solving more than very few instances at a time was simply too hard for them to do properly. As such, we have decided to randomly allocate 15 participants to the replication of Experiment 1, which we will refer to as Experiment 3.1, and 20 to the replication of Experiment 2, which we will refer to as Experiment 3.2. In both, we have asked participants to solve \sayat least three settings out of the randomly ordered set.

Through the above human study, we investigated what ordinary people (i.e., non-experts) deem as appropriate solutions to instances of participatory budgeting. Our study comprised of several artificially-generated instances of participatory budgeting for which non-experts were asked to select the bundles they consider to be the most appropriate. In addition, we have asked our participants to rank verbal explanations that correspond to different aggregation methods for participatory budgeting. We focus on both the case of real-valued utilities (Experiment 1) as well as on the case of approval ballots (Experiment 2).

The main conclusion from Experiment 1 is that most people select the NASH method (i.e., maximizing the Nash product of voter utilities) or the SUM method (i.e., maximizing the sum of voter utilities), with NASH being more popular than SUM. Our confidence in this conclusion is rather high, as participants were generally consistent in their choices.

As the first experiment consisted of instances with real-valued utilities, the two most popular aggregation methods were selected for further investigation under the setting of approval ballots in Experiment 2. The main conclusions from Experiment 2 is that most people select bundles that correspond to the #Projects utility function (i.e., the utility of a voter equals the number of projects approved by the voter that are being funded in the winning bundle). The second most popular utility function is the 0/1 function, that assumes a unit utility when at least one project approved by the voter is funded. Here, as well, our confidence in the conclusions is rather high, as our participants were generally consistent in their choices.

Despite the seemingly coherent results discussed above with respect to the bundles selected by our participants, we have observed a discrepancy between the bundles participants select and their ranking of the corresponding verbal explanations. This discrepancy is more visible in Experiment 1 and when considering the NASH aggregation method in Experiment 2, but less visible when considering the SUM aggregation method in Experiment 2. We believe that this is at least partially due to the NASH method being a more complicated aggregation method. We view this issue as a good motivating example for the necessity of explainable social choice peters2020explainable , i.e., the need to find good ways to communicate aggregation methods to common people. It is, indeed, important to note that these results might be also influenced by the specific verbal explanations we have chosen.

We recognize that the current study is limited by the amount, quality, and diversity of the data used. In the context of this work, our participant pool was neither very large nor very heterogeneous and consisted of 215 Israeli and Polish university students. This may hinder the generalization of our findings in the general population. Future replication of this study in the general population could address this concern. In addition, our PB settings were relatively small in terms of number of projects and voters compared to how PB is commonly practiced by municipalities. It is, however, important to note that in a preliminary informal examination of the matter we have found that testing larger instances (e.g., $>10$ voters or projects) may be too complex for non-experts and is likely to bring about poor-quality answers. This result is also supported by a recent study laruelle2021voting . As such, we plan to examine the issue of scalability in the future through other means such as in-depth interviews with potential decision makers. It is also important to note that some technical study design decisions have also had an effect the results. For example, in Experiment 2, we assumed that voters approved their top 2 or top 3 project while, in some settings, voters could have approved a different number of projects. Furthermore, our random tie-breaking may indeed have an effect on the results, in particular wrt. the Nash product. Last, it is important to remember that different aggregation methods may provide the same solution for a given PB setting. In our empirical evaluation, we focus on settings for which the examined aggregation methods disagree. We found that any two methods we examined provide different solutions for 19%-42% of the randomly generated PB settings we examined.

We plan to extend this work in several directions: first, we seek to establish a collaboration with an Israeli municipality in order to examine our findings in a real-world large scale PB setting. Since the standard aggregation method used today is a greedy approximation algorithm to SUM over #Projects, real-world results of additional methods could possibly shape the way PB is practiced. Second, we plan to consider various ballot types, such as Knapsack votes. Third, we plan to investigate what non-experts deem desirable in additional non-trivial social choice settings such as mutliwinner elections mwchapter . Last, we plan to further examine additional human-centered aspects of PB decision making such as the presumed need for transparency or explainability from an aggregation method to be useful in practice. Specifically, we wish to examine how PB outcomes should be best mitigated to human decision makers.

Nimrod Talmon was supported in part by the Israel Science Foundation (ISF; Grant No. 630/19).