Proportional Participatory Budgeting with Additive Utilities
Authors: Grzegorz Pierczyński
Piotr Skowron
Dominik Peters
Venue: NeurIPS 2021 Poster (2021)
Keywords: committee elections
participatory budgeting
aggregating preferences

Abstract: We study voting rules for participatory budgeting, where a group of voters collectively decides which projects should be funded using a common budget. We allow the projects to have arbitrary costs, and the voters to have arbitrary additive valuations over the projects. We formulate two axioms that guarantee proportional representation to groups of voters with common interests. To the best of our knowledge, all known rules for participatory budgeting do not satisfy either of the two axioms; in addition we show that the most prominent proportional rule for committee elections, Proportional Approval Voting, cannot be adapted to arbitrary costs nor to additive valuations so that it would satisfy our axioms of proportionality. We construct a simple and attractive voting rule that satisfies one of our axioms (for arbitrary costs and arbitrary additive valuations), and that can be evaluated in polynomial time. We prove that our other stronger axiom is also satisfiable, though by a computationally more expensive and less natural voting rule. 

Proportional Participatory Budgeting with Additive Utilities
Dominik Peters University of Toronto Toronto, ON, Canada dominikécs. toronto.. edu pierczynski leriski@miimmi @mimuw. edu. pl p w.s.wronomimus edu pl
Grzegorz Pierczyúski University of Warsaw
Piotr Skowron
University of Warsaw
Warsaw, Poland
Warsaw, Poland
Abstract
We study voting rules for participatory budgeting, where a group of voters col- lectively decides which projects should be funded using common budget. We allow the projects to have arbitrary costs, and the voters to have arbitrary additive valuations over the projects. We formulate two axioms that guarantee proportional representation to groups of voters with common interests. To the best of our knowl- edge, all known rules for participatory budgeting do not satisfy either of the two axioms; in addition we show that the most prominent proportional rule for commit- tee elections, Proportional Approval Voting, cannot be adapted to arbitrary costs nor to additive valuations so that it would satisfy our axioms of proportionality. We construct a simple and attractive voting rule called the Method of Equal Shares that satisfies one of our axioms (for arbitrary costs and arbitrary additive valuations), and that can be evaluated in polynomial time. We prove that our other stronger axiom is also satisfiable, though by computationally more expensive and less natural voting rule.
Introduction
Consider abstract model where there is group of agents who have preferences over set of options. Each option has a cost, and the goal is to select subset of options whose total cost does not exceed a predefined budget. This model provides a formal framework for number of real real-life scenarios. Perhaps the most natural example is Participatory Budgeting (PB). Through a voting system, PB allows residents of city (the agents) to decide which projects (the options) will be funded by the government. In recent years, PB has been started in many cities around the world [Cabannes, 2004, Aziz and Shah, 2020], and in some cases is used to decide significant fraction of the city budget. For example, in Paris, PB has been run every year since 2014, and since 2016 the total amount funding for PB in Paris has been more than 100 million euros annually. Besides PB, the formal model captures the problem of electing representative committee for group of voters, say faculty board or a parliament [Faliszewski al., 2017, Lackner and Skowron, 2020], but also appears useful in situations that do not involve humans. For example, our framework describes the problem of selecting validators in consensus protocols. such as the blockchain [Cevallos and Stewart, 2020], the problem of selecting web pages that should be displayed in response to user queries, where the selected set of web pages should be useful for different types of user profiles [Skowron et al., 2017] or the problem of locating public facilities [Skowron et al., 2016, Byrka et al., 2018). Algorithms for PB can even be used for improving the quality of genetic algorithms [Faliszewski al., 2016 While there are numerous applications of the model that we consider, for concreteness we will use terminology referring to participatory budgeting.
In this paper, we focus on designing algorithms (which we call aggregation rules) for selecting projects. We are interested in rules that are fair in the sense that each agent has roughly equal influence on the outcome. This implies that the selected subset of projects must proportionally represent the views of
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Northside
SOOL
pop. 120k
D ST0OK
T
550
S1500
F
5006
Circleville
Sioe
Westside
Eastside
pop.
H Be0k
G
pop. 110k
R $138
?
SAL
J
STUR
A
.V 540
K
L SII
Southside
pop. 80k
Figure 1: Map of Circleville, showing the locations and costs of the PB project proposals.
the voters, and every group of voters with similar preferences should have an appropriate portion of the available budget allocated to fulfilling those preferences. Our results contribute to the study of fairness algorithmic decision making. Notably, while many works on this topic aim be fair to agents described by feature vectors (that for example contain demographic information), we only use agents' preferences. Fair algorithms will need identify cohesive groups of agents on their own.
To understand the constraints that fairness and proportionality place on the decision procedure, let us start by discussing the way cities implement PB today. To count the votes, most cities a variant of a simple protocol: Each voter is allowed to vote for a certain number of project proposals. Then, the projects with the highest number of votes are funded, until the budget limit is reached. While simple and intuitive, this is a bad voting rule. To see this, consider Circleville, a fictional city divided into four districts. A map of the city is shown in Figure 1. The districts all have similar sizes, but Northside has the largest population. Suppose $400k have been allocated to PB, and suppose that all the project proposals are of local character (such as school renovations), and so residents only vote for projects that concern their own district. For example, every Northside resident will cast votes for projects A, B, C, and D, but no one else votes for these. Because Northside is the most populous district, the Northside projects will all receive the highest number of votes, and the voting rule described will spend the entire budget on Northside projects. The 280k residents of the other districts are left empty- handed.
To circumvent this obvious issue, many cities have opted hold separate elections for each district. The budget is divided in advance between the districts (c.g., in proportion to their number of residents), district, and voters only vote in their local election. While this avoids
each project is assigned the issue of spending the entire budget in Northside, this fix introduces many other problems. For example, projects on the boundary two districts (such as A and P) need to be assigned to one of them. Residents of the other district may be in favor of the boundary project, but cannot vote for it. Thus boundary projects are less likely to funded, even if they would be more valuable overall. Similarly, projects without a specific location that benefit the entire city cannot be handled. Also, interest groups that are not geographic in nature will be underserved; for instance, parents across the city might favor construction of a large playground (project C). but with separate district elections, parents cannot form a voting block. Similarly, bike riders across the city cannot express their joint interest in the construction of bike trail along Example River (projects R, S, H. and G).
To solve these problems, seems desirable to hold single city-wide election, but use voting system that ensures that money is spent proportionally. The voting system should automatically and endogenously identify groups of voters who share common interests, and make sure that those groups are appropriately represented. This aim has been identified by several researchers [Aziz et al., 2018b], but no convincing proposal for a proportional voting rule has emerged so far. Indeed, no good formalization of "proportionality" for the PB context has been identified in the literature, except for

---

the concept of the core. However, the core is a very demanding requirement, and there are situations where it fails to exist [Fain et al., 2018].
In this paper, we formalize proportionality for participatory budgeting as an axiom called extended justified representation (EJR). The axiom requires that no group of voters with common interests is underserved. We construct a simple and attractive voting rule (the Method of Equal Shares) that satisfies EJR for approval preferences, and that satisfies EJR up one project for general additive valuations. We then discuss a strengthening of EJR-which we call fully justified representation (FJR) and show that this strengthening is still satisfiable, albeit by a different voting rule.
Both our proportionality axiom and our voting rule are generalizations of concepts that have been introduced in the literature multi tilter-iinerr voting [Faliszewski et al., 2017]. That literature can be seen as handling a special case of PB, where all projects cost the same amount of money. This is often called the unit cost assumption. It turns out that the unit cost assumption substantially simplifies the problem. Further, much of the relevant literature studies rules that work with approval ballots, where voters are allowed approve or disapprove each project. In our paper, we allow any additive valuations (not just 0/1), which is more expressive. The proportionality axioms and voting rules that we introduce all work for general additive valuations. This is notable, since allowing additive valuations introduces significant conceptual difficulty. Indeed, most prominent multi-winner voting rules do not naturally extend additive valuations (or at least not gracefully).
Allowing additive valuations gives voters a way to more precisely describe their preference inten- sities. This can be valuable information in a PB setting where there are often projects which differ significantly in their cost. In practice, PB elections typically only elicit approval information. Using rules such as ours (defined for general additive valuations), in two different ways: either as 0/1 utilities (so that a voter's utility for a selected outcome is the number of approved funded projects) or as cost-based utilities (so the utility for an outcome the total cost of approved funded projects). These two interpretations lead to interestingly different rules, with cost-based utilities favoring more expensive projects and leading to outcomes that are more similar to the outcomes that are selected by the greedy rule typically used by cities today.
can interpret this approval information
2 Preliminaries
For each t N, write it] = [1, .., An election is tuple (N, C, cost, (u.)iE)), where:
[n] and C' = (ci,..., are the sets of voters and candidates (or projects).
cost: C -++00 Q+ is function that for each E C7 assigns the cost that needs to be paid if c is selected. For each T S C, we write cost (T) Eeer cost(e) for the total cost of T.
For each voter i NN the function u, C - [0, 1] defines i's additive utility function. If set T C C of candidates is implemented, i's overall utility is (,) = Eeer Wz Mz(c). For subset 5 C N of voters, we further write (T) Eies ΣeET uc(c) for the total utility enjoyed by S if is implemented. We assume that u. (c) > 0 for each c E C, so that every candidate is assigned positive utility by least voter.
The voters have a fixed common budger which we normalize to A subset of candidates W C is feasible if cost(W) (W) < 1. Our goal is to choose a feasible subset of candidates, which we call an outcome, based on voters' utilities. An aggregation rule (or, in short, a rule) is function R that for each election F returns a feasible outcome W = RRF) called the winning outcome.
There two interesting special cases of our model:
Committee elections. In this case, there exists k N (the committee size) such that each candidate costs 1/a. Then W is an outcome if and only if [W| < k. In this special case we also refer to outcomes as committees, and we say that the election satisfies the unit cost assumption.
Approval utilities. In this case, for each i E N and E C it holds that u,(c) E 1). The approval set of voter is A(i) == {cE O: u,(c) = 1}. and we say that approves candidate c e A(1). If c E A(i) n W. we say that is representative of i.
Often we combine of these special cases, and study approval-based committee elections.
Sometimes there ties. For the results of this paper it does matter how these ties are broken.
3

---

3 The Method of Equal Shares (MES)
Recently, Peters and Skowron [2020] introduced an aggregation rule for approval-based committee clections that they called Rule X. In that setting the rule satisfies combination of appealing proportionality properties. Here, we extend it to the more general model of participatory budgeting, that is, to the model with arbitrary costs and utilities. We will call this rule the Method of Equal Shares (in short, MES).
Definition 1 (Method of Equal Shares (MES)). Each voter is initially given an equal fraction of the budget, i.e., each voter is given 1/n dollars. We start with an empty outcome W = 0 and sequentially add candidates W. To add a candidate to W, we need the voters to pay for c. Write Pt(c) for the amount that voter i pays for we will need that ΣiEN Pi(c) = cost(c). We write ps (:W Erew Pi(c)= S 4 for the total amount has paid so far. For p 2 O, we say that candidate e & is p-affordable if
Σ min t - p..(W), p) = cost(c). NEN
If no candidate p-affordable for any MES terminates and returns W. Otherwise it selects a candidate & W that is p-affordable for minimum p. Individual payments are given by
p:(c) = min # pw)),, ue(c)
Intuitively, when the Method of Equal Shares (MES) adds candidate it asks voters to pay an amount proportional to their utility u, wc(c) for c; in particular, the cost per unit of utility is p. If voter does not have enough money, the rule asks the voter to pay all the money the voter has left, which 1 - (W). Throughout the execution of MES, the value of p increases. Thus, candidates are added in decreasing order of utility per dollar that the voters get from the candidates. In comparison to the work of Peters and Skowron [2020], the new elements in our definition the rule are (1) the formula according to which the costs of selected projects are divided among the voters, and (2) the algorithm specifying in which order the candidates are selected; these are critical to ensure that the rule is proportional.
3.1 Extended Justified Representation (EJR)
The first notion of proportionality that we examine is Extended Justified Representation (EJR). This axiom was first proposed for approval-based committee elections [Aziz et al., 20 Even for the special case of approval-based committee elections, only few rules are known satisfy EJR [Aziz et al., 2017, 201 8a, Peters and Skowron, 2020], but the Method of Equal Shares is one of them. In this section, we introduce a generalization of EJR to the PB model and show that our rule continues to satisfy EJR.
We first recall the definition of EJR for upproval-basee committee elections. Intuitively, this axiom ensures that every large enough group of voters whose approval sets have a large enough intersection must obtain fair number of representatives. For example, if group of voters forms a-fraction of the whole population and if this group agrees on sufficiently many candidates, then it should be allowed to decide about a-fraction of the elected candidates. Formally, this is achieved by excluding the possibility that each member of the group approves less than [aok] elected candidates.
Definition 2 (Extended Justified Representation for approval- committee elections). We say that a group of voters S is ê-cohesive for & E N if |S| 2 f/k n and INke A(i) > &. A rule R. satisfies extended justified representation if for each election instance F. and each ê-cohesive group of voters there exists voter i S such that [A(i) n R(E) > L.
At first sight it is unintuitive that we only require that at least one voter obtain é representatives. However, the strengthening of EJR that requires each member of S to obtain & representatives is impossible even on very small instances [Aziz et al., 2017]. Still, even with only the an-least-one guarantee, EJR has plenty of bite [Aziz et al., 2018 80, Skowron, 2018, Peters and Skowron, 2020].

---

The generalization of this axiom to the PB model is not straightforward and to the best of our knowledge none has been proposed in the literature. 2 To warm up, let's first relax the unit cost assumption, but stay in the approval approval-based setting. Then EJR should state the following.
Definition 3 (Extended Justified Representation for approval- based elections). We say that group of voters S is -cohesivve for T S C' if [S] 2 cost(() n and S NiES A(i). A rule R satisfies extended justified representation if for each election instance E' and each T-cohesive group S of voters there exists a voter E S such that [A(1) n R(E) 2 |
Thus, cohesiveness now requires that the group can identify a collection of projects T that they all approve and that is affordable with their fraction of the budget ([S) 2 cost(T) n). Note that voters i E S obtain utility (T) = (T] from T: EJR requires that least one member of S must attain this utility in the election outcome.
To further generalize EJR beyond approvals is more difficult, because the notion of a candidate who is approved by all members of S does not have an analogue. Instead, we quantify cohesion by calculating the minimum utility that any member of S assigns to each project in T'.
Definition 4 (Extended Justified Representation),
group of voters S is (a, -cohhesvee, where a: C- [0; 1] and T S C, if [S] 2 cost(T) n and if u;(c) 2 acc) for all i E S and c E T'. A rule R. satisfies extended justified representation if for each election instance E and each (a, -oohesive group of voters S there exists a voter E S such that (E()) 2 a(e)
Again, an (ax, -oohessve group of voters S can propose the projects in T, since they are affordable with S's share of the budget. The values (a(c))eET denote how much the coalition S agrees about the desirability of the projects in T. In particular, we have u, (T) 2 Eeet a(e) for each i S. Consequently, Definition 4 prohibits any outcome in which every voter in S gets utility strictly lower than Eeer (c); hence there must exists E S such that (R))) 2 acer
EJR is a demanding property in the PB model. Consider the special case where there is only one voter, N {1}. Then any outcome W satisfying EJR must solve the knapsack problem, i.e. it must maximize Enew in (c), since otherwise an optimum knapsack T witnesses an EJR violation. Because the knapsack problem is weakly NP-hard, this presents a difficulty for a rule to satisfy EJR.'
Proposition 1. Unless P = NP, no aggregation rule that can be computed in strongly polynomial time can satisfy EJR in the general PB model.
Indeed, the Method of Equal Shares fails EJR in the general PB model. However, we can show that it satisfies a mild relaxation, which requires EJR to hold "up to one project".
Definition 5 (Extended Justified Representation Up To One Project). A rule R satisfies extended justified representation up to one project if for each election instance E and each (a, coohesive group of voters S there exists a voter i E S such that either u, (R((E)) 2 Eeer a(c) or for some a E C holds that (R) U {a}) > Ecgra(c).
It worth noting that in the approval-basee model. Definitions and 5 are actually equivalent, because the "up to one project" option never applies: Consider an (a, cohhceiiive group of voters S. Since voters' utilities are 0/1, we may assume that for each c T we have a(c) 1: if (<c) 0 this is clear; otherwise we can remove from T without losing cohesiveness. Thus, the cohesiveness condition equivalent to the condition that every voter approves every candidate in T. Finally, note
that in the approval model, due to the strict inequality, both conditions u: (:((E)) 2 Eeer acc) and Bagc.u, u. (R(E) U {a}) > E.ET a(c) boil down to A(i) n R(E)) 2 E.ET a(c) = [T].
Our main result is that the Method of Equal Shares satisfies EJR up to project in the general PB model. By the previous observation, it hence satisfies EJR in the approval- -aasedl---aed model (even when not imposing unit costs).
Theorem 1. The Method of Equal Shares satisfies EJR up one project in the participatory budgeting model.
2 Aziz et al. [2018b] generalize the weaker axiom of Proportional Justified Representation (PJR) [Sánchez- Fernández et al., 2017] beyond unit costs, but they operate a non-standard utility model where voters care more about more expensive projects.
Aziz et al. [2018b, Prop. 3.8] prove similar result for their BPJR-L notion, by reduction from subset sum.
5

---

Proof. For a contradiction, assume there is an election E, set S S N and a set T S C such that: (i) cost(T)) I 151/,, (ii) (.(c) 2 a(c) > (candidates with a<c)
be skipped) for each i and E T, and (iii) u. (R(F) U {a}) S Eeer ((c) for each i E S and E T.
Assume for while that the voters from S have unrestricted initial budgets, and let analyze how MES would proceed in this case. For simplicity, let us rename the candidates in I" so that T ,c, Ct) and that for 1 S i < S candidate c; picked by MES before candidate cj.
Whenever candidate E T is selected, the voters pay for this candidate. Voter pays (c(c) dollars for and in return, she gets utillity (c(c). Thus, the price-per-utiliy she pays equals Ps(c) pr(el/u.(e). MES works in way that all voters from who pay for e obtain the same price-per-utile for all i,j E S and C' we have that Pi(c) Py(c). Further, this sitce-pe-utiiltyy equals at most cost(e//us()), independently of whether any voters from \ S pay for or not (if no voters from N \ pays for c, then the price-per-utilie equals exactly cost(c//n((e):
ratio, i.e.
Ees (c(c) Pe(c)
px(c) Pc(c) (c)c)
2 (c)
Pa(c) (c(c) JES
1j(c) = EjEsPylo Ejes Uy(c) S
cost(c)
(c(c)
Ejes (y(c)
(s(c)
Since (c(c) z a(c) for each i E S and c E T, the price-per-utility for c E T equals at most costc)//ssja(c). Now, consider the voter who in the first possible iteration uses more than 1/n dollars For this voter, call her i, let us consider the function f defined as follows. For each value x, the function returns the price that i needs pay to achieve the utility We make this function continuous, by assuming that the candidates are divisible. That is, the voter pays p for her first paid candidate with utility uz (c), then f(wx(o)/2)= f/2, f( ((wx())/s) r/s, and on. The key observation that the function f is convex. This is because MES selects the candidates in increasing order of price-per-utee peruulltt-.ilt... This function depicted below.
pr(e2) [
pi(c) [
pi(e)) [
(,(c))
u,(c)
u,(o2)
Engr a(c)
We are interested in the value S(Eee (c))). This value would be maximized the fragments the function with the lowest slope were the shortest. However, we know that the part of the function that corresponds (c(c) must be length at least equal to uc(c) 2 acc). Thus:
cost(c) (c) [Sla(c)
cost
cost((T
f Σ a()) OETT
< Σ a(c) p:(c) S Σ a(c)
<
S
[S|
OET
CET
OET
Now, consider the first moment when uses more than 1/n dollars. Until this time moment, MES behaves exactly in the same way as if the voters from had their initial budgets set to 1/n (this follows from how we chose i). Further, we know that in this moment, if we chose candidate that would be chosen if the voters had unrestricted budgets, then the utility of voter i would be greater than >eer (c). This gives a contradiction, and completes the proof.
Theorem 1 establishes the Method of Equal Shares as a prime candidate for voting under a budget constraint, showing that satisfies a demanding fairness property. This makes it the first known rule
'The only case when there is no such voter is when every candidate E C with us > 0 has already been elected before. But then the utility of from the elected outcome clearly least Eeer us ua(c) 2 Eeer a(c).

---

that can give such strong proportionality guarantees in the model with additive utilities and arbitrary costs. In the literature on the special case of approval-based committee elections, another rule has received much attention: Proportional Approval Voting (PAV). Let us briefly recall the definition of this rule.
Definition 6 (Proportional Approval Voting (PAV)), For an approval-baser election, PAV selects a feasible outcome maximizing EiEN H(]A(i) WI), where H(r) = Ej= 1/j is the rth harmonic number.
This rule satisfies EJR when assuming unit costs [Aziz et al., 2017]. But without unit costs, PAV fails EJR. In fact, Example shows that, for each r 2 0, PAV does not even satisfy EJR up to projects.
Example 1. Fix a constant r E N (r 2 2), and consider the following approval based profile:
p
voters:
{ai, 02 ,,,,...,,7 ar. {bi .2.bb,,.bb,1) b,).
voter:
The candidates d1, .2,..... Or cost 1/r dollars each; the candidates 01, b....., EJR requires that the one voter who approves candidates bj..... b, must approve at least candidates the outcome. However, PAV selects {a), 02, ..... ),), leaving the voter with nothing.
, by cost 1/1² dollars each.
In fact, in Appendix A, we prove that rule that globally maximizes an objective function voter utilities (like PAV) can satisfy proportionality. Further, in Appendix C we argue that another rule for proportional approval-based committee elections, Phragmén's 's rule, does not extend to the PB setting.
3.2 Approximating the Core
An important proportionality property that has been proposed for PB is the core [Aziz et al., 2017, Fain et al., 2018], an idea adapted from cooperative game theory.
Definition 7 (The Core), For an election (N, C, cost, fu) an outcome W in the core if for every S S N and T S C' with |S] 2 cost(T) there exists i S such that u; (W) 2 u; (T).
The core is a stronger guarantee than EJR. The core allows any group S to present an arbitrary T that they can afford, and guarantees that at least member i E S would prefer to stick with the core outcome W, so (:WW) 2 (T). EJR only guarantees that v;(W) 2 Exer mi (c). Thus, EJR only respects counter-rooposals T if they have broad agreement within the coalition S. This is arguably a reasonable restriction, since such coalitions can more easily coordinate "complain" against the selected W. Still, it would be nice give the stronger core guarantee. Unfortunately, there are elections where no outcome is in the core, even with unit costs.
Example 2. We have 6 voters and 6 candidates with unit costs, and A = 3. Utilities satisfy
u1 (c1) > un (c22 > 0, ua(ca) > (c(cs) >
u2(02) > (2(cs) > 0, ug(ca) > uy (c1) > 0: ug(cs) > us(co) > O,
uc(cs) > W6 (c4) 0,
and all other utilities are equal to O. Let W C C be any feasible outcome, W| < 3. Then either IW n {ci, C2, 03) < 1 or W n (ca, Cs Go) } < 1. Without loss of generality assume the former, and assume that C2 & W and C3 & W. Then S fez, os) and T = {ca} block W, since 2 S 2
cost(T) n 3 6 = 2 and both ug(cs) > uz (c2) 2 (2(W) and uy (cs)ss > ug(C1) 2 (W).
Notably, this example is not approval-basse based. It unknown whether the core is always non-empty for upproval-based elections (with or without the unit cost assumption).
In the committee context, Peters and Skowron [2020] showed that the Method of Equal Shares (MES) returns an outcome that never violates the core too badly. We can generalize this result to the general PB setting: MES provides multiplicative approximation the core."
Definition 8. For 2 say that outcome is in the a-core if for every S N and 7 C with [S] 2 cTs n. there exists E S and c e T such that u, (R(E) U (c)) 2 '.(T)
"This example is adapted from Fain al. [2018, Appendix CJ so as to satisfy the unit cost assumption. *Our approximation notion differs from one proposed by Fain et al. [2018] (which also involves an additive term) and proposed by Cheng al. [2019] and Jiang et al. [2020] which approximates the coalition size.
7

---

Theorem 2. Given an election E, let Umax be the highest utility voter can get from feasible outcome. Let Umin we denote the smallest, yet positive utility a voter can get from a feasible outcome:
Umax
max max KEN cost(W)
(W) and Umin
min min 21 W:)
NEN us wW))>>
Then the outcome selected by MES is always in the a-core for a = 4 log(2 Umax/ Umiun)
The bound of is asymptotically tight. All proofs omitted from the main text appear in Appendix D.
3.3 Other properties of the Method of Equal Shares
In Appendices B and C we discuss two other properties: priceability [Peters and Skowron, 2020, Peters et al., 2021] and exhaustiveness. Here, let us only discuss the latter one. Exhaustiveness requires that a voting rule spends its entire budget. Of course, due to the discrete model, we cannot guarantee that the rule will spend exactly dollar (i.e., the entire budget); however, we can require that additional project is fits within the budget.
Definition 9 (Exhaustiveness, Aziz et al., 8b). An election rule R is exhaustive if for each election instance E and each non-selected candidate & R(E) holds that cost (R(E) U {c}) 1.
Notably, the Method of Equal Shares fails to be exhaustive: even there is enough budget remaining to fund more projects, the rule may reach state when no project is p-affordable. In Appendix C we discuss few possible ways to make the rule exhaustive. We experimentally compare these modifications in Appendix H.
4 Greedy Cohesive Rule
In Section 3 we discussed the EJR axiom for the PB model, and saw that it is implemented by Method of Equal Shares. We will now propose strengthening of EJR, and show rule that satisfies the new strong property. Interestingly, even in the approval-based committe--llecton model our new property is substantially stronger than EJR, and hence this new rule provides the strongest known proportionality guarantees. On the other hand, compared to MES, is computationally expensive and arguably less natural.
4.1 Full Justified Representation (FJR)
Our new proportionality axiom strengthens EJR by weakening its requirement that groups must be cohesive. Thus, the new axiom guarantees representation to groups that are only partially cohesive. Definition 10 (Full Justified Representation (FJR)). We say that a group of voters S is weakly (8, -cocheiieee for 3 E R and T S C, if [S] > cost(T)
and (T)) 2 B for every voter i E S. A rule R satisfies full justified representation (FJR) if for each election instance and each weakly (8, -oohhssiee group of voters S there exists a voter i E S such that u; (R(E)) 2 B.
In the approval- based committee-election model, FJR boils down the following requirement: Let S be a group of voters, and suppose that each member of S approves at least / candidates from some set T C' with [T] < f, and let |,|] > f/k n. Then at least one voter from S must have least representatives in the committee. It is clear that in the special case of B = f, we obtain Definition 2, hence FJR implies EJR. The same implication holds in the general PB model.
Proposition 2. FJR implies EJR in the general PB model.
It is easy to see that FJR is implied by the core property (cf. Definition 7). It is related to, but stronger than, some other relaxations of the core discussed by Peters and Skowron [2020, Section 5.2].
Previously known aggregation rules faill FJR (see Appendix E). Still, it turns out that FJR can always be satisfied: we present a (somewhat artificial) rule satisfying this strong notion of proportionality. Definition 11 (Greedy Cohesive Rule (GCR)). The Greedy Cohesive Rule (GCR) is defined sequen- tially as follows: we start with an empty outcome W 0. At each step. we search for weakly (8, T) ccoeesvve group S. If such a group exists, we find one where 3 2 is maximum, add all the
II Appendix F.1 we study additional properties of GCR. For those results it is useful, at this stage, to break ties in favor of smaller cost(1"). The proof of Theorem 3 does not depend on the way we break ties.

---

candidates from T to W, remove all voters in S from the election and repeat the search. If no such group exists, we stop and return W.
Let us first check that the Greedy Cohesive Rule always selects outcome that does not exceed the budget limit. Indeed, whenever the algorithm adds some set T to W, then by definition of weakly cohesive groups, we have [S] 2 cost(T") n, and hence it removes at least cost(T)) voters after this step. Thus, if GCR selects an outcome with total cost cost cost(W), ) then it must have removed at least cost(W) (W) voters during its execution. Hence cost(W) 1.
Theorem 3. The Greedy Cohesive Rule satisfies FJR.
In Appendix we further analyze GCR and discuss ways to extend its outcome when it is not exhaustive. We also present example where GCR selects counter-intuitive outcome.
5 Experiments
In this section we evaluate different voting rules on data from real-world participatory budgeting elections carried out in several major cities in Poland. The data we use is taken from Pabulib and was collected by [Stolicki et al., 2020]. The data is anonymized except for some basic demographic information which we do not use in our experiments.
We looked at election instances in which the projects were divided into several groups. One group consists of city-wide projects, and each other group consists of projects that were assigned a city district. Each voter was allowed to approve at most ten city-wide projects, and at most ten projects from her district. A part of the municipal budget was assigned city-wide projects and the other part was divided among the districts in proportion to their populations. Currently, the cities that we consider use a rule that selects projects greedily in order of approval score until the budget is exhausted.
In our experimental analysis we used types of voters' preferences:
Approval utilities: corresponding directly to the approval- upproval-ballots ballots from our PB data.
Cardinal utilities:
for each voter i and each project Cj we obtained the utility uz(cz) as follows. If i does not approve cj. we set uc(c)) = O. If approves Cj. we sample uz(c)) from the normal distribution centred at cost(cy). (We also tested similar models where u,(c)) was sampled from the uniform and exponential distributions, but those led qualitatively similar conclusions.)
We are interested in comparing the Method of Equal Shares, the greedy approval rule currently used for selecting projects, Phragmén's rule, and the sequential version of PAV (sPAV). (We have limited the experiments to polynomial-time algorithms,, since the instances are quite large.) Since Phragmén's s rule does not extend additive utilitics, we only use this rule for approval utilities.
In our analysis we evaluated the following metrics:
Total utility (UTIL.. The total utility of the voters from the selected set W: ΣIEN Eeew uz(c).
Distribution of projects (PROJ-DIS). For each election instance look at the projects selected from each district. We compute their cost and divide it by the fraction of the budget that is proportional to the population of the district. From those ratios we take variance.
Distribution of utilities (UTIL-DIS). For each election instance and each voter we compute her normalised utility from the set of selected projects W,, which we define as ΣIEN Eeew u;(c) divided by E.ew (c). We compute the variance of these values.
In Appendix H.1 we discuss in detail the obtained results and provide tables summarizing the measured metrics. Below we only briefly discuss the conclusions from the experimental evaluation.
First we checked whether the outcome that in fact selected by the cities is fair according to the kind of fairness criteria we have been studying. We found that in at least 59 out of 366 elections (16%), EJR was failed. In most cases, the failure was of the form that there who approved 0 of the selected projects but who approved an unelected project in common, and the
group of voters
'The data is publically available pabulib.org.

---

group was large enough to afford that project. This is even a failure of the PB version of the axiom
JR (Justified Representation).
Second, we compared three different strategies of making MES exhaustive. We observed substantial differences between different variants of MES. We conclude that MES gives lot of flexibility to a mechanism designer, as it often selects outcomes that do not spend all of the budget, while still satisfying strong fairness requirements like EJR. Depending on the specific objectives, mechanism designer can choose to complete this outcome using different strategies. Among the strategies we described in Appendix C, we observed that the outcomes produced by ExH2 are better from utilitarian perspective. It also divides the budget between different city districts in substantially fairer way than outcomes produced by ExH1. Therefore we suggest ExH2 as the preferred method.
In our third experiment we compared MES, Phragmén's rule, and PAV. We observed that for approval utilities the results returned by MES and Phragmén's 's rule comparably good, both in terms of the total utility obtained by the voters and in terms of proportionality measured as a distribution of projects and voters' utilities. On the other hand, if we take model with more fine-grained utilities, the difference between the two rules becomes apparent. This difference is unsurprising since Phragmén's 's rule does not take into account the more fine-grained information on utilities, but operates only on approval ballots. Yet, our results suggest that there is indeed a considerable advantage of using rules (like MES) that take into account the full information contained in cardinal additive utilities. We conclude that MES performs as well as Phragmén's 's rule for approval ballots and outperforms it when more fine- fine-graine grained information on voters' utilities are available. Somewhat surprisingly, we show that the sequential variant of PAV produces highly disproportional outcomes compared to Phragmén's 's rule and MES. Altogether, our experiments confirm our theoretical results and suggest that the Method of Equal Shares outperforms the other two rules in terms of proportionality and/or efficiency.
6 Conclusion
In this paper, we have formulated two axioms, EJR and FJR, that capture the idea of proportionality in the participatory budgeting (PB) model. We have argued that none of the prominent committee elec- tion rules extend to the PB model so that it would satisfy even much weaker forms of proportionality. We have designed simple and natural rule for the PB model, the Method of Equal Shares (MES). It satisfies EJR and other proportionality-elatee properties, and it is computable in polynomial time. The stronger of our two properties, FJR, is also satisfiable, albeit by different and arguably less natural voting rule. It is an interesting open question whether there exists a natural voting rule that satisfies FJR and shares other desirable properties of MES.
There are numerous results which are not included in the main text. Specifically, in Appendices B and C we discuss other properties of MES, and in Appendix F provide more detailed analysis of GCR. In Appendix G we explain that our rules can be directly applied to a model where voters have ordinal preferences, that is, when they rank the candidates from the most to the least preferred one. Notably, in the ordinal model MES satisfies the axiom of proportionality for solid coalitions, which is perhaps the strongest known axiom of proportionality for ordinal preferences.
Many cities run PB by dividing the overall budget between districts and running separate elections in each district. In particular, this is true in the Polish cities that provide our experimental election data. We claimed in the introduction that this practice of separate elections leads to inferior outcomes. We designed final experiment to study this question. Our results show visible advantage of using global rules such as MES over separate district elections. For example, MES always produces outcomes with more equal distribution of voter utility, and in most cases also provides higher total utility in comparison to the rules that are in actual use in the elections we examined.
Acknowledgments
Grzegorz Pierezyński and Piotr Skowron were supported by Poland's National Science Center grant UMO-20 MM002019/35/BBB. 2019/35///ST6/022155
10

---

References
H. Aziz and B. Lec. The expanding approvals rule: improving proportional representation and monotonicity. Social Choice and Welfare, 54(1):1-45, 2020.
H. Aziz and N. Shah. Participatory budgeting: Models and approaches. In Tamás Rudas and Gábor Péli, editors, Pathways Between Social Science and Computational Social Science: Theories, Methods, and Interpretations. Springer, 2020.
H. Aziz, M. Brill, V. Conitzer, Elkind, R. Freeman, and T. Walsh. Justified representation in approval-based committee voting. Social Choice and Welfare, 48(2):461-485, 2017.
H. Aziz, E. Elkind, S. Huang, M. Lackner, L. Sánchez-Femnnndzz, and Skowron. On the complexity of extended and proportional justified representation. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI-2018), pages 902-909, 2018a.
H. Aziz, B. Lee, and N. Talmon. Proportionally representative participatory budgeting: Axioms and algorithms. In Proceedings of the 16th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-2017), pages 23-31, 2018b.
G. Benade, S. Nath, A. D. Procaccia, and N. Shah. Preference elicitation for participatory budgeting. In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI-2017), pages 376-382, 2017.
Byrka, Skowron, and K. Sornat. Proportional approval voting, harmonic k-median, and negative association. In In proceedings of 45th International Colloquiun Automata, Languages, and Programming (ICALP-2018), pages 26:1-26 14, 2018.
Y. Cabannes. Participatory budgeting: significant contribution to participatory democracy. Environ- ment and Urbanization, 16(1):27-46, 2004.
Alfonso Cevallos and Alistair Stewart. A verifiably secure and proportional committee election rule. arXiv preprint arXiv:2004. /2900, 2020.
Y. Cheng, 7. Zaang, K. Munagala, and K. Wang. Group faimess in committee selection. In Proceedings of the 2019 ACM Conference on Economics and Computation, pages 263-279, 2019.
B. Fain, K. Munagala, and N. Shah. Fair allocation of indivisible public goods. In Proceedings of the 2018 ACM Conference on Economics and Computation, pages 575-592, 2018. Extended version atXiv:1805.0316
P. Faliszewski, J. Sawicki, R. Schaefer, and M. Smolka. Multiwinner voting in genetic algorithms for solving illposed global optimization problems. In Proceedings of the 19th International Conference on the Applications of Evolutionary Computation, pages 409-424, 2016.
Faliszewski, P. Skowron, A. Slinko, and N. Talmon. Multiwinner voting: A new challenge for social choice theory. In U. Endriss, editor, Trends in Computational Social Choice, pages 27-47.
Al Access, 2017.
P. Faliszewski, P. Skowron, S. Szufa, and N. Talmon. Proportional representation in elections: STV vs PAV. In Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-2019) pages 1946-1948, 2019.
Z. Jiang, K. Munagala, and K. Wang. Approximately stable committee selection. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 463-472, 2020.
M. Lackner and P. Skowron. Consistent approval-basee multi-winner rules. In Proceedings of the 19th ACM Conference Economics and Computation (EC-2018), pages 47-48, 2018.
M. Lackner and P. Skowron. Approval-based committee voting: Axioms, algorithms, and applications. Technical Report arXiv:2007.00 01199 [cs.GT] arXiv.org, 2020.

---

D. Peters and P. Skowron, Proportionality and the limits of welfarism. In Proceedings of the 2020 ACM Conference on Economics and Computation, pages 793-794, 2020. Extended version arXiv:1911.1174..
D. Peters, G. Pierczynski. N. Shah, and P. Skowron. Market-based explanations of collective decisions. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI-2021), 2021.
L. Sänchez-Fernández, E. Elkind, M. Lackner, Fernández, J. A. Fisteus, Basanta Val, and P. Skowron. Proportional justified representation. In Proceedings of the 31 AAAI Conference Artificial Intelligence (AAAI-2017), pages 670-676, 2017.
P. Skowron. Proportionality degree of multiwinner rules. Technical Report arXiv: 181008899 [cs.GT], arXiv.org, 2018.
Skowron, P. Faliszewski, and Lang- Finding a collective set of items: From proportional multirepresentation to group recommendation. Artificial Intelligence, 241:191-216, 2016.
P. Skowron, M. Lackner, M. Brill, D. Peters, and E. Elkind. Proportional rankings. In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI-2017), pages 409-415, 2017.
Dariusz Stolicki, Stanistaw Szufa, and Nimrod Talmon. Pabulib: participatory budgeting library. arXiv preprint arXiv:2012.06539, 2020.
N. Talmon and P. Faliszewski. A framework for approval-basee budgeting methods. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI-2019), pages 2181-2188, 2019.
Thiele. Om flerfoldsvalg. Oversigt over det Kongelige Danske Videnskabernes Selskabs Forhandlinger, pages 415-441. 1895.
N. Tideman and D. Richardson. Better voting methods through technology: The refinement- manageability trade-off in the Single Transferable Vote. Public Choice, 103(1-2):13-33) 2000.
D. Woodall. Properties of preferential election rules. Voting Matters, 3:Paper 4, 1994.
12


Reviews:
[{"review_id": "vHRopevXDJ6", "reviewer": "Reviewer_yC2K", "summary": "This paper studies the proportional participatory budgeting model, where the projects have arbitrary costs and the voters have additive utilities. In this classic model of PB, the paper studies fairness concept and explore whether existing rules satisfy certain fairness guarantee. Most of the results in this paper are based on approval-based committee elections and some concepts are slightly modified to fit the PB model.\n\n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The major contributions are:\n\n1. The paper extends Rule X to proportional participatory budgeting and the axiom named Extended Justified Representation (EJR), which is well-known in committee elections. It is easy to follow since they define it step by step by using several `intermediate’ definitions. They also show that Rule X satisfies EJR up to one project, a mild relaxation of EJR, and give a counterexample to show the PAV rule does not satisfy EJR. In addition, they show that Rule X satisfies the alpha-core with asymptotically tight bounds with respect to alpha and other properties like exhaustiveness.\n\n2. The paper proposes a strengthening concept of EJR, namely FJR, which guarantees representation to groups that are only partially cohesive. Although Rule X fails FJR, they also give a new rule named GCR, which satisfies FJR.\n\n3. The paper also do experiments comparing different variants of Rule X, Phragmén’s rule, and PAV and explore more about GCR.\n\nHere are some concerns about the paper.\n\n1. It looks like EJR and EJR up to one project is different in the general PB model. The authors only show that Rule X satisfies EJR up to one project, and PAV fails EJR. Does PAV fail EJR up to one project in the general PB model? It would be better to compare two rules with the same axiom in the general PB model. Is there any brief thinking about Rule X and EJR? \n\n2.It would be better to give the definition consistently, like definition 7 uses |S|>cost(T)*n but definition 8 uses \\sum_{c\\in T}cost(c)\\le |S|/n, both having the same meaning, but the former looks concise.\n\n3. The authors also propose FJR. Are there any scenarios where the rules that satisfy EJR are not good, so we need to use rules that satisfy FJR?\n\nThe authors addressed my questions.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "15 "}, "extra_text": {}}, {"review_id": "pwNEu4-iEMF", "reviewer": "Reviewer_T7rt", "summary": "The authors introduce two axioms for participatory budgeting, EJR and FJR, which are related to proportionality/fairness of PB mechanisms. Their main result shows that a proposed PB mechanism, \"Rule X\" satisfies EJR, and PAV (an incumbent mechanism), and its variants, do not. They briefly describe a rule (Greedy Cohesive) that satisfies FJR. They describe some experiments with real PB data, which are not included in the main paper.\n", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nThis paper presents some interesting and novel theoretical results in participatory budgeting. The exposition and notation is very clear, and authors take care to place their contributions within the existing literature. The introduction of EJR and FJR, and their adaptation of Rule X to a general PB setting, are both notable contributions.\n\nThe proof of their main theoretical results (Theorem 1 and Example 1) are easy to follow, and I appreciate that these are explicitly included included in the main paper. Some of the other theoretical contributions are less impactful, as they are left to the appendix (which I did not read). I am somewhat familiar with this literature -- and by no means an expert -- and these results look sound to me.\n\nOne negative point: there are several experiments with real PB data mentioned in the conclusion, which are not discussed or presented in the main paper. The extent of these experiments could almost constitute a separate paper, and they don't seem to add much to this paper since they are only mentioned in passing. As an applied researcher, I would have enjoyed reading about these experiments, and the implications of this theoretical work on real PB elections. However these experiments are not very important to the main (theoretical) contributions of this paper, so the overall paper is not diminished by their absence. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is very little discussion of the social impact of this work. The new proportionality axioms (EJR, FJR) are described in theoretical detail, though not from a practical perspective. (This seems to be the norm for most social choice and mechanism design literature.)\n\nThe authors certainly could have done more to discuss the practical pros and cons of their axioms and Rule X, perhaps with the discussion of some experiments using real data. Their one example of Circleville (Fig. 1) is nice, but only one example. In particular, it would be helpful if the authors expand on how the practical implications of EJR/FJR differ from those of the core (or other notions of fairness and efficiency in PB).\n", "review_text": "", "extra_scores": {"ethical_concerns": "Nothing in addition to my previous comments.\n", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "GgMJMEkZPFN", "reviewer": "Reviewer_tQCy", "summary": "The paper deals with a setting of participatory budgeting in which voters's preferences over projects are aggregated to fund a subset of the candidate projects with a limited budget. Based on justified representation in committee elections (a related setting without costs) a fairness concept is introduced as well as an aggregation rule (named Rule X) which is shown to satisfy the concept, while other commonly used rules fail to do so. Several variants, restrictions and extensions are discussed.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The topic of participatory budgeting and the suggested model are, as far as I know, in the scope of Neurips. The results and open questions significant and original as far as I can tell. The models and their theoretical analysis appear reasonable to me.\n\nTo my mind, related work should be elaborated on in the introduction. Some information is only provided later (see for example Section 3.1, middle and bottom of page 4), and should be mentioned early on. For instance, a reference for the concept justified respresentation is missing in the introduction (cf p. 1 and p. 3). \"Many works\" (l. 39) are referred to without literature pointers. The introductory example uses some general statements without reference such has \"most cities\" (l. 43), \"many cities\" (l. 55).\n\nI like the readability of the problem setting and the main part of the paper. Especially, the intuition and formality, and the comparison to the state of the art in committee elections and a permanent review of where the results can be settled in comparison was quite helpful. At some points defensive statements like \"our proofs are significantly different from...\" and \"This is yet another explanation why EJR is am important and well-justified axiom\" seemed a little misplaced and too meta-explanatory to me.\n\nConsidering Example 1 (p. 7), I get the impression that the condition is too strong to hold for a single voter. Even if that player forms a T-cohesive subset, it might make sense to relax the EJR property to large enough groups. What happens to rules like PAV for such a variant? \n\nProofs and additional details are often deferred to the appendix. From my point of view, the paper should be self-contained. Hence, it would be better to include at least sketches in the main paper and omit references to an appendix.\nSimilarly, Section 3.3 and the conclusion should be rewritten to present information differently.\nWithout the appendix many details are not comprehensible. For instance, I have not verified the proofs of Theorem 2 (Appendix D) and Theorem 3 (Appendix F). To my mind, the latter analysis of a new rule satisfying FJR is one of the main claims in the paper and should have more focus. Statements such as \"in Appendix F we discuss other important properties as well as some drawbacks of GCR\" (l.328) do not provide much valuable information in the main paper.\n\nAt the same time Figure 1 takes a lot of space for example details that are barely used. The picture is only referred to in one paragraph, and many variables are not even used.\n\nThe example of a \"bike trail along Example River\" (l. 66) additionally involves the issue of dependencies of projects which is not studied here. I wonder what can be said about such additional constraints.\n\n\nMinor details:\n\nl. 49: \"so we can assume...\" the following statement might work for the example but this is assumption cannot be implied (without reference from social sciences). It would be better to rephrase this less generalized.\n\nl. 102: Please rephrase \"that is\"; what follows is only an implication.\n\nl. 110: A Committee size |W| can also be less than k?\n\np.4: The notion mathcal{R}(E) is not defined before Definition 2, and can easily be added in the preliminaries.\n\np. 8: 3.3: Priceability is not defined at all.\n      4.1: The tie breaking procedure is mentioned to be needed in the context of priceability, which is not studied in the main paper. For the sake of self-containment, perhaps the information \"breaking ties in favor of smaller cost(T)\" can be written in Footnote 6, if not left out completely", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "-", "review_text": "", "extra_scores": {"ethical_concerns": "-", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "20"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is probably the strongest paper in my batch (as AC).  
Decision: Accept (Poster)