Strategic Cost Selection in Participatory Budgeting
Authors: Piotr Faliszewski
Łukasz Janeczko
Andrzej Kaczmarczyk
Grzegorz Lisowski
Piotr Skowron
Stanisław Szufa
Mateusz Szwagierczak
Venue: NeurIPS 2025 poster ()
Keywords: Participatory Budgeting
Social Choice
Game Theory
Equilibria
Primary area: theory

Abstract: We study strategic behavior of project proposers in the context of approval-based
participatory budgeting (PB). In our model we assume that the votes are fixed and
known and the proposers want to set as high project prices as possible, provided
that their projects get selected and the prices are not below the minimum costs of
their delivery. We study the existence of pure Nash equilibria (NE) in such games,
focusing on the AV/Cost, Phragmen, and Method of Equal Shares rules. We also
provide an experimental study of cost selection on real-life PB election data.

Strategic Cost Selection in Participatory Budgeting
Piotr Faliszewski AGH University Kraków, Poland fa falissn Taliszew@agh.edd edu.pp
Lukasz Janeczko
AGH University Kraków, Poland
janeczk@agh. edu.pl
Andrzej Kaczmarczyk University of Chicago Chicago, USA akaazzmarcczkkiicccccoo....
Grzegorz Lisowski
University of Groningen Groningen, The Netherlands g.a. www.wssssieeee..e maa.iswwsiirrgg.n
Piotr Skowron
Stanislaw Szufa
University of Warsaw Warsaw, Poland
CNRS, Université Paris Dauphine-PSL. Paris, France
p. p.skowron@mimu..ed pp1
S. www.ufaagaallll. com
Mateusz Szwagierezak
AGH University
Kraków, Poland
matissz@sttudent.. www.:/deee.................
Abstract
We study strategic behavior of project proposers the context of approval-based participatory budgeting (PB). In our model we assume that the votes are fixed and known and the proposers want to set as high project prices as possible, provided that their projects get selected and the prices are not below the minimum costs of their delivery. We study the existence of pure Nash equilibria (NE) in such games, focusing on the AV/Cost, Phragmén, and Method of Equal Shares rules. We also provide an experimental study of cost selection on real-life election data.
1 Introduction
Consider a city that implements participatory budgeting (PB) [Cabannes, 2004; Goel et al., 2019; Rey and Maly, 2023]. The city council allocates fixed amount of funds for the initiative and invites citizens to submit project proposals, for which the funding decisions will be made through voting. One natural question that the proposers face how much money should they realistically request. is tempting to propose expensive projects, as higher costs are typically associated with better quality and broader scope, but overly expensive projects risk rejection due to a limited budget.
Indeed, evidence suggests that the costs of the projects are often set strategically. For example, in 10% of participatory budgeting elections held in the city of Wroclaw, Poland, all project propos- als had costs equal to the maximum allowed amount (see the Pabulib database [Faliszewski et al., 2023]) in the corresponding instance. Moreover, in 85% of these elections, more than half of the proposals were priced at the maximum value. A similar phenomenon, less pronounced, also oc- curs in other cities. For instance, 25% of Pabulib PB instances approximately half of the projects have costs reaching at least 90% of the maximum allowed value in the corresponding instance. In another 50% of these instances, more than 30% of the projects are priced or above 50% of the
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

allowed maximum. This pattern is unlikely to be coincidental and it seems implausible that the implementation costs of different projects would naturally converge to such similar values. Instead, this suggests that projects are prepared strategically, with costs deliberately set as high as possible within the given constraints and perceived chances of selection.
Cost-selection strategies are likely influenced by the voting rules used. If the rule prioritizes the number of votes a project receives, proposers might feel encouraged submit more expensive pro- posals. This happens, e.g., if the city uses the BasicAV rule (also known as GreedyAV [Boehmer et al., 2023] or GreedCost [Rey and Maly, 2023]) which greedily selects those projects that are ap- proved by the largest numbers of voters (provided they still fit in the remaining budget). Conversely, the city were to use a proportional rule, such as the Method of Equal Shares (MES) [Peters and Skowron, 2020; Peters er al., 2021] or Phragmén [Brill et al., 2017; Los et al., 2022], then each proposer would have to analyze how the other ones might act and choose the costs accordingly.
For example, in recent instances of participatory budgeting in Wieliczka-where the BasicAV rule was used and the maximum project cost was set to half of the budget-exactly two projects were winners, each with the highest allowed cost. However, when in 2023 Wieliczka used MES in their experimental "Green Million" PB election, there were 30 winning projects, with costs distributed much more uniformly over the range of the allowed values (the maximum allowed project cost was 10% of the budget, so if the proposers acted as previously, there would be 10 winning projects; for details of the election, see https://quullsarrs.neeeeee miiirooooss//illooooimmiiono milion/). While this is anecdotal evidence, shows that voting rules do affect the structure of PB elections.
Our goal is to analyze this ghme-the nature of project cost selection under various participatory budgeting rules. Studying strategic cost selection is also natural direction in market analysis and is present, e.g., in the context of the Pooeeling-Dowrr model; see the overview of Eiselt [201 IJ. Notably, our work is different from that of Aziz et al. [2023], who consider how voters pool their funds; see also the work of Wagner and Meir [2023].
The Game We analyze the following scenario. The sets of projects and voters are fixed and each voter indicates which projects he or she approves (this information is common knowledge, an assumption we discuss later on). Each project is controlled by a different proposer choosing its cost so that is as high as possible, while ensuring that the project is selected. However, each project also has certain delivery cost-i.e. the lowest cost under which it can be reasonably implemented- and the proposers prefer costs that are at least as high. Note that we view the notion of a project broadly: Choosing a lower cost means proposing a smaller-scale project, and choosing a higher cost means submitting a more comprehensive one (but addressing the same general need). Importantly, whether voter approves project or not, does not depend on its cost; this strategy of the voters is often called threshold approval voting [Benadè er al., 2020; Fairstein et al., 2023]. The projects are chosen according to a given rule, such as BasicAV, AV/Cost, Phragmén, or MES (see Section 2 for details). We analyze whether thus defined games- where the project proposers are the players- have pure Nash equilibria and, if so, what costs are reported under these equilibria.
While our games present simplified view of reality due to abstracting away from excessive com- plexities, they lead to identifying certain phenomena and explaining behavior that we see in data. Consequently, our model lays the foundations and sets expectations for more sophisticated scenar- ios. Natural extensions will become apparent after we explain our assumptions and their limitations:
Votes are common knowledge. As we use classic Nash equilibrium analysis, need the ability to evaluate players' utilities for all possible strategy profiles, which essentially means that the votes are common knowledge. While this is a standard assumption in the analysis of Nash equilibria, in practice, neither the precise identities of the voters nor their votes are known to project proposers when submitting their projects. Yet, proposers often estimate potential support, e.g., using insights from previous PB editions. Hence, despite its seemingly strong assumptions, game theory offers valuable insight into strategic aspects of cost selection.
Project costs do not affect approvals. We assume that voters' approvals do not depend on project costs. Although it is simplification, is supported by several observations. First, data shows that costly projects are frequent, suggesting common belief that high prices do not deter vot- ers. Second, approving projects based on their quality and ignoring the costs often suggested as superior strategy for utility-oriented voters [Benadè et al., 2020; Fairstein et al., 2023].
2

---

Third, there is evidence that taking project costs into account, e.g., performing the value-for- money analysis, is cognitively expensive [Fairstein et al., 2023].
While relaxing our assumptions would give a more general class of games, we start with a clean, simple model, in order to obtain a baseline. That said, we complement our discussion by allowing the voters to have individual ranges of costs under which they approve each project. and we argue why we believe that such model leads to less useful conclusions (see Section 6).
Our Contributions. We study the existence of pure Nash equilibria in our games, under various PB rules and a number of restrictions on their structure. Importantly, we find that MES with cost utilities always admits NEs with the costs of the projects bounded proportionally to their expected support, whereas BasicAV has NEs where a single project takes the whole budget. In contrast, AV/Cost, Phragmén, and MES with approval utilities may fail to have any NEs at all. The existence of an NE for a rule suggests that it might naturally incentivize project proposers to gravitate towards it, whereas the non-existence indicates increased challenges in reasoning about the costs, leading to less predictable behaviour.
Further, our theoretical tools enable the experimental analysis of NEs in real-life scenarios. We conduct such an analysis based on the Pabulib dataset [Faliszewski et al., 2023]. We find that Phragmén and MES based on approval utilities are very different from MES with cost utilities. The former two rules promote cheaper projects, and the latter selects fewer and more expensive ones.
Our model aligns well with the patterns observed in real elections, such as those in Wroclaw and Wieliczka. Similarly, it provides insight into why most cities using BasicAV impose upper bounds on allowed project costs. Interestingly, the city of Šwiecie, Poland that transitioned from BasicAV to MES in 2023, dropped such upper bounds. This shows that the city officials have an intuitive understanding of the strategic incentives arising under different voting rules.
2 Preliminaries
Participatory Budgeting. We define a PB instance (or, a PB election) as a tuple E = (P, V. B, cost), where p= {pi...-, Pm is a set of projects, V = (Ul,...,Uo, vn is set of vol- ers, B E R2, is the available budget, and cost: - RR, is a function specifying the cost of each project. Each voter en casts a nonempty approval ballot A(u;) C P. containing the set of projects that he or she approves (see, e.g., the work of Fairstein et al. [2023] for a discussion of other ballot formats). Note that voter may approve projects whose total cost exceeds the available budget. We often refer to the voters and their approval ballots as either an approval profile or a preference profile. We extend the A(-) notation so that for a project pt, A(p;) is the set of voters that approve pa. Then, [A(p:)] is the approval score of pt. For each project ps. we assume that [A(p)) 2 1. Given a subset of projects P', we let cost (P') Ep'eP' co')
Each PB instance comes with tie- breabing order > over the projects, used by the PB rules to resolve internal ties. While tic-breaking can notably influence voting [Obraztsova and Elkind, 2011; I; Obraztsova al., 2011 and PB elections [Boehmer et al., 2023], especially in case of smaller instances [Janeczko and Faliszewski, 2023], we do not expect many ties in PB (ties are very rare in Pabulib data; see also the work of Xia [2021] | for argument regarding large ordinal elections).
Participatory Budgeting Rules. A PB rule is a function f that for a PB instance E outputs a set f(E) of projects with total cost not exceeding the budget. We refer to the projects f(E) as winning (or selected, or funded). Note that our rules are resolute, that is, their outcomes are unique. We focus on the following ones, denoting by E = (P, B, cost) the instance we consider and assuming > to be the tie- bebakkkking order:
BasicAV. It starts with W- = 0 and considers all the projects in the order of their nonincreasing approval scores (with ties broken using >), putting a considered project p into W cosl(W {p}) < B. Finally, it outputs W.
AV/Cost. For each project p, its approval-to-cos ratio is cost)) AV/Cost acts like BasicAV, considering the projects in the nonincreasing order of these ratios and breaking ties using >
Phragmén [Brill et al., 2017; Los et al., 2022]. Phragmén starts with W = 0 and fills it in as fol- lows. Initially, the voters have empty virtual bank accounts, but they continuously earn money
3

---

at the rate of one unit per unit of time. When there is a project p such that the voters who approve it have least cpst(p) units of money all together and the project is within the budget (i.e., (o U {p)) < B), these voters purchase it: is included in W, the bank accounts of voters in A(p) are reset to zero, and p is removed from consideration. If cost U {p)) > B, then p is removed without being included in W. If several projects could be purchased simul- taneously, we pick one using the tie-breaking order. The rule stops and outputs W when all projects are removed from consideration.
Method of Equal Shares (MES-Cost) [Peters et al. 2020; 2021]. First, each voter receives 2//V amount of money. Then we let W = 0 and proceed iteratively: Within each iteration, for each project p not in W we compute its affordability coefficient ap as the smallest number such that the following holds (b; is the money that voter on currently has):
Ev,EA(p) min(b,, ap- cost(p)) = cost(p).
(1)
If no such value exists (i.e., the voters approving p cannot afford it) then we set 0 00. If Ap = oo for all & W. then we terminate and output W. Otherwise, we choose p' o W with the lowest affordability coefficient (using tie-breaking, if needed), include p' in W, and take Op'' cost(p'') money from each voter in A(p') (or all the remaining funds, if the voter had less than Og'' cost(p')). )) Due to the use of cost in Eq. (1), the rule is called MES with cost utilities. MES with Approval Utilities (MES-Apr). It works like MES-Cost, but with Eq. (1) replaced by Enve min(h, ap) = cost(p)- While in MES-Cost the affordability coefficients are be- tween 0 and under MES-Apr they can be as large as B.
Remark 2.1. Both variants of MES may output a set of projects that can be extended without exceeding the budget. In our experiments we use Phragmén completion: When MES variant finishes, we extend its output by running Phragmén with voters' bank accounts initiated with their then-current amounts of money. This defines the MES-Cost/PP and MES-Apr/Ph rules.
Many authors also study other PB rules (see, e.g., the works of Goel al. [2019]: Talmon and Faliszewski [2019]; Sreedurga et al. [2022]); for an overview, see the survey of Rey and Maly [2023] and the book of Lackner and Skowron [2023] (which regards multiwinner elections, where projects have unit costs). BasicAV is commonly used in practice, MES-Cost also was recently used by several cities (see https://equalshares..c net); the other rules are mostly studied theoretically.
Structured Preferences. In a plurality profile, each voter approves exactly one project, whereas in party-list profile the projects are grouped into "parties" and each voter approves all projects from single party. Importantly, plurality profiles form special case of party-list preferences. Some cities require plurality profiles (e.g.. Wroclaw, Poland; see the respective datasets in Pabulib); party-list ones are mostly interesting theoretically.
Definition 2.1. Consider sel of projects P and a voter collection V with approval ballots over P. We say that these voters have: (1) plurality preferences, if A(v;)] = for each voter us (2) party-list preferences, if either A(v;) = A(u,) or A(e,) n A(u,) = @ for each two voters is and vz.
For a party-list profile, let party(p) (p) denote the set of projects approved by these voters that approve.. p.
3 Participatory Budgeting Cost Games
We now define our main object of study, participatory budgeting cost games (PB games). Formally, a PB game is tuple (P, V. B, d). where is a set of projects, V is a collection of voters with approval preferences over the projects from P, B is the available budget, and d: P + R. is a function that associates each project with its minimal delivery cost (see the description of the payoffs in the next paragraph). We assume that for each project pi, d(px) < B. In this game, the projects are the players and each of them needs to report its cost. That is, a strategy profile is tuple (C1, (ci,...,,C,, C,), with a cost e; E R4 for each project ps, which will be used in a PB election. As is standard, by (c_1, d') we mean a strategy profile identical to a except that project p; reports cost c' We often write c(p,) to denote the cost reported by p. under profile c, and we use strategy profiles as cost functions in PB instances.
Let us fix PB rule f and PB game G = (P. V. B, d). For strategy profile the associated PB instance is E(c) = (P. V, B, c) and the payoff of each project p; E is:
(c) C. d(p.) if f(E(c)),
and 2,(c) = 0 otherwise.

---

Table 1: Our NE existence results. By "d = 0" and "arb. d' we mean zero and arbitrary delivery costs.
ballots
Plurality arh. d
Purty-List arh.
Unrestricted arb
0
d ==
Legend
BasicAV
NE guaranteed for an arbitrary tie-breaking
AV/Cost
NE always exists for some tie-breaking NE for all tie-breaking orders
PC-2
TA
7:42
Thn BA
P::2
Phragmén
D
?
conjecture
Ccc
result holds also for each project p have d(p)) S ap(p). where ap the cor- responding upproval-propottoonll strategy profile
APs
Thxx
4.0
4.
Thrs 412
MES-CCst
Tho
Thas
Thx.49
Thc.49
The
The interpretation is as follows: Each project p has a minimum delivery cost d(p), which is the lowest price under which it can be implemented. Yet, with more money the project can be better, the proposer prefers this, and the utilities implement this preference. In particular, the proposers do not receive funds equal to the utility values. Instead, to compute utility values, we deduct minimum delivery costs. We often consider the special case of zero delivery costs."
For PB rule I and PB game G = (P, V, B, d), we say that a strategy profile for this game is Nush equilibrium under I (is an f-NE).
no project has a profitable deviation. That is, it cannot benefit by reporting different cost than that from the f-NE (assuming other costs change).
Definition 3.1. For PB rule f and PB game G = (P, V. B.d), we say that strategy profile for this game a Nash equilibrium under f (is an f-NE) for every project ps P and every cost d' E R2 it holds that uc(c)= 2 ua w,(c.i,d).
Example 3.1. Take AV/Cost and PB game with projects pı, P2, voters U1,..., Us, budget 10, and {ri, 12) and A(p2) U4, 15), so this is plurality profile. Strategy profile c where c(p1) = 4 and c(p2) = 6 is an NE. Indeed, according to AV/Cost, A(pa)l/e(pz))
zero delivery costs. We have A(pı)
1/2, and both projects are selected under any tie-breaking order. If either of the projects reports a lower cost, it gets selected, but its utility decreases. it reports a higher cost, is not selected and its utility drops to zero.
under these costs pı and p2 are tied as [A(p) (A(p))/e((ss)
We sometimes use approval -o-eeeierr---ootttt (A/D) tie-breaking orders, which favor projects with larger ratios of their approvals to delivery costs. So, > A/D if projects with zero delivery costs are ranked highest, while A(p.)/a(p)) > A(ps)/d(ps) implies pt > Pj if d(p:) d(p,) > 0. As some cost ratios, there may be several different A/D orders.
projects may have equal approval-to-delive
Remark 3.1. In our games, a proposer receives the same utility of zero when his or her project is not funded and when it is funded with exactly its delivery cost. One could distinguish these cases by using extended utility function ui, such that:
(c(c)- = =c(p)) - d(p.)= + I[c(p)) 2 d(pi)] if E (E(())
and <<(c)= = otherwise,
where 1 [x] is 1 x holds and 0 otherwise. We prefer our formulation as it is simpler and captures the intuition that only projects more costly than their delivery costs are worth implementing. That said, all our NE-(non jexiteeeee results still hold for the extended utility functions (for the nonexistence results this is automatic and for the existence ones, see Appendix A).
4 Existence of Equilibria
Our theoretical results, summarized in Table 1, focus the existence of NEs in PB games. We mostly show that either: (1) There always is an equilibrium, for any tie-breaking order; (2) There always is equilibrium for some A/D tie-breaking order; (3) There is PB game with no equilib- rium for any tie- die-breaking order. When such statements are difficult to show, we seek instances with no equilibria for some tie-breaking order. Such an observation is weaker than a result of type (3),
1 'This assumption well justified. First, based on the design of the game, project proposers are incentivized to submit costly projects, so the risk of costs approaching zero is minimal. Second, assigning fixed delivery costs introduces an unrealistic hard constraint, as proposers often possess the flexibility to adjust project scope and influence the costs. Modeling delivery costs zero thus provides clean representation of this fiexibility.
5

---

is incomparable to a result of type (2), and implies that a result of type (1) does not exist. Pragmat- ically, it is most important to know whether a result of type (1) holds or not in given setting; the other types of results indicate various levels of bad news regarding the existence of Nash equilibria.
We interested in strategy profiles that are proportional in some way, and, in particular, in which the costs of the projects are justifiable by the level of support that they have. A detailed discussion of fairness in PB is, for example, in the works of Brill et al. [2023] and Maly et al. [2023], well as the works defining MES and Phragmén). Below, we define a basic type of such a profile, where project costs are proportional to the numbers of approvals they get.
Definition 4.1 Sooproval-Prooottoonn
Strategy Profile). Consider PB game with P (pi.p...... ................................ ... ). We say that strategy profile ap is approval-proportional if for each project p it holds that ap(p) B |A())// Eyep |A(y')).
Under plurality preferences ap is natural for rules that aim to achieve proportionality. For more involved settings, other profiles may be more appropriate (see, e.g., MES-Cost and Theorem 4.9).
4.1 BasicAV
For BasicAV, there an equilibrium where the most popular project requests the full budget amount. Proposition 4.1. For each PB game and each internal tie-breaking order > there is a BasicAV-NE where the project with most approvals (best with respect to >> reports cost B.
In fact, the most popular project reports cost (and is selected) under every BasicAV-NE. Hence, Proposition 4.1 indicates that proposers of projects receiving many approvals have an incentive to overstate their costs, whereas proposers of less popular projects have an incentive to bundle them together, to garner votes (indeed, this is what seems to happen in Wieliczka PB elections held using BasicAV; recall Section 1). Consequently, BasicAV equilibria our games are disproportional, highlighting known deficiencies of this rule.
4.2 AV/Cost
Some shortcomings of BasicAV are remedied by AV/Cost, for which the approval-proportinn strat- egy is an equilibrium. To show this, we note that in an NE, if the delivery costs are limited, all projects are funded, using the whole budget. It follows that then ap is the only equilibrium profile. Proposition 4.2. for each project p we have d(p) S ap(p). then ap is the only AV /cost-NE.
If (some of) the delivery costs are higher than the costs implied by the approval-proportionn strategy, then the situation becomes more complicated and it is no longer true that an NE exist for all internal tie-breaking orders. Yet, there always is a breakin order yielding an NE.
Example 4.3. Take PB game (P, V, B, d) with plurality ballots, where P [PI,P2), |A(pi)
[A(p2)] = 5. B = 10, d(pi) = 0, d(pz) = 6, and the tie-breaking order is p2 > p1- Assume that is an AV/Cost-NE. Consider two cases: (1) If c(p2) 2 then either (a) c(pi) Z c(p2). where is better for pı to report a cost lower than c(p2) (otherwise P2 is selected before p1 and there is no budget left for p1), or (b) c(pi) < c(p2) and it is better for pl increase its cost (keeping it below c(p2)). (2) If c(p2) < 6, then either P2 is chosen and it prefers to report cost 6 (otherwise its payoff c(p2) - d(p2) < 0), or p2 is not selected. meaning that c(p1) < c(p2) and it is better for pı to increase its cost (keeping it below c(p2)).
Nevertheless, if we change the tie-breaking order so that pı > p2, then (6, 6) is an equilibrium, where only Pı is funded: Both projects would decrease their payoff by lowering costs and they would not benefit by increasing their costs (p1 would no longer be selected, and p2 's payoff would not change).
Theorem 4.4. For each PB game and A/D tie-breaking order there is an AV/Cosi-NE computable in polynomial time.
Proof sketch. We propose an algorithm that computes the claimed profile e iterations. Starting from the situation where each project reports its delivery cost, in each iteration it selects group of projects that "underreport" their costs compared to their support. Then, it increases their reported costs as much as possible, with the projects remaining funded. Finally, if the funded projects after the

---

update do not use up the whole budget, the procedure is repeated for the remaining projects whose prices have not been increased so far. These projects, albeit worse regarding the delivery-cost-to- support ratio, can still benefit from the increase. In the end, the procedure outputs an equilibrium profile. The somewhat involved proof is in the appendix.
We conclude by noting that even for plurality preferences the costs of projects selected in an equi- librium can be arbitrarily far from using the entire budget.
Proposition 4.5. For each integer > 1 there is a PB game with plurality preferences and AV/Cost- NE profile e with the total cost of projects funded under AV/Cost at most B/7y
4.3 Phragmén
For plurality ballots, AV/Cost and Phragmén always output the same projects. Thus, the next corol- lary translates results from the previous section to the case of Phragmén.
Corollary 4.6. For each PB game with plurality ballots, (a) if d(p) I ap(p) for all p E P. then ap is the only Phragmén-NE for every tie bie-brekking order; (b) otherwise, for each A/D tie- breakkkknng order there is Phragmén-NE (and there are PB games and tie- feebreaking orders with Phragmén- NE).
Naturally, Proposition 4.5 also holds for Phragmén, so there are games with equilibria for which Phragmén funds projects whose total cost is an arbitrarily small fraction of the budget. Next, we focus on more involved preference profiles. On the positive side, for party-list ballots (and zero delivery costs) we always have unique equilibria, for every tie-breaking order: Each project p reports a cost proportional to the number of its approvals, divided by the size of its party.
Proposition 4.7. For every PB game with party-list ballots and zero delivery costs, there is the A(p)
unique Phragmén-NE where for every project p we have c(p) = B [V pPrrpgggll]]
Unfortunately, party-list preferences with zero delivery costs are where the good news end. Indeed, we find that there are small instances without equilibria.
Proposition 4.8. There is a PB game with six projects and six voters and zero delivery costs, for which there is no Phragmén-NE irrespective of the tie-breaking order.
4.4 Method of Equal Shares
The mechanics of MES might seem similar to those of Phragmén, as these rules follow the approach in which voters buy the projects they approve. However, contrary to Phragmén, in both types of MES voters have limited amounts of budget to spend. So, the approval scores of projects give upper-bounds on the maximum costs that the projects might report. I.e., as each voter gets an equal share of the budget, projects that cost more than the total budget of their supporters cannot be funded.
In case of MES-Cost, this translates to our most positive result: For each PB game there always is an, essentially unique, MES-Cost-NE, regardless of the tie-breaking order and the delivery costs. Furthermore, this NE can be computed in polynomial time and if all the projects have sufficiently low delivery costs and sufficiently high support, then it uses up the whole budget (even though, in general, MES is not exhaustive). Together with its proportionality features, this reinforces the position of MES-Cos as a very attractive PB rule.
Theorem 4.9. For each PB game, there is a polynomial-ti computable MES-Cost-NE profile c, unique up to the actions of the projects not selected by MES- -CSSt under c.
Proof sketch. Let p be the project with the largest number of approvals (and preferred in the tie- breaking order, if there are several such projects). We observe that p can always request the full amount of money that its voters have at the beginning of the execution of MES-Cost; the rule would fund p irrespective of the costs of the other projects. Thus, p reports this amount and funded (if the amount is below its delivery cost, p reports the delivery cost and is not funded). The project has no reason to report less, and reporting more would cause it to not be funded. Then, we disregard all the voters that approve it and repeat the reasoning for the remaining projects and voters.
D
7

---

Table 2: PB instances analyzed in experiments.
Instance
[P]
V
Budget
Avg. num. of approvals per ballot
Wesola
29
1182
1011 000 PLN
7.87
Kleine Wereld
52
426
250 000 EUR
11.93
Perhaps surprisingly, for MES-Apr the results are much less positive. While there always MES-Apr-NE for plurality ballots, in general there are small games with zero delivery costs that have no MES-Apr-NE irrespective of the tie-breaking order used.
Theorem 4.10. For each PB game with plurality ballots, there is a polynomial -imee time computable MES-Apr-NE.
Proposition 4.11. There are games with zero delivery costs, for which there no MES-Apr-NE regardless of the tie-breaking order, even if we have only 4 projects and 16 votes.
In case of party-list ballots, existence of equilibria depends on delivery costs and tie-brea
Theorem 4.12. Every PB game with party-list ballots and an A/D tie tie-breaking order has MES-Apr-NE computable in polynomial-tine preferences, nonzero delivery costs and non-A/D tie tie-breaking that do not have MES-Apr-NE.
There are examples of PB games with party-list
For zero delivery costs every tie- tie-breaking order is A/D, so the above theorem shows that PB games with party-list preferences and zero delivery costs always have MES-Apr-NE. We conclude by noting a surprising difference between MES-Apr and Phragmén, presented in the following theorem. Theorem 4.13. In some instances symmetric projects (w.rt. their supporters) submit different costs in MEr-Ap,-NE, but identical ones in Phragmén-NE.
5 Experiments
We move on to the experimental analysis of our games for real-life PB instances from Pabulib [Fal- iszewski ef al., 2023]. We focus on two instances, one held in 2022 in Wesola (a district of Warsaw, Poland) and one held in 2019 in Kleine Wereld (a part of the Noord District of Amsterdam, The Netherlands). A few details regarding these instances lyzed many other instances from Pabulib, some of which we show in Appendix C. While all of them lead to similar conclusions, the instances chose particularly illustrative. Our code is publicly available at https://github.. hwtptddwwwooo/oooeeocoeeee PRAGGeGR-RRRAAMMAAAttrtttteeee cost- ceos--selection-.- in- P
available in Table 2. We have also ana-
We perform two experiments. First, we take PB instance with the original project costs and com- pute proposers' best responses. Second, we seek equilibiria for our instances. We omit plots for MES-Apr/Ph, as they resemble those for Phragmén (see Appendix C).
5.1 Winning and Losing Margins
Take PB instance E and PB rule f. Intuitively, for each project p its best response br(p) is the highest cost such that if we use it instead of cost(p), then p is (still) funded under f. We define it as the supremum of the set of costs under which p is funded. Then, if p is winning in E under we let its wimning margin be br(p)- br(p)_cos((p), and if it is losing we let its losing margin be cost(p) br())-
In Figure we show the winning and losing margins (and, hence, the best responses) for all the projects from our two PB instances. For BasicAV, we observe very high winning margins for the projects with the largest numbers of approvals, and close-to-zero best responses for the remaining ones (this phenomenon is particularly visible Kleine Wereld). In principle, under BasicAV project receives few votes even making it cheap will not make it funded, unless is cheap that selected simply because nothing else could fit within the budget left. For AV/Cost the best responses roughly correspond to the numbers of approvals each project got; the same, roughly, holds for Phragmén and MES- Mpr-App/Ph. The margins for MES-Cost//e Cost/Ph are different, with several most-approved projects having much higher winning margins than the rest.
The main general observation is that unless project received relatively few approvals, then typically its proposers could have reported a much higher cost. In practice, this means that project proposers
8

---

BasicAV
Phragmén
AV/Cost
MES-Cosi/Ph
Cost millions)
0.25
0.15
0.1
0.8
530
422
100
Cost (in millions)
0.05
0.03
0.02
0.01
$ @
222
Winning margin
Losing marpie
Number of votes
Figure 1: Kleine Wereld with one of 250k EUR at the bottom. Projects ordered by decreasing approval scores (on the z-axis) are represented by bars. Tacks and crosses show, respectively, the original and best response costs.
Winning and losing margins in real-life Wesola with the budget of 011k PLN the top and
should rather focus on designing convincing, attractive projects, and not on minimizing their costs, as the latter is not as likely to be decisive. Yet, of course, there are projects where lowering their costs could have gotten them funded; see also the recent work of Boehmer et al. [2024].
5.2 Finding Equilibria Using Dynamics
In the second experiment, our goal was to compute (approximate) equilibria for our two instances. While for BasicAV, AV/Cost, and MES-Cost/Phi we could compute the equilibria using results from the previous section, this would not be possible for Phragmén and MES-Apr/Ph, Instead, simu- late certain dynamics. (For the rules where we can compute equilibria directly, our dynamics give nearly identical results; for Phragmén and MES-Apr/Ph there may be NE, but the results suggest that the profiles that we find are, at least, close to being equilibria). We assumed zero delivery costs. In Appendix D we show results for delivery costs equal to 80% of the originally submitted ones, obtaining similar conclusions.
Given PB instance, our dynamics go as follows. First, each proposer reports the same cost as was originally chosen for his or her project. Then, in each iteration, one of them, selected uniformly at random, either slightly increases or decreases his her project's cost. Specifically, the proposer chooses a number z between 0 and cost/ / 10 uniformly at random (where cost is the current project's s cost) and if their project was losing in the previous iteration, then the proposer decreases its cost by x, and it was winning, then he or she increases its cost by x (but if this action would have caused the project to lose, then the proposer does not change the project's 's cost). We expect to converge to an NE, if one exists, after running sufficiently many iterations.
In Figure 2 we present the results of the dynamics, that is, the obtained strategy profiles, after 10 000 iterations. Under BasicAV, as expected, all the budget goes to the project with the most votes. Under AV/Cost, every project ends up with cost proportional to its support. Like in the previous exper- iment, Phragmén, and MES-Apr/Ph produce similar results, while those of MES-Cost/hh remain different. For BasicAV, AV/Cost. and MES-Ca MES-Cost/Ph most of the projects "reached" the costs pre- dicted by the equilibrium. (However, note that not all of our dynamics ended up in perfect equilibria within 10 000 iterations as, e.g., some projects are not winning).
The main conclusion from this experiment (supported also by simulations for other PB instances; see Appendix C) is that under AV/Cost, Phragmén, and MES-Apr/Ph the proposers are incentivized to use costs that mostly reflect the number of approvals they receive. Under MES-Cost/Ph, most strongly supported projects, well as those that are supported by many voters who do not approve other, more popular projects, can request much higher costs. Consequently, an NE Mos-CosstPhh funds fewer, more expensive projects than AV/Cost, Phragmén, and MES-Apr/Ph. We view this

---

BasicAV
Phragmén
AV/Cost
MES-Cost/Ph
Cost (in millions)
0.25
IM TM/
0.2
0.05
GUG$ER
$
Cost (in millions)
0.04
0.00
0.02
4
+
3 1
362
155
122
100
(Originally winning project
Equilibcium congurable))
Number of votes
Strategy profiles after 10000 iterations of our dynamics for the instances Wesola with the budget of 11 PI.N at the top and Kleine Wereld with one 250k EUR the bottom.. Projects ordered by decreasing approval scores (z-axis). Final projects' costs shown by bars; the original costs shown as dashed lines. Red and green bars indicate, respectively, losing and winning projects; brighter parts are the increases over the original cost.
Figure 2:
observation as one of the more important take-home messages from our work, which can be used to favor
in practice (while funding some cheap projects is important, funding only such projects logistically challenging for cities that then need to coordinate their implementation).
What If Votes Depended on Costs?
So far, have assumed that the voters' approvals are independent of the project costs. We justified this view in the introduction, and here we further argue that not only is it reasonable, but also es- sential. Specifically, we demonstrate that if the approvals depended on the costs, then our equilibria guarantees would collapse, albeit due to such dynamics among voters and project proposers that are not particularly realistic. This reinforces the careful design of our basic model, which allows for both accurate analysis and meaningful insights into real-world phenomena.
We extend basic model cost-interval PB games, where each voter approves project p exactly if its cost falls within an interval that v views as acceptable for p (specified in the game description). This approach is inspired by the model of Sreedurga [2023].
Theorem 6.1. For f E (BasicAV, AV/Cost, Phragmén, MES-Apr, MES-Cost). there is cost- interval PB game with no delivery costs that has no f-NE.
We find the basic model more insightful because cost-interval PB games allow for very unrealistic icenarios-sude as having voters that approve building a bike path for at most $25,000, when others do only if it costs above $75,000. In practice, such disparities Theorem 6.1 exploits exactly such scenarios and the ability to shift between received support by varying the costs (even under plurality preferences). While cost-interval PB games capture more nuanced voters' behaviors, they also allow for vastly unrealistic cases that distort the results.
unlikely, but the proof of
7 Summary and Future Work
We have introduced a game-theoretic framework capturing strategic cost selection of projects in participatory budgeting scenarios, studied the existence of equilibira in our games, and used them to analyze two real-life PB instances. We believe to have set the groundwork for future studies, which may include establishing the complexity of deciding if equilibria exist in our games and studying more involved settings, emerging from relaxing our basic assumptions. In particular, is compelling to verify what extent observations hold in more realistic models.
10

---

Acknowledgments
This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 101002854). Piotr Skowron was supported by the European Union (ERC. PRO-DEMOCRATIC, 101076570). Views and opinions expressed are however those of the authors only and do not necessarily reflect those of European Union or the European Research Council. Neither the European Union nor the grant- ing authority be held responsible for them. Grzegorz Lisowski acknowledges support by the European Union under the Horizon Europe project Perycles (Participatory Democracy that Scales). This research has been supported by the French government under the management of Agence Na- tionale de la Recherche as part of the France 2030 program, reference ANR-23-IACLL-000.
Funded by the European Union
erc
References
H. Aziz, S. Gujar, M. Padala, M. Suzuki, and J. Vollen. Coordinating monetary contributions in participatory budgeting. In Proceedings of SAGT-2023, pages 142-160, 2023.
G. Benadè, Nath, A. D. Procaccia, and N. Shah. Preference elicitation for participatory budgeting. Management Science, 67(5):2813-222) 2020.
N. Boehmer, Faliszewski, Janeczko, and A. Kaczmarezyk. Robustness of participatory budget- ing outcomes: Complexity and experiments. In Proceedings of SAGT-2023, 2023.
N. Boehmer, Faliszewski, L. Janeczko, D. Peters, G. Pierczyúski, Schierreich, P. Skowron, and S. Szufa. Evaluation of project performance in participatory budgeting. In Proceedings of IJCAI-2024, pages 2678-2686, 2024.
M. Brill, R. Freeman, S. Janson, and M. Lackner. Phragmén's voting methods and justified repre- sentation. In Proceedings of AAAI-2017, pages 406-413, 2017.
M. Brill, M. Lackner, J. Maly, and J. Peters. Proportionality in approval-based participatory budget- ing. In Proceedings of AAAI-2023, pages
2023.
Y. Cabannes. Participatory budgeting: A significant contribution to participatory democracy, Envi- ronment and Urbanization, 16(1):27-46, 2004.
Horst Eiselt. Equilibria in competitive location models. Foundations of location analysis, pages 139-162, 2011.
R. Fairstein, G. Benadè, and K. Gal. Participatory budgeting designs for the real world. Proceed- ings of AAAI-2023, pages 5633-5640 2023.
Faliszewski, J. Flis, D. Peters, G. Pierezyúski. P. Skowron, D. Stolicki. S. Szufa, and N. Talmon. Participatory budgeting; Data, tools and analysis. In Proceedings of IJCAI-2023, pages 2667- 2674, 2023.
A. Goel, A. Krishnaswamy, S. Sakshuwong, and T. Aitamurto. Knapsack voting for participatory budgeting. ACM Transactions on Economics and Computation, 7(2):1-27, 2019.
L. Janeczko and P. Faliszewski. Ties in multiwinner approval voting. Proceedings of IJCAI-2023, pages 2765-2773, 2023.
M. Lackner and Skowron. Multi Winner Voting with Approval Preferences. Springer Briefs in Intelligent Systems. Springer, 2023.
M. Los, Christoff, and D. Grossi. Proportional budget allocations: Towards systematization, In Proceedings of IJCAI-2022, pages 398-404, 2022.

---

J. Maly, S. Rey, U. Endriss, and M. Lackner. Fairness in participatory budgeting via equality of resources. In Proceedings of AAMAS- pages 2031-2039, 2023.
Obraztsova and E. Elkind. the complexity of voting manipulation under randomized tie- breaking. In Proceedings of IJCAI-2011, pages 319-324, July 2011.
S. Obraztsova, E. Elkind, and N. Hazon. Ties matter: Complexity of voting manipulation revisited. In Proceedings of A,MAS-201, pages 71-78, May 2011.
D. Peters and P. Skowron. Proportionality and the limits of welfarism. In Proceedings of EC-2020, pages 793-794, 2020.
D. Peters, G. Pierezyúski, and P. Skowron. Proportional participatory budgeting with additive utili- ties. In Proceedings of NeurlPS-2022 pages 12726-12737, 2021.
S. Rey and J. Maly. The (computational) social choice take indivisible participatory budgeting. Technical Report arXiv.2303.00621 arXiv, 2023.
G. Sreedurga, M. Bhardwaj, and Y. Narahari. Maxmin participatory budgeting. In Proceedings of I/CAI-2022, pages 489 489,499,.00 2022.
G. Sreedurga. Indivisible participatory budgeting with multiple degrees of sophistication of projects. In Proceedings of AAMAS-2023, pages 2694-2696, 2023.
N. Talmon and P. Faliszewski. A framework for approval pppsev based budgeting methods. In Proceedings
of AAAI-2019, pages 2181-2188, 2019.
Wagner and R. Meir. Strategy-proof budgeting via veg-like mechanism. In Proceedings of SAGT-2023, volume 14238, pages 401-418, 2023.
L. Xia. How likely large elections tied? In Proceedings of EC-2021, pages 884 885, 2021.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract clearly describes the main goals of the paper and the results mentioned in the Introduction reflect both theoretical and experimental contribution of the manuscript.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals motivation as long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
The manuscript contains a detailed description of the modeling assumptions that were chosen, as well as the restriction that they entail. Furthermore, the theoretical questions that were not answered in the submission are clearly marked.
Justification:
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-tex system might be used reliably provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
13

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: The main manuscript contains proof sketches for the main claims, and full proofs of all results are provided in supplementary material.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple-
mented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
The details needed for reproducing the main results of the paper provided.
Guidelines:
The answer NA means that the paper does not include experiments.
the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results way produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
14

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The real-life data used in the experiments is publicly available. The code will publicly available upon acceptance.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (httpss//nips.ccppbbicc guidds/CodeSSbbissioooooof
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [NA]
Justification: Neural networks are not used in this paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Values of standard deviation have been provided in the supplementary mate- rial, where useful for the interpretation of the results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
15

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (c.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state The authors should prefer- ably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: None of the experiments required extensive computational resources. All the experiments can be feasibly computed on a standard MacBook Air with MI chip.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't t make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://eeuuppppcppppbpilbceelcd
Answer: [Yes]
Justification: Yes, fulfill the anonymity requirement well other parts of the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
The manuscript primarily theory-focus, and does not provide direct practi- cal implications.
Guidelines:
16

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitiga- tion strategics (c.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
There is no high risk of misuse of the proposed data.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by re- quiring that users adhere usage guidelines or restrictions access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
The only external data comes from Pabulib, and it is properly credited in the references.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (c.g.. CC-BY 4.0) should be included for each asset.
17

---

For scraped data from a particular source (e.g., website), the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms of use the pack- age should be provided. For popular datasets, paperswitheode. ceeersswtthooeecccdaaaaaatte com/datasets has
rated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
Justification:
The paper does not introduce any new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Question:
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, cura- tion, or other labor should paid at least the minimum wage the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
18

---

Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: LLMs were not involved in the core method development.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (ttps///eeutts..ccommmeeeeee///) for what should or should not be described.
19

---

A Games with Preference for Funding
A PB game with preference for funding (PB/P4F game) is standard PB game where instead of our standard utility functions we use the extended ones, as defined in Remark 3.1:
u c(p:) d(p)) + 1 (e(xs) 2 d(p:)) if pi f(E(c)),
otherwise,
where 1 [x] is 1 if x holds and 0 otherwise.
All our NE-(non)existence results for PB games translate to PB/P4F games. Indeed, if a PB game does not admint an equilibrium then neither does its P4F variant (every profitable deviation a PB game is also profitable in the corresponding P4F game). The other direction is more involved as there are games that have equilibria in our model but do not have them in the P4F variant (see Exam- ple A.1). However, if a PB game has NE where all projects that report values above their delivery costs are funded, then it remains an NE in the corresponding P4F game (a profitable deviation for the P4F game would also be profitable in the original one). All our existence results produce equilibria that satisfy this condition.
Example A.1. Consider three projects PL, P2. Ps, each supported by one distinct voter. with delivery costs d1 = 1, d2 = d3 = O, tie-breaking order P1 > P2 > P3 and budget B = 2. As we prove in the appendix, the corresponding PB game admits Phragmén-NE c (2, 1) but the corresponding P4F PB game has no NEs under Phragmén.
Below we argue why the statement from the above example indeed holds. Let us denote the PB game from the example as G and the P4F PB game as G". Using G and G', we show now that in some cases PB games admit Phragmén-NE, while PB/P4F games (based on the same input) do not.
First, observe that (2, 1) is Phragmén-NE in PB games. To see that, suppose that it is not and consider a project p; and a cost &4 for which us (c-., 4)) > uz(c). If p; is p2 or ps. we notice that p; is selected under but not under (c_i, c)), for each de >> C;- So, neither p2 nor pa can improve its utility. For p; = pı, we notice that it is not funded under e and that it can only be funded c S 1. But then us ((c(,, c)) S 0. follows that e is Phragmén-NE in PB games.
Second, we show that G' does not admit a Phragmén-NE. For contradiction, suppose that G' admits a Phragmén-NE, say c, for PB/P4F games. As warm up, note that at least one project has to be chosen in E(c), as otherwise each project benefits from lowering their cost to B = 2.
Further, consider the case that in projects have the same cost c. If c < 1, then, following the tie- breaking order, P1 is funded and gets negative utility. Hence, by increasing its cost to c' > B > c, pi becomes not funded and increases its utility. Also, if e 2 1, then P3 is not funded, and as d3 = 0, can benefit from decreasing its cost.
Now, suppose that in c projects do not have the same costs. Let ci > 1. Then, if c2 2 c1 or C3 2 C1 then some project that not funded would benefit from lowering its cost. For a complementary case of C2 < C1 and < C1, we further consider two subcases. If C2 + C3 < 2, then one of p2 and pa would benefit from increasing their cost. Alternatively, 02 + C3 2 This implies that c > 1 and
that 2 1 or C3 2 1. In this case p1 would benefit, in a PB/P4F game, from choosing ci = 1 and becoming selected.
Finally, if c1 < 1, then it benefits from increasing its cost if it is funded under e. Notice further that if it would not be funded, then C2 1 and c3 < 1, and both of these costs are lower than e1- It follows that one of them can increase its utility by increasing its cost.
As our case distinction is exhaustive, we know that there is no Phragmén-No for G'. Consequently, we proved our claim about the equilibria in games G and G¹.
B Missing Proofs
B.1 Proof of Proposition 4.1
Proof. Take a PB game and strategy profile e as described in the statement, and let p the project such that c(p) = B. If project other than p increases its cost, it still is not selected so this is not
20

---

beneficial move. If decreases its cost then its utility drops, and if it increases its cost then it is not funded. In either case, its utility decreases. So, i BasicAV-NE.
B.2 Proof of Proposition 4.2
In our proof we first use the following proposition.
Proposition B.1. Take a PB game and the corresponding strategy profile ap. If dfp(p S app(p) for each project p. then if a profile is an AV/Cost-NE for this game, then (1) Eper c(p) -B, and (2) AV/Cost funds all the projects.
Proof. Let the notation be as in the statement of the proposition. In the beginning we observe that if Epep c(p) < B, then AV/Cost selects all the projects. Hence, the project considered last benefits by reporting a higher cost (so that the sum of the reported costs is B). Thus such a strategy profile is not an equilibrium.
Next, let us assume that EPE c(p) > B. Let Pwon and Plost be sets of projects that, respectively, are and are not funded. By our assumption, we know that Piost must be nonempty, and we also note that Pwon must be nonempty. Naturally, Σ,ep,... c(p) I B. For each two projects pa and pj in Pwon. it must be the case that [A(r:)/c(pp)) = (A(ps)//((p)) For example, if we had [A(r))/c(pp)) > [4(r))//((p)) then AV/Cost would consider P: prior Pj and, consequently, it would be beneficial for ps to increase its reported cost by small-enough amount so that it would still be considered (and selected) prior Pj- This would contradict the assumption that is an equilibrium. Next, since Epep ap(p) = B, there must be some project p' in Pwon such that c(p') > ap(p') 2 d(p') (otherwise, if each project p' E Pwon reported at most ap(p'). then any project E Plost would be selected after reducing its cost to ap(p), so could not have been NE). Further, by definition of the approval-proportionn value and, so, for every project q E Plost it holds that [A(o)//ap(a) = [A(r') |A(r') /ap(p') > (A6)')/a())) )- This means that every project q E Plost can improve its utility by reporting cost ap(g) and being selected. This contradicts the assumption that c is an equilibrium.
profile, for every project p E P. we have that [A(r)//p(()) is the same
Thus it must be the case that Epep c(p) = B, which implies that AV/Cost selects all projects.
Proof of Proposition 4.2. Consider PB game (P,V, B, such that for every E P it is true that d(p) S ap(p).
We argue that strategy e = ap is a AV/Cost-NE. Note that the sum of the reported costs in e is exactly B and all projects are funded. Hence, for each player, decreasing the cost leads to a utility loss. Hence, a profitable deviation could only be through increasing the reported cost. Towards contradiction, let us fix some player p: E ap and assume that reporting cost of c leads to a better payoff. This means that p; is funded in the modified election E' = (P, V. B, (c_,, 4)), that is, P: E AV /e//ssss Additionally, since by Proposition B.1 we know that Σ Cj B, it immediately follows that e; + EjepPh CG > B > EjEppRo Cy. It is also the case that for each j E [P|, (M(33)//e IP/33//3 > MA(R)//2. Hence, in particular, in the run of AV/cost for E', all projects are considered before Ps. Since all of these project are selected, by the time the procedure starts considering pt. the remaining budget is smaller than c/. so p. & AV /cost(E") (E"); a contradiction. Note that because all projects that are funded are always considered by the procedure in the same time, the result is independent of the tie-breaking order >
We now argue that every strategy profile other than ap is not a AV /cost-NE. To this end, we take such a profile с and assume towards contradiction that it is a /C/cost-NE. Observe that since j ap, there exist two distinct projects p; and Pj such that A(px) * |A6p))l/e, Hence one of the projects is considered earlier than the other; we assume without loss of generality that ps is considered before Pj. Notably, as is (by our assumption) AV /cost-NE, by Proposition B.1, we know that (ps. } / S AV /cost(c). This implies, however, that p: can report a slightly higher price e; and still be selected by AV /c//ost thus obtaining better payoff. Formally, there exists a of > e resulting in the profile (c(, c-i) in which (A(P)lf/)) < [I(())l//3 So, p: is (still) considered by AV /cost before ej and the deviation is small enough (that is, e4 c4- < G,) to guarantee that p; E AV cost(((c.,, c.). So, is not AV AV/cost /cosst-EE; a contradiction. Again, due to Proposition B.
21

---

Data: set P (pr, (p1.P2.... P2,....-Pry of projects with the delivery costs function d, set of voters with their ballots, budget B, A/D tie-breaking >
Result: profile с that is a AV//ost-ND under tie-breaking >.
1: B B
remaining budget If initial strategy
2: c t
d(
CD If let t(p). for each P E P. be d(P)/A(e)
I/ note that is nondecreasing w.r.. values
If posxx denotes the top ith project of order > restricted to X C
3:
Po <- (- P: & B*}
prospective projects A are there projects to consider? # P' belper variable guardian "fake" value guardian "fake" value
4:
while Pp o do
5:
P' t Pp
6:
((posp.(0)) t inf
7:
((posp<(PP') + 1)) +- inf
8:
maximum integer & $ P such that
p(posp (x)) Eiso-1 A(posp (i)) S B* < (p 1)) Eise+1 A(posp:(1)
9:
T maximum I d(posp (R++ (k++1))/ (gpes)
such that x ΣiE[R] A A(posp) (i)) S B
10:
for = 1 to k do
If updatte and B
11:
c(pos po (i)) + T A (pos (i))
12:
B* - B* c(possp. (i))
Pp - Pp (possp (i))
14:
end for
i: < |P' then
16:
P. - P, {pospp (k 1)}
end if
18: Pp < E Pp: c(p) < B
19:
end while
20:
return
Algorithm Finding a Nash equilibrium for AV/cost.
in each Nash equilibrium, all projects are selected to be funded. Hence, our proof works for every possible tie-breaking.
B.3 Proof of Theorem 4.4
Proof. Our Algorithm computes the claimed AV/Cost-NE.
Let us fix a PB game = (P, V, B, d) and some corresponding A/D tic-breaking >, as specified in the theorem statement. We first introduce helpful notation and discuss > in more detail. Then, proceed with presenting a high-level description of Algorithm that finds the claimed AV/Cost-NE, Eventually,
which refer conclude with proving Claim itself.
prove the correctness of the algorithm using Claim 1 and
Recall that by definition > orders the projects p; nonincreasingly according to approval-to-delivey. cost ratios (A(p.)l/a(p.). Crucially, > is always compatible with the order in which AV/Cost considers the projects assuming they report their delivery costs, that is, where for all pt E P, c(p.) d(pt)- In what follows, for each set of projects X C P. each P. E X, and the corresponding suborder > x of write x (p:) to denote the position of pt in x Analogously, for some natural num- ber æ S |X], we denote by top (z) the set top z projects according to >x
Algorithm 1 constructs the AV/Cost с iteratively, starting from strategy cp in which each project reports its delivery cost (Line 2). In each iteration of the while loop, the algorithm selects group of projects that "underreport" their costs compared to the support that they get. As the next step, the algorithm increases the reported costs of these projects in strategy AV/Cost as much as possible ensuring that the projects remain funded. If the funded projects after this update do not exhaust the budget, the procedure repeated for the remaining projects, whose prices have not been increased so far. Such projects, albeit worse regarding the delivery-cost-to-uuppe ratio, can still benefit from
22

---

the increase. The algorithm outputs с if one of the updates step lead to the situation in which the whole budget used when there is no more projects underreporting their costs.
In the following more detailed description of Algorithm 1, we use the notation as specified in the pseudocode and whenever the value I in iteration of the loop is smaller than Pll, we define p" posp + 1) (assuming the value of P' from the corresponding iteration). Central to Algorithm the while loop. Importantly, due our basic assumption on the delivery costs of the projects (i.e., that for each p E P. d(p) s B), initially set Pp is not empty (Line 3), so the while loop runs least once. Line 9 of the algorithm guarantees that in each iteration the loop sets the values of T and & to:
k: < P and = dir")/ d(p")/A(p)) or Σ
(S1)
k < P and T
|A(p))] B",
(S2)
Py (kk
k = PP and T
Σ
A(pp)] = B"
(S3)
(k)
The aforementioned case distinction is crucial for the following claim.
Claim 1. Right after executing Line 18 each iteration of the while loop of Algorithm 1, it jointly holds that:
1. all projects from topp (k) are funded under strategy profile and none of them has profitable deviation for c;
2. either k PP| or there exists a project p" = pos (k + 11 that is not funded and has no profitable deviation for profile c;
3. project from top from с only by strategies of projects in Pp in a way that, for each p E Pp. c'(p) 2 c(p));
(k) has profitable deviation for each strategy profile e' that differs
4. either = =IP' or the project p' = pospr(t (k + 1) has no profitable deviation for each strategy profile e' that differs from only strategies of projects in Pp such that, for each p E Pp. cp(p)= 2 c(p);
5. no project in P Pp has a profitable deviation in c.
Note that Algorithm ends when executing Line 18 makes P, empty. So, by Item 5 of Claim I the algorithm returns profile which is Nash equilibirum. Clearly, in each iteration k >> so least one element is removed from P. in every iteration of the loop. Consequently, the algorithm always ends and thus correct. To conclude the whole proof remains to show that Claim 1 indeed holds.
Proof of Claim 1. We provide an inductive argument over the iterations of the while loop of Al- gorithm 1. For the sake of the argument's simplicity, instead of thinking of AV/Cost considering projects in nonincreasing order of approval-to-com ratio, we say that considers projects in nonde- creasing order of cost-to-approval ratio. We note that these two interpretations are equivalent. We take the first iteration of the loop as the base case and subsequently show that Items
hold.
Item We first show that each p E top (k) is funded election F(c).. Let us denote as ((p) the ratio c(p)/ Due to Line and the following foreach loop. we know that every project in top (k) is tied to be considered by AV/Cost due to the same cost-to-approval ratio T. So, if = |. then all projects in P. P' are tied for consideration. Since, by Line 9 all project costs sum up to 3 = B, the claim holds. We follow assuming that lo < IP'|. In this case, Line 9 shows that p² has cost-to approval ratio t(p") 2 T. Recall that > orders projects nondecreasingly with respect to their cost-to- apprrovl ratio assuming Co and that differs from cu only in strategies topp- and all
of projects topp.. (k:). Hence, p² precedes c each project except of those projects in po (k) are considered before y" (the latter holds even in the case of (pp) = T due to >). Eventually, Line guarantees that the cost of all projects in top pr (k) does not exceed the budget. Knowing that, we show that project in top (k) has profitable deviation in To
23

---

prove it by contradiction, let us assume that some player p: topp-(kk has profitable deviation by reporting cost of > Cū the opposite case of cj < e; trivially does not yield payoft improvement for Pt. As a result, Px has to be funded in the corresponding election (((c_;, C)). In this election, Ps has cost-to-approval ratio 1' 4//M(D]] T. We further split our analysis into the three cases from Equations (S1) to (S3).
Assuming Equation (S1), project p" is also funded in election E", as it is considered before pz due to t' > T. Hence, the funded projects cost at least
T
E Py Est Ps7Pi
+11A)++(((()))) +TA
T.
E
AA(p))
(k+1)
However, due to Line 8, we know that B" contradiction with the fact that p, funded.
T T Etopp/ [A(p)). which gives the
Suppose Equation (S2) or Equation (S3) hold. Then, given our assumption that pj is funded, the total cost of funded projects is
T.
Σ
[A(p)) +1Appp) >
Py (1k) P:Pp;
T
Σ
AA(s)) B" B,
PyEtop
Here, the equality is due to the assumption of Equation (S2) or Equation (S3); which yields the sought contradiction.
Item 2. = |P'). then the statement trivially holds. Otherwise, let us consider p" in the light of Equation (S1). Due to Line 8, we have that
B <T
Σ
AA(s)]
(k+]))p(k+)))
Σ
I(A(p))) + d(p").
(AE)
Hence, since all projects in p.)).()) are funded, p" is not funded. Naturally, if p" reports cost bigger than d(p") it will not be funded more. whereas reporting cost lower than d(p') results in a worse payoff, which finishes the argument for, for Equation (SI). By the condition of Equa- tion (S2), it immediately holds that all projects top (k) use up the whole budget. As result, again, p" not funded and, analogously to the case Equation (S1), p" has no profitable deviation. We already observed that Item 2 trivially holds for l: PP|, which subsumes Equation (S3).
Items 3 and Observe that assuming strategy c, projects in P. are considered after all projects outside of Pp in election E(c). This is because order is compliant with the order of considering projects by AV/Cost and our modifications to the initial strategy profile do not change order of considering projects (note that we let modified projects be tied for consideration with cost- to-approval ratio T). Furthermore, note that Algorithm never decreases the reported costs of the projects and never considers the same project twice, the projects in P. will never be considered before the other ones as a result further modifications of c. So, no modification of the profile c that increases the costs for projects in P. can influence the decision made for projects in top, (k) or po (I + 1) (depending on whether < PP)), as the latter are considered by AV/Cost earlier than projects in Pp-
Item 5. Note that P\ P. consists only the following projects: (i) those removed the foreach loop, that is, loppr(k); (ii) p² if h: < PPI:: and (iii) those removed in Line 18. Regarding the first two groups, we have already shown that they not have profitable deviation for c. Let f be topp. (k) if k < IP'l or, otherwise, let be p". The last group Y consists of these projects p E P!
24

---

for which p > and whose d(p) > B". Hence, by >, these projects are considered after all projects in (k) However, projects in pop (k) are selected to be funded, which leaves exactly B* remaining budget. So there is not enough budget left to fund any project in Y, even if it reports its delivery cost. Hence, no project Y has a profitable deviation.
Thus, we have established the base case and we move on to the induction step. Consider æ' > and the x-th iteration of the while loop, assuming that the base case claims are met for the (a 15-18 1)- th iteration. Due to the assumptions for the (x - 1)-th iteration together with the fact that our algorithm never changes the order > in which AV/Cost considers projects and that it never considers the same project twice, we can ignore all projects processed in previous (z 1) iterations of the while loop. Clearly, the ignored projects will have no impact on the current loop iteration except for decreasing the value of the variable 8* representing the remaining budget. Consequently, the arguments for Items to 4 earry on without changes for the ath iteration of the while loop. The be the set of players
claim from Item 5, however, needs more attention. Let Q(x-1) = P PP p(=-1)
without profitable deviations after the (2 1)-th iteration of the loop. Note that P p(*-1) We denote by R the set of projects, that are removed from the initial state of Pp by Lines 13 and 18. That is, consists of all these projecst that-due to Items to and the argument for Item the base case-hasee
no profitable deviation in So, we have that Pp = P' \ R. We now consider the set Q = P Pp of the projects for which we need to show that they have no profitable deviation. Putting the bits together, we observe the following:
Q Pp Po= = (P \ [t)
P PI R) (P (PPR)
Since P n R = R. we obtained that Q = RU-UUQ ((=1) thus showing that the z-th iteration extends the set of project that do not have a profitable deviation with a collection of project that have no profitable deviation either. As result, we proved Item 5 for the r-th iteration.
Having proven Claim 1, we completed the argument for the correctness of Algorithm and Theo- rem 4.4.
B.4 Proof of Proposition 4.5
Proof. Take a natural 7 > and consider a PB game (P, V, B, d) where P= (PI, Ps). , B 10, d(pi) = d(p2) = 0, and d(ps) 10 27 The voters have plurality ballots such that [A(p))
We assume tie-breaking order P1 P2 P3- We claim that strategy profile such that c(P1) = c(p2) = 24 and c(ps) = 10 - 24 is a Phragmén-NE.
[A(p)) 1 and A(ps) 207
First, we see that if the projects reports costs as c then Phragmén selects P1 and p2. Indeed, we see that at time moment 2y the voters supporting each of the projects have exactly much money as is need to purchase them. Due tie-breaking, the singleton voters supporting P1 and p2 buy these projects and, then, there is not enough budget left for P3 and the rule finishes.
Second, we observe that no project can benefit by changing its strategy under Indeed, if either P1 or P2 decreased their cost, they would obtain lower payoff, and either of them increased their cost, Ps would be funded instead and the payoff of the project that increased its cost would drop to zero. If Ps decreased its cost then it would be selected, but its payoff would become negative (due to the delivery cost), and if it increased its cost then its payoff would remain zero Consequently, is Phragmén-NE.
Finally, we have c(pi) c(e2) 1/7, and as B- 10, this is less than B/7, This concludes the proof.
B.5 Proof of Proposition 4.7
Proof. Consider PB game G and the strategy profile as defined in the statement of the propo- sition. We claim that c a PNragmén-NE. First, we observe that under e Phragmén selects all the projects, so it is not beneficial for any of them to report lower cost. On the other hand, if some project p reports a higher cost, this project not selected by Phragmén. To see why this the case, consider some project p. Under c, the total cost of the projects in party(p) is B-IA(pl//vv). Since
25

---

each of the [A(p) voters supporting these projects earns one unit of money per one unit of time, altogether they earn this money in time B//V|. This value independent of p so, under c, the last project of each party is funded at the same time. Hence, if some project increased its price, it would be considered even later and, by that time, there would not be enough budget left. Hence, never beneficial to increase a cost and so, C is Phragmén-NE.
remains to show that C is the unique Phragmén-NE for our game. To this end, let c' be some arbitrary equilibrium for G. By Proposition B. we know that under c' the reported costs of all projects sum up to B and all projects are funded. Next, we observe that for each project p, all projects from (p) report the same cost. Indeed, if there were two projects, p' and p" E party(p), such that c' c'(p') c' (p"".. then would be beneficial for p' report a higher cost (but below c' (p("), so that Phragmén would still consider and fund it prior to p" (for which, then, there would not be enough budget left).
Finally, if there are two projects, p and q, such that party(p) F party(g), then, under c', the last project from pprty(p) and the last project from party(g) are selected by Phragmén at the same time. Indeed, if this were not the case, then it would be beneficial for the one selected earlier to report higher cost (but so that it still is selected at an earlier time than the other project).
Altogether, the only strategy profile that satisfies the properties described above is c as defined in the statement of the proposition.
B.6 Proof of Proposition 4.8
P2. p's and pa = p5 Similarly, the set of voters is V = V' V", where V ='=(orr u2,, J and V" {ur,, U2", 03") The approvals are as follows (see also Figure 3 for illustration):
Proof. Let our project set be = P' U P", where p'= =
1. p is approved by uy, 1/ is approved by uz, and plg is approved by all the voters in V
2. The approvals for the projects in p" are analogous, except that they are approved by the voters from V"
We set the delivery costs be zero for every project, and we set the budget B to be 1 (the exact value will be irrelevant we will operate on times when Phragmén reaches the costs of particular projects rather than on directly on these costs). We claim that under Phragmén there are no Nash equilibria for the thus defined PB game G (P,, (P,V B, d).
p
P2
//1
1/
1/1
1/3
0/2
1/3
1/2
Figure 3: Illustration the PB game from the proof of Proposition 4.8. The projects are depicted as boxes. Each voter approves those projects that are drawn directly above him or her (and are crossed by the dotted line).
For the sake of contradiction, let assume that there is Phragmén-NE for G and let it be ct. For each project p E P, let time(p) be the time moment (in the sense of the Phragmén rule) when the voters approving p would collect exactly c* (p) amount of money (assuming that neither of these voters spends it on any other projects in between; hence time(p) = c" (p)/1A(p)))) We make the following observations:
1. All projects in P are funded for the reported costs c* (if some project were not funded, would prefer to report small nonzero cost that would be at most equal to B and that would ensure that Phragmén considers it first).
2. It must be the case that lime(p)) time(pá). Indeed, if we had time(p() < &ime (ph) then it would be beneficial for pi to slightly increase its cost, but so that time(zh) would still be below p6g Then, irrespective in what order are the other projects funded, pi 's voter would collect enough money to purchase p before the ph 's voter would, and p would be
26

---

bought (since 2/2 would not be selected at this time yet, there would be enough budget left for this). This would contradict that c* an equilibrium. The case time(p') < time is symmetric.
3. It must be the case that time(pp) = time(pf) and, hence, also equal to time (p)). Indeed, if we had lime(p/)) < (ime(p]) - time(p)) then it would be beneficial for p/ report slightly higher cost, so that téme(p') would still be smaller than time(p1) = tpmm) yet ply cost would not have increased by more than the total costs of p1 and pzz Then P/1 would still be selected before pi and p/2 and there would be sufficient amound of budget left for it. This would contradict that c* is an equilibrium. On the other hand, if time(p)) > tyme(p') = (p() then it would be beneficial, e.g., for pi to report slightly higher cost, but ensuring that time(p() < time(p/). Indeed, if originally we have time(p') < táme(p'). then pi is funded before P/g by Phragmén. After the increase, pl would still be purchased before 2/3 and, thus, there would still be sufficient budget for it. This would contradict that c* is an equilibrium.
4. By reasoning analogous to the one given above, it must be the case that time(p") = time(p!) time(pg).
Given the above observations, we set:
time' time (p')) time (p/2) time(p'y) and
time" time(p")) time(p") time(p"))
Note that this implies that c* (p1) c² cp(p4) time', c* (pf") c² (p')) = time", c² (p() 3- 3ime,'', and c* (p²) = 3- time". We claim that time' = time". Indeed, let us consider what happens if time' < time" (the case where time" < time' symmetric). There are two cases two consider (the second case also splits into two).
Case A First, let us assume that least one of pl and p/ is preferred to p/g by the tie-breaking order (for the sake of specificity, let this be p¹). Then it is beneficial for p1 to slightly increase its cost. To why this is the case, let consider how Phragmén operates after this increase. At time time(pí) = time the voters have enough funds to purchase either pi or plz (and not enough to purchase p/z. who increased its cost). The rule selects p11 due tie-breaking. Consequently, voter I' pays for p/1 and his or her virtual bank account is reset to zero Voters 2' and 3' still have time' amount of money. The cost of pl is 3- time'. so voters in N' will have collected enough money for it after further 1/stime' amount of time. However, if pl2 increased its cost from time' to an amount a bit below 4/3 time' then its voter will have collected this amount earlier, and plz will be purchased before P/g. This contradicts the fact that c* is an equilibrium.
Case B' The second case is that pl is preferred by tie-breaking to both p1¹ and p/z- Then it is beneficial for pla to slightly increase its cost. Again, let us consider how Phragmén operates after such a change. If pg is selected prior to both pf and p²z then at time time" (after the purchase of pL) the voters have the following amounts of money:
1. Voter 3' has lime" amount of money and the remaining voters in N' have nonzero amounts of money (specifically, each of them has time" time', because they paid for p and ph at time time').
2. All the voters in V" have empty bank accounts.
Hence, only after another time" amount of time will the voters in N have enough money to pur- chase pf and pl. Yet, at this time the voters in N' would, altogether, have more than 4time". So, pl increased its cost to be between 3- time' and 4 time' (which is smaller than 4 time"), ), then p's would be funded before pf and phz and there would be sufficient amount of budget left for this.
Case B" On the other hand, if at least one of pl and p/a is preferred to pl by tie bre-bieg at time lime", then both y and py are funded at that time (because after one of them is selected due to tie- breaking, the voters in V" no longer have enough money to purchase P²z. but they do have enough for the other one among r" and y²)) Consequently, after p" and yy are purchased at time time". only projects p/z and pd are not selected yet and the voters have the following amounts of money:
27

---

1. Voter by has time" amount of money and the remaining voters in V have nonzero amounts of money (specifically, each of them has time" time', because they paid for pi and pl at time lime')
2. Voter Uyr has time" amount of money and the remaining voters in V have no money.
Since voters in V have, together, more money than those V", but voters from both groups (jointly) earn money at the same rate (as |V| IV",, if plJ increased its cost to be slightly below that of pk it will be funded before plg. Consequently, if c* is an equilibrium then we must have time' -tmme"
Finally, it suffices to show that the assumption time' = time" also leads to no equilibrium. W.l.o.g, we assume that pa precedes both pi and 112 in the tie-breaking order, and that 2/ precedes both pf and pl (if this were not the case, then the arguments given in Case A above would still show that c" is not an equilibrium). However, now we can see that, e.g.. it is beneficial for P/3 to slightly increase its cost. This follows by the same reasoning as given in Case B'. Hence, we have reached a contradiction. Consequently, under Phragmén there is no Nash equilibrium in our game.
B.7 Proof of Theorem 4.9
Proof. Let (P, V, d) be MES-Cost PB game.
We provide an iterative algorithm that computes c. In each iteration, the algorithm fixes selected values of c, drops the corresponding projects from further consideration and deletes the voters that have no budget left. The algorithm finishes when there is no more projects consider. Before laying out the details, let us recall that in MES-Cos HES-Cost, each voter gets the equal share of the budget and cannot spend on the projects more than their entitlement.
Our algorithm constructs the strategy c step by step maintaining the collection V' of voters to con- sider and the collection P' of projects to consider. The algorithm starts with setting V = V, P' P and proceeds as follows:
1. Remove from P' all projects Pt P' for which AA(p.) V'I B/IV| is lower than d(p:) or equal to zero and let their strategy be c(p,) d(p.).
2. For each project Pj E P let ag = a,= 1/::=//440 A/V' (due to Step I we avoid dividing by zero) and let p" be the project Pj E P' with the minimum ay-value (in case of tie, select the first one in the tie-breaking order).
3. Set the strategy c(p") to ( BB/V], that is, such that p' reports the cost equal to the total budget of its supporters in V"
4. Remove all supporters of p" from V and remove p* from P
5. Repeat Steps 4 until P' is empty.
Our algorithm is based on the following useful claim about the decisions made by MES-Cost.
Claim 2. Let us fax some stage of MES-Cost in which every voter with a nonzero budget has the same value of budget and let V be these voters. Then, for each a' d'affoordable project vf it holds that that a' +//A6""nVV
The claim is implied by the definition of MES-Cost. Observe that if a project p is a-affordable, then the voters approving it have enough budget to buy it and a is the minimum such æ that n'1I- x- cost(p) S cost(p) The sought is then clearly 1/IA()'nV'))
Let us denote by (pi.p?...., .P)) the projects considered in the respective iterations to of Steps 1-4. In what follows we show that in each Nash equilibrium MES-Cost selects exactly projects (pi, Po..p,....,. ).) in the given order and that c is a Nash equilibrium. We apply induction over the stages of MES-Cost.
For the base case, we argue that pf has to be selected first by MES-Cost and has to play e(c)) in every Nash equilibirum. Assume for contradiction that some other project p' is selected first instead
28

---

P1
P2
P3
P4
Figure Approval sets projects pt. P2, P2,P3, P3, and p4. Here, each vertex represents single voter.
of pi in a Nash equilibrium. Due Claim and since MES-Cost selects a-affordable projects starting from those with the smallest a, it follows that one of the three holds: (i) 1/A((')) < 1/1 (ii) 1/AA(')) 1/ A(rT)) and p' is preferred pi by the tie-breaking, or (iii) pi reports a cost greater than the budget of its supporters. Cases (i) and (ii) yield clear contradiction to Step 2, which defines př. Case (iii), reporting cost c' (pi) = d(pī) + B 1A(r))/// (such an c always exists contradiction. Knowing that p; is selected first in
due to Step 1) is profitable deviation for pi every Nash equilibrium, we observe that pi reports a cost c' (Pi)) B IA(pi)//Iv), then reporting exactly c(j)) = B 14(x7)//Iv is always a profitable deviation, which confirms that in every Nash equilibrium pi strategy c(pi) and selected first by MES-Cost.
We move on to the inductive step and thus consider stage i of MES-Cost in which project p is selected. Imporantly,
we have shown that player pi has report cost c(pi) equal the total budget of pi supporters, then we can assume that at the i-th stage we have only voters who either spend all their budget or who did not spend their budget at all; we denote the latter group by V'. As result, Claim 2 holds at the i-th stage, which we consider. Thanks to this, we apply an anal- ogous exchange argument (pretending that voters outside of V do not exist) that for the base case to show that indeed has to be selected at the i-th stage. Then, we directly repeat the ar- gument regarding the optimal strategy for pi applying it to pz. Eventually, we have shown that in each Nash equilibrium for MES- projects (pi. P2, ... are selected and report, respectively, costs (c(pT), c(p5), c(pī)).
B.8 Proof of Theorem 4.10
Proof. Let (P, V. B,d) be MES-Apr PB game with plurality ballots. In MES-Apr, like in every MES rule, each voter receives B/[v| money for the whole election process. As each voter approves only one project, each project pj can request most M (p+) IA(p0)-B/VV) from its supporters, and will report this cost as they would not spend any money on other projects. Thus, if d(p:) < M (pr), project pt reports M (p:) and gets selected with its maximum possible cost. Otherwise, if d(p.) > M (p:), Ps cannot be selected with cost covering d(pr), so reports d(p:) and is not selected.
B.9 Proof of Proposition 4.11
Proof. We create four projects PI..... P4 and 16 voters U1...., V16- Project p1 is approved by voters U,...., Usi project pa by voters ........ ... V1s U1; project Ps by voters Us...., 0g; and project p4 by voters bg...., U13- We set the budget to be some positive integer and delivery costs to be d = 0. Please note that we do not specify tie-breaking tie- breaking.
prove nonexistence of MES-Apr-NE in any
For better visualization of the instance, please look at the Figure 4. In particular, one can see that the instance is symmetric (each project is approved by three voters supporting only it and by two voters, one shared with each neighbour).
29

---

Now we will show that there is no MES-Apr-NE for this instance. Suppose towards contradiction that some profile e is a MES-Apr-NE.
At the beginning, each voter receives b = [ exceeding 5b- 5/8 I6 (otherwise its supporters would never have enough money to buy it, and b) no 3B (as each project has three supporters that contribute only to it, it is nonoptimal to say less than they have). Further, each project has zero delivery costs, each project must be selected in MES-Apr-NE, otherwise an unselected project could have decreased its cost to O and be selected. For this reason, Σi= c(p;)= S B.
B =
B money. Therefore, a) no project says cost 16
project says less than 36 = I6
For the sake of brevity, for yet-unselected project p; in iteration j. we denote 0r (p,) minimum value such that project p; is az (P.)-affordable according to MES-Apr rule (or infinity, if such a value does not exist). By E I.,, we mean some very small positive real number such that adding it does not change the given strict inequality sign.
Due to symmetry, w.l.o.g. we can assume that 1) project ps says the lowest cost (i.e., c(p1) S c(p2), c(p)), c(p2) I c(ps) and P2 wins ties with ps. If it was not the case, we can shift or rotate projects and perform analogous reasoning.
and wins ties if there is more than more project with this cost as well as 2)
Before we move on, let us exclude some cases in which c cannot be MES-Apr-NE.
We point out that if there is project of the same cost as Pt then P1 could have increased its cost by some positive number e while still being considered first and getting more, so с could not have been MES-Apr-NE in this case. Therefore, Pi has the same cost either as 1) p4. or 2) p2 (please note c(pi) = c(ps) implies c(pi) = c(p2) due to assumption that c(p2) S c(ps)).
With our assumptions, project P1 is selected in the first iteration and each of its supporters pays c(ps) for p1. As b e(p:) 5
for any Pt.Pj E P, voter i1 has insufficient money to contribute the equal share sípal to purchase p2. Therefore, in the second iteration, (p() = c(rx), (2(p2) c(p2)-(b- )
5- <
B 16
3
an
c(ps) 5
and ar (ps) c(pa)- (b- )
a2(P2).
Please note that a² (p2) = c(pa) (b- sim) <(m) 1 stmn)
6c(m))
B
20 + 2c(p1)
4c(p1)
20
61
20
8 2 c(p1)
au
8) = c(pt) 6B-5B c(p.) +
B
c(p.) = an (p1). Thus, as
16-20
16-20
(222)) > a (p project P4 would regret saying the same cost as project pl. Indeed, selecting Pr in the first iteration significantly increases a2 (P2) and (2(P)). so if ps said c(p4) c(p1), then it would benefit from slightly increasing the cost by (it would still be before p2, but it would earn more). For this reason, it cannot be the case that c(pi) = c(p4), so due to the former reasoning we know that c(p1) = c(p2) and c(p1) < c(pa).
So we know that: c(pL) = c(p2). c(pI) < c(pi), and c(p2) S c(ps). We have two cases to consider:
Project p4 is selected in the second iteration. It means that (p4) S a2(22). We observe that it must be (12 (p2(p4) = 02 (p2), otherwise it would be beneficial for p4 to slightly increase its cost by in such a way that p4 is still considered before p2 and gains more.
In this case, as P2 and p3 are approved by disjoint sets of voters and both p1 and P1 took the same amount of money from the same number of their supporters. both p2 and pa should request for the same amount of money, that is, all money that their supporters have.
Thus c(ps) = c(c2) 3- b + (b <(pul) + (b- <(pu)) = 5b
c(p))
e(ps) and
c(p4) = 5 - (5b e(p)) c(pz)) = 256 5c(p2) c(pi).
5
However, we know that c(pi) = c(p2), so c(pi) c(p2) c(pa) 5b c(p))
c(ps) which implies that c(p4) = 25b - 5c(p2) - c(p1) = 25h - 6C(p1). Therefore,
(p(44) = a2 (p2) means that e(pa) c(pz)-(b- s Ge(p1) - 1. which is equivalent to
5
4
20
256 6c(p1)
6c + 1006 24c(p)) 6c(p1) 1-56 56 + 30c(p)) 1056 + c(pi) 20
2. Then we have c(p)) = c(p2) c(pa) = Th 46.
and c(pa) = 25h Gc(p)) ) = 25h 21b
2
30

---

to c' (p()) = 365 Naturally, projects P2 and P3 are selected in first two iterations so voters v1,, ................................ U/ supporting Pt are left with b <(r2) b, b, b, b c(ps) money respectively and they have b <(<a) + + b+b++++
Now imagine that project p1 changes its cost from c(p1) Tb
2
5
b <(g=) 5b- 2 10 To
365 money in total which they can only spend on project p1 as
they disapprove P1- So P1 gets selected with c' c'(11) = 36b that could not be MES-Apr-NE
= c(p1) which indicates 10 >
75
2
Project P2 is selected in the second iteration. It means that (p2) S az(p4). We observe that it must be (P2) = Oz (P4), otherwise it would be beneficial for P2 to slightly increase its cost in such a way that p2 is still considered before P4 and gains more (please note that even if pa would jump before p2, it takes money from the disjoint set of voters from p2 s supporters, so it does not disprove this argument).
By performing analogous calculations to the previous case and using c(p1) = c(p2) we obtain that a= (P2) = c(p=)- بليا
Ge(p1] b 20 i.
so az(ps) az(p2) c(pi)
Ge(p1] b + c(p1) 6c(p))
20 4
After pl and p2 are selected, voter en has money left, voters 02,...: 03 have b
c(p)
5
money left, voters .,....., e have b - az (p2) = - ( (G((p)) left, and voters u6,,... 2/2 have b money left.
()= 256 (356-6((p)) money
20
We need to consider two cases:
P3 is selected before P4. Then c(ps) c(p2), otherwise (if c(p2) < c(ps)) P2 would increase its cost by in such a way that c(p2) + < c(ps) and still be selected in the second iteration, but with more money. Because c(ps) c(p2) c(pi) and the supporters of P2 and P3 are disjoint and symmetric, after selecting ps. voter es be left with no money whereas voters ....... with b - (pssp)) = b - a2 (P2) = 25b-6)(p1).
20
Further, in the fourth iteration, the supporters of p1 have together 3b + 2- 256 Gc(p)) 306++256 256 (5b--6((b)) 556-6e(p) Ge(p))
20
10 so p4 asks for the money they still have in total.
10
Therefore, c(p4) Gc(p:) 55
556- Ge(p1) 30c(p:) 25b 110b 12c(p1) +
10
42c(p1)
1356 + c(p1)
1356
Thus c(p1) 6c(p)
6. 1385
42
1356-
1006
1506
4.7
28
42"
Imagine what happens if p1 increases its cost from c(p1) = 1356
to cp
1568
42
42
Then P2 gets selected first with cost c(p2) c(pa)
1356 and each of its supporters pays 42
lank
27h Next, each of p3's 's supporters will pay 42 to purchase p3 (voters
27b
42
supporting Pa and Py are disjoint). After that, regardless whether P4 is selected before
pi or not, the supporters of p1 have 3b + 2 (b the supporters of pı have enough money to purchase pl. We showed that pl could
2
27b
42
3-42-2-156
42
156b
42 so
improve its utility by changing its cost, so the proposed e not MES-Apr-NE in this case.
- P4 is selected before p3. It means that a3(p4) S (2(2s). As we know how much money each voter has in the third iteration, as(ps) = c(p4)- Be(e1
200(p))-250-66(x) and az(ps) = e(ra) cips)
20c(p=)-4eig)
After insert-
80
80
ing the exact values we obtain that (p())) S as(ps) = 20e(p4) 2256--266666
<
80
4c((p) + 20c(ps) 2 20c(pz) - 256 10c+10c(pp) + c(ps) 2 c(p,)+ c(p)) 56
80
2
4
However, c(ps) 2 c(p.)+ + simn _ > c(p1) + 2/ 4 c(p)) + 4 > c(p)) + =
c(p2)+ 2. so c(pa) is significantly greater than c(p2). In other words, even when voter
Ue pays a greater share to buy p4 and is left with less money than c(ps) there still enough money to purchase p3- Therefore, P2 can increase its cost from c(p2) = c(pi)
5
to c(p3) - and lose the second iteration with p4, but still be funded before ps and obtain more money. For this reason, is not MES- MES-App-NE.
31

---

We showed that in no case MES-Apr-NA exists for this instance. The remaining tie- fre-breaknng order are completely analogous due to the instance's symmetry.
It means that for the given instance there is no tie-breaking for which MES-Apr-NE exists.
B.10 Proof of Theorem 4.12
Proof. We first consider the case of zero delivery costs, it is simpler. Let (P,N,B,d) be AEs PB game with party-list ballots and zero delivery costs.
At the beginning, each voter receives B/IvI money. In a party-list profile, as every two voters have either the same preferences or the disjoint ones, A(p;) A(porty(p:)) The total money the sup- [A Therefore, the projects in [V]
porters of pprty(p;) have is M (party(p:) [A(p:)] 8/IVI=
(p:)y(p:) need to somehow distribute this money between them in such way that no project would complain and change its cost to obtain better outcome.
Since we have cardinal utilities, the a-value of project p; is initially a (1.). = AApartyy (P:)] For this reason, MES-Apr will start from the cheapest project in the party to the most expensive one (following tie-breaking order in case of a tie) and equally take the budget from the party supporters to fund the next project unless the cost exceeds the money they still have.
e(ps)
This means that each project should ask for the equal part of the money of party supporters, that it, M(party(p.)) [party(p:) The project asking for more money would be moved to the end of the order when its supporters have insufficient money to fund it, so no project would increase its cost. Asking for less money is pointless if it already funded.
For this reason, for the profile where each project says c(p;) AES-Apr-NE.
M(pprty(p.)) [A(party(p:)] we obtain
Next we move to the case with arbitrary delivery costs. Let (P, B, d) be a MES-Apr PB game with party-list ballots. Recall that at the beginning each voter receives B/|v1 money. Then, the total money the supporters of party(p:) have is M (porty(p:) = |A(p:)] B/IV1 = [A(w]]-BB
Let > be the A/D tie-breaking order from the theorem statement. Note that for the case of party-list ballots > orders the projects within the same party nondescendingly by the delivery costs. That is, within the same party cheaper projects preferred to the more expensive ones, In case of two projects within the same party with equal delivery costs, we assume without loss of generality that the project with a lower index is preferred (we can always relabel projects to achieve this condition). Notably, does not impose any specific order with respect to the delivery costs over any two projects of two different parties.
Since in MES-Apr consider cardinal utilities, the a-value of project pt is at the beginning: c(pc) a1 (p:) [A(party(p.)) For this reason, MES-Apr will start from the cheapest project in the party to the most expensive one (following the specified tie- bebakiiaiig order in case of a tie) and equally take the budget from the party supporters to fund the next project unless the cost exceeds the money they still have.
Now we have to consider two cases:
The last in the bre-brea order project Py E party(ps) has delivery cost d(p,) not ex- M(porty(p.)) Note that this case is similar to our case with zero delivery costs ceeding |party(P:)]
that started this proof with, i.., each project submits M(pertu(p.)) gets funded, and no project benefits from changing its cost.
party((:))
The last in the tie-breaking order project pj E porty(ps) has delivery cost d(pp) exceeding M(party(p.)) [parby(p]]] In such a case, if every project submitted cost d(pj), then pb would not be selected as it is last in the tie-breaking order and cannot profitably decrease its cost. For this reason, we set the cost of p3 to be d(p)), remove Pj from consideration, and repeat this procedure as long the product of the number of yet-remained projects and the delivery
32

---

cost of the last in the tie- bre-bren project exceeds M (party(p:)). Suppose now that the procedure stopped and project Ps was the last removed one. Then all y yet-remaining projects would say cost min( (MMM(MM(rr)))))/// d(pa)) )) and be given this funding. Saying more than d(ps)) would result being overtaken by project Ps: and thrown out of the outcome due to insufficient budget. Saying more than M (pprty((p)))/ would result in getting the last among remaining projects and asking for more money than left in the budget at that timestamp.
The combination of e profiles calculated in the above way for all parties a MES-Apr-NE for the given instance.
L
Example B.2. Take PB game G with one voter approving projects Pt. P2- and p3- Let B 6,
d(pi) = 3, d(p2)= = O, and d(ps) = 0, with pı > P2 > p3- There is no MES-Apr-NE in G (the full proof is in the appendix and we give sketch): Suppose that e. is an NE. Then c(p1) (otherwise, as it is selected, Pr improves by reporting 3) and c(p2), c(ps) < c(pi) = 3 = B/2 (otherwise, the more expensive one is not funded). Since c(p2) + c(pa) < B. P2 may report (c(c))+)(e2))/2 and still be selected, so C is not an NE.
Suppose lowards contradiction that is such equilibrium. W.L.ogg.let c(p) 2 d(pi) = 3. Otherwise, if p1 would be selected under these costs (and, hence, received a negative payoff), then it would prefer to report d(p1) and receive utility O. If it was not funded under c, then (c-s, d(p)) also would be an equilibrium. Next, we observe that c(p1) = 3. Indeed, if Pı reported a value greater than 3, then one of the projects could obtain a better payoff: If p2 Pa reported value greater or equal to c(p1). then it would benefit by reporting a smaller one; if p2 and ps reported values that sum up to more than B, then least one of them would benefit by reporting a smaller cost, and if they reported values that sum up to at most B then either (a) one of them would benefit by reporting a larger cost, or (b) if they both reported 3, Pl would benefit by reporting 3. Hence, we have that c(pi) 3 = B/2. Then, both c(p2) > O and c(ps) > O (the project reporting O would benefit by reporting a larger number). Further, we have that c(p2) c(p1) and c(ps) < c(pi). Indeed. if either P2 or ps reported value greater or equal to c(p1) then it would not be selected and, hence, would benefit by reporting a smaller cost. So, c(p2) + c(pa) B. But then either of them would benefit by reporting a higher cost (so that the sum of their costs would not exceed B). Thus e not a MES NEN-Ap.-NE.
B.11 Proof of Theorem 4.13
Proof. Our example is in fact the example from Proposition 4.8 narrowed to prim voters and projects.
We have three voters vi, U2, and ea as well as three projects pl,P2, and p3. Projects p and p2 are approved by, respectively, voters U1 and v2, while project pa is approved by all three voters. We set the budget to be some positive integer denoted as B and the delivery costs of these projects to be O. We set the tie-breaking between projects to be P1 > P2 > P3. For the sake of brevity, for yet-unselected project p. in iteration j. we denote a, (p.) as minimum value such that project pi is ag (p:) aaffordbbaee according to MES-Apr rule (or infinity, if such a value does not exist).
Let (c(p1) MES-Apr-NV
7B 36
c(p2)
8B 36 c(pa)
21B be the costs the projects say. We will show that it is 36
At the beginning, each of three voters receives B 12B money.
3
In the first iteration, a (PI) 7B/30- and ps are tied, while P2 has greater a-value and is skipped for now. Thus, due to tie-breaking, we select p1 and voter 21 pays 36
1
2B 36
an (P2) #2/36
SB a1 (px)
36
218/38
3 36
7B
so p
for p1-
12B Thus, since the budget of In the second iteration, vn has 5B money while both U2 and v3 have 36
36
2/ did not change, (2(22) = an (p2) =
8B In order to purchase Ps, voter U1 would need to spend
36
all left money whereas Up and v3 would need to pay more to make up i 's insufficient money. More
precisely, (p3) =
108/3e
8B So projects p2 and Pa are tied and we select pa
2
36
due to tie- biebbraaknn (by taking money from 02).
33

---

Finally, in the third iteration, we will select ps as its supporters have 5.8 all voters will use use all their money for it.
4.8
12B
21B = =(ps),
36
36
36
We showed that each project is selected with the proposed costs so no project benefits from lowering its costs. Next, Ps will not increase its cost as its supporters would not have enough money buy it in the last iteration. Further, P2 will not increase its cost as it would lose with ps in the second iteration and its only supporter U2 would pay 36
SB for ps, leaving insufficient 35 for p2. Analogously,
Pi will not increase its cost as it would lose with P3 in the first iteration and its only supporter 1i would pay 7B for ps. leaving insufficient 5B for p1-
36
36
For this reason, с (c(p1) instance.
7B c(p2) 36
21B) is MES-App-NE for the given &B c(pa)
36
One can show in an analogous way that c' (c' (p() MES-Apr-NE for the given instance.
8B c((p2) 36
7B c'(ps)
21B is also 36
36
B.12 Proof of Theorem 6.1
Let us begin by introducing additional notation. In cost- PB game G+ (P,
associate each voter with approval function A V x P - 2/0.B1, with A(v,p) p) specifying how costly can a project p be for v to approve it. For simplicity, we assume that A(v, p) is a possibly empty interval. We say that voter potentially supports project p if A(v. p) * 0. Then, for a strategy profile c, the corresponding PB election E(c) = (P. V, B. is such that each voter approves project p P if cps E (p). Then, the payoff function and Nash equilibria are defined for cost-interval PB games analogously to PB games. We now showcase examples witnessing the result for particular voting rules.
MES-Cost. Consider the following cost-interval PB game G. Take the set of projects P =
(p.. as well as the set of voters V {u1, 02, U3 24 Further, we let A(11, p1) A(u2, P1)
[8, 12). A(va, P1) = A(vs,P1) = [0, 4). A()),P2) = [4, 8). and A(v2.P2) = A(U3,P2) P2) =
A(va.22) = [0. Finally, let B 16.
Suppose that there exists strategy profile that is a MES-COSI-NE. Let us then consider the following, exhaustive cases:
1. c(pI) E (4,8) U 16). Then, pr is not funded, while for c(p1) = 1, Pı is founded regardless of c(p2).
2. c(pi) E (8, 12] Then, pl not funded, and hence could benefit from lowering its cost.
3. c(p1) 8. Then, we note that as c is an NE, c(p2) 3, then P2 is funded but would not be selected for (8, c'(p2) with c((p2) > 3. But then, P1 is not funded under c, while would benefit from submitting c' c'(p1) 4.
4. c(pI) E [0, Then, c(p2) = 4, as then P2 is funded under but would not be under
(c(p1), c' (p2)), for any c' (p2) > 4. However, in that case p1 would benefit from raising
their cost to 8.
It follows that there is no MES- NES-Cost-NE in G.
BasicAV. Consider the following cost-interval PB game G. Take the set of projects p= {21. where P1 > P2. as well as the set of voters V = {U, U2, V3. Va. Us Further, we let A( P1) = [5. 9). A(v2, P1) [3, 7]. A A(U3, P2) = [4, 8). A(es. = [5. 7]. and A(Us, P2) = [1, 6] so this is plurality profile. Finally, let B = 10.
Suppose that there exists a strategy profile that is BasicAV-NE. Let us then consider the follow- ing, exhaustive cases:
1. c(p1) E [0, U) 10). Then, p1 is not funded but would benefit from submitting c' c((p2) = 3, then pl is always selected.
2. c(pi) [3, 4) U (7, 9]. Then, we note that as c is an NE, c(p2) = 7, as then P2 is funded
but would not selected for (c(p1), cp())) with c' c'(p2) > 7. But then, pt not funded under c, while it would benefit from submitting c' c((p) = 7.
34

---

3. c(p1) E [4,7]. Then, c(pz) = 6, as then P2 is funded under but would not be under (c(pi), c' (p2)), ) for any c' (pz) > However, in that case p1 would benefit from reducing their cost to 4.
It follows that there is no BasicAV-NE in G.
AV/cost. Consider the following cost-interval PB game G. Take the set of projects P = {pI. }2), where p2 > Pl. as well the set of voters V = {v1, U2, U3, v. Further, we let A(v1.
P1) ) = [4. 9),
A (U2g. P1) = A(u,,P1 = [8, 9]. and A(v,, P2) = [2, 6]. so this is plurality profile. Finally, let
B 10.
Suppose that there exists a strategy profile c that is a AV/Cost. Let us then consider the following, exhaustive cases:
1. c(p1) E [0, (), 10). Then, p1 is not funded but would benefit from submitting c((2))
5, as then is always selected.
2. c(pi) [8, (8. Then, we note that as is NE, e(p2) = c(pil/a, as then p2 is funded but would not be selected for (c(p1), c(22) with c' (p2) > o(pu)/a. But then, Pi not funded under while it would benefit from submitting c(p1) E [4, c(p2)).
3. c(PI) 85. Then, c(p2) min( min)((pp))))) 6) E [5, 6]. as then P2 is funded under but would not be under (c(P)). c'(p2) c2(p2)), for any c((p2) > min(((p))) 6). However, in that case
P1 would benefit from raising their cost to 9.
4. c(Pi) 5). Then, c(p2) min(10- c(p2), 6) [5, 6). as then P2 is funded under but would not be under (c(P)), c' (2(2)), for any c' c'(22) >> min(10 - c(p2), 6). However, Pi would benefit from raising their cost to 9.
It follows that there no AV/Cost G.
Phragmén. The claim follows by the example for AV/Cost, as Phragménand AV/Cost are equiva- lent for plurality elections.
MES-Apr. Consider the following cost-interval PB game G. Take the set of projects P {21.P2). as well as the set of voters V = {U1, U2, v3). Also, let A(U .PI) A(v [12, 18). Then, let A(v2, Pi) = A(V2.P2) = [6. 12] and the approval function of 03 be the same as the ap- proval function of 02. Finally, we let B = 18 and assume zero delivery costs. It's clear that each voter received B/3 = money units at the beginning of the algorithm regardless of the costs of the projects.
Suppose that there is a MES-Apr-NE c (c1, 02) for G. First, we can see that each of the projects is funded with the cost set to 6 regardless of the cost submitted by the other proposer. So, both projects are funded under (2), Hence, we notice that e₁ [6. 12] and C2 E (6. 12), as otherwise, either one of the projects would submit cost higher than 12 and be supported by only voter (whose budget 6), or submit cost lower than 6 and not be supported by anyone. So, in both scenarios one of the project would not be funded. Let us then consider the following exhaustive cases:
1. C1 12 or C2 12. Without loss of generality, let C1 12. Then, see that C2 8 or C2 = 12. Otherwise, if 02 E (8, 12), then P2 would not be funded and if 0o < 8, then P2 would be funded under (12, C2 + e), for some 0. But then, one of the projects is not funded under (C1, C2), as 01 + C2 > B. Hence, according to previous observations, (c1, (2) is not MES-Api-NE.
2. C1 [6, 12) and Ci E 66, 12). Observe that for this cost range, only voters v2 and va may pay for these projects, while having 12 money units in total. Then, we observe that G + C2 < 12, as otherwise one of the projects would not be funded. Moreover, 61 C2. as otherwise the proposer P: submitting the lower cost would benefit from increasing c.- Hence, in this case 61 C2
But then P1 would also be funded under (12, 6), and hence (cI, C2) is not an MES-Apr-NE
It follows that there is no MES-Apr-NE in G.
35

---

Table 3: Additional PB instances that analyze in the experiments. Vote Len. means the average number of approvals a ballot. Rule indicates PB rule that was used in original election.
Instance
[P]
V
Budget
Vote Len.
Rule
Bemowo
83
5181
4854279
10.8
BasicAV
Bielany
98
4957
5258802
9.8
BasicAV
Wilanow
35
2359
1516962
9.59
BasicAV
Wlochy
43
2221
1719224
9.51
BasicAV
BasicAV Bemowo
Busi Biclany
BascAV Wilmow
BusiAA Wlechy
Costria Costiia mithors
millbrs)
Con Go aitibocs
300
1
Number
Nambereed
Nambher AV/Coott
AV/Cost
Bemowo
AV/Cost
Bielany
AV/Cost Wilsnow
Wlochy
Cos miliitio
Cos milloay)
Cos milloon) P S &
3001
A
Nimber
Phragmon
Bemowo
Phragman Bielary
Phrigman
Wilsnow
Phragmin
Wlochy
Cos Eo (illoos)
Doo On millors)
6 2
Cool En millins)
&
3000
1255
Sumber
VO0ES
Sumber
votes
Nimber of 100es
Number of 100m
MES Apo/Ph
Bemowo
ApoPP
Bieluny
MES Azelt
Wilmow
MES Apr/Ph Wiochy
Coot On callion))
Coo de milloo)))
Gn millow))
6 6
Cloa lo sollbw))
&
309
195
VOIES
Sunba of HOtES
Namber of 1000S
Namber of VO0ES
MES-CosPPh
MES-Coo/Ph Bielany
MES-CowPh Wilanow
MES MEN-CooPhh Wkechy
Cost (n pittors)
Cont millors)
6 E.
Coo Dn unllas)
2001
120
Number of VOKES
Sumber of HORes
Nimber of
Namber of V000S
Figure 5: Winning (green bars) and losing (red bars) margins in real-life PB. Projects ordered by decreasing approval scores (on the z-axis) are represented by bars. Tacks and crosses show, respectively. the original and best response costs.
C Additional Experimental Results
Here, we present experimental results for four additional PB instances held in 2022 in different districts of Warsaw, Poland, i.c., in Bemowo, Bielany, Wilanow, and Wlochy. Details regarding these datasets are presented in Table 3. In Figure 5 we present the winning and losing margins in additional real-life PB instances, and in Figure 6 we present the strategy profiles after 10'000 iterations of our dynamics.
Moreover, in Table 4 we present comparison of the original winning and losing margins and those after 10'000 iterations. We observe that in most cases the size of the margins drastically decreased.
D Dynamics With 80 % Delivery Costs
In Figure we show the results of the dynamics from Section 5.2 for the case where each project has delivery cost equal to the 80% of the cost it had in the original instance. We see that aside from
36

---

Original Margins
10000 it. Margins
Rule
Winning
Losing
Winning
Losing
BasicAV
1830 + 1283
122 = 182
0
24 = 37
Bemowo
AV/Cost
150 + 104
225 = 257
1
0.2 0.1
Phragmén
141 = 91
220 = 261
3
0.9 = 0.7
MES-Apr/Ph
150 95
223 = 264
3
2
MES-Cost/Ph
250 + 323
205 = 244
1
1
BasicAV
1447 + 1355
218 = 205
2
Bielany
AV/Cost
157 + 128
171 + 150
0.9
0.2 0.3
Phragmén
146 + 121
176 + 154
4
0.9 0.9
MES-Apr/Ph
148 + 121
176 = 151
3
1
MES-Cost/Ph
172 + 193
180 = 154
3
3
BasicAV
265 + 249
64 51
0
0
Wesola
AV/Cost
+
+
0.3 0.4
0.2
Phragmén
69 + 31
51
2
0.9
MES-Apr/Ph
79 + 33
43 37
2
0.7
MES-Cost/Ph
70 + 56
65 + 45
0.1 0.1
0.4
BasicAV
536 + 399
87 = 80
Wilanow
AV/Cost
87 + 59
51 + 34
2
0.1
Phragmén
77 + 52
+
2
0.2
MES-Apr/Ph
89 + 56
58 = 37
2
0.7
MES-Cost/Ph
79 + 120
95 + 64
1
2
BasicAV
532 + 524
46 = 35
0
0
Wlochy
AV/Cost
107 + 49
- 48
0.8 1.0
0.1 0.1
Phragmén
83 + 52
62 = 42
3
2
MES-Apr/Ph
85 + 53
= 45
2
1
MES-Cost/Ph
138 + 186
56 + 46
0.2 0.2
0.4
Kleine Wereld
BasicAV
117
1.0
AV/Cost
12 + 8
12 + 12
0.1 + 0.1
0.1
Phragmén
10
10 11
0.5
0.2
MES-Apr/Ph
11
11 11
0.4
0.2 0.2
MES-Cost/Ph
26 34
11 11
2
0.1 - 0.0
Table Comparison winning losing margins original elections and 10000 iterations of game. (All the values are 1000 PLN EUR). In each entry the first value denotes the average and the second value (i.e., the one after + sign) denotes the standard deviation.
fairly expensive projects, whose cost could not drop below the delievery cost, the overall behavior of our rules is with zero delivery costs.
37

---

BeeiAA Bemowe
BanicA Birlany
RoscAV Willnww
BasicAV Woele
5 8
1294
Namther
AV/Ccs BaCooA
AV/Cox Bielary
Windhr TAIIIIAIT
Cop Oectenttion
Coe (iiiie
6
E
0
Nasben VARS
Nuxdec of vilce
Piroarnóo
Pingamco
Biclany
Plaamin Wilseww MI
Cyn (ello
81 8
2
0
22
Sarber
Namberof of miies
Apr/t
Bemowo
Apc/Ph Bielary
MES-Apsls Willaoo
MES-Ap/Pt Whely
8 8
Con S
81
2
Naxber
MES Cosy7b
Bemowo
MES Cooyth
Bielary
MES-Crelfh
Wilnow
MES Windw
8
0
8
81
22
Figure 6: Strategy profiles after 10000 iterations of our dynamics. Projects ordered by decreasing approval scores (z-axis). Final projects' costs shown by bars; the original costs shown as dashed lines. Red and green bars indicate, respectively, losing and winning projects; brighter parts are the increases over the original cost. The triangles at the top mark the originally winning projects. Brown circles denote the equilibrium costs (for rules for which can compute it).
38

---

Klene
AVICoo Wesdh
AWXCost Kiine World
Immm
Pleannin Wonde
Porgarn
Klinne Wordld
Sarba
TITITT
Weods
Cuedt
5 6
Na
Figure 7: Strategy profiles after 10 000 iterations of our dynamics. for the case where each project has delivery cost equal to 80% its original cost in the instance. Projects ordered by decreasing approval scores (z-axis). Final projects' costs shown by bars; the original costs shown as dashed lines. Red and green bars indicate, respectively, losing and winning projects; brighter parts are the increases over the original cost. The triangles the top mark the originally winning projects. Brown circles denote the equilibrium costs (for rules for which we can compute it).
39


Reviews:
[{"review_id": "LKDVHD2M7Z", "reviewer": "Reviewer_Ewmz", "summary": "This submission concerns strategic aspects of project proposal in the standard model of approval-voting-based participatory budgeting. There are a number of standard preference aggregation rules -- drawn from both theory and practice -- which take in project (voter) approval sets and costs, along with an overall budget, and output a deterministic budget-feasible subset of projects (possibly making use of a prescribed tie-breaking rule or order). \n\nAtop this setting, the submission proposes a game-theoretic formulation of the process from the project proposer's perspective. Each project has a minimum cost (analogous to a reservation price), and proposers can specify a project cost above this minimum. If the project is funded, the proposer's utility is the difference between their specified cost and the minimum; if unfunded, then $0$. The task is then to establish for which combinations of rules, restricted approval profile settings, conditions on the minimum cost, and assumptions about the tie-breaking rule used this game has pure-strategy Nash equilibria (PSNEs), and what they are. \n\nThe submission finally analyzes a few actual participatory budgeting instances, comparing the reported project costs to individually computed best response project costs according to the specified game. It also heuristically attempts to identify PSNEs in these instances, and compares the PSNE found with the reported costs in the profile.", "questions": "1. Why did you choose this particular form of proposer utility (line 173.5)? Since all rules are deterministic, this is a full-information setting, and you're after pure strategies, it seems like you might need only (i) that proposers are indifferent between being funded below the minimum and receiving no funding, and (ii) for c > d utility is monotonically increasing. Does this check out? If so, I think it strengthens the case for this model.\n\n2. In Section 6 and the discussion following Theorem 6.1, the more general model you contrast against seems to allow voters to have both different minimum and maximum thresholds for project costs, outside of which they will not vote for the project. An intermediate choice (and perhaps a more reasonable one for value-conscious voters) might be that they share a common minimum equal to the project's minimum cost, and have different maximum thresholds. Does Theorem 6.1 remain true in this intermediate model, or do some rules still admit PSNEs? \n\n3. For what proportion of runs did your heuristic PSNE-finding algorithm fail to converge? For the rules where you do not prove there is a unique  PSNE, did you find evidence of multiple distinct PSNEs? Multiple substantially different PSNEs?\n\n\nPossible corrections:\n\tan NE exist -> exists (233)\n\talways is -> is always (282)", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\t- Overall the submission is well-organized and well-written.\n\t- I found the case made in the introduction that there is a large amount of strategic cost selection in practice to be quite compelling. \n\t- This overall inquiry seems careful, thorough, and more or less complete.\n\nWeaknesses:\n\t- At a high level, some of the positive results are unsurprising. For rules that iteratively build the winning slate and are insensitive to project cost, it makes perfect sense that each project should maximize its reported cost, conditioned on not 'falling off' of the end of the budget.\n\t- There is perhaps some tension between the case made in the introduction,  the experimental findings, and the credibility of the model. If strategic behavior is evident, why is it empirically so far from best response or equilibrium? If it is because of incomplete information in practice, are Nash equilibria the right way to model this phenomenon?\n\t- I found the notational choices somewhat confusing. Should $c(p_i)$ on line 173.5 in fact be $c_i$? If $c$ and $d$ are both project-dimensional cost vectors, why not make their `type' and notation symmetric? \n\t- I also found some of the technical language -- particularly the order of quantifiers -- around results relating to tie-breaking unclear. For instance, does (b) in the statement of Corollary 4.6 mean 'for all A/D TBOs' ... or 'there exists an A/D TBO...'?\n\t- More discussion of why rules with PSNEs are normatively preferable would be helpful. This is especially true since the assumption that all votes are common knowledge is quite strong. When are these PSNEs such that they can be played without perfectly knowing all voters' approved projects beforehand?", "was_revised": true, "final_justification": "At a high level, I find this problem well-motivated and the treatment provided here responsible and thorough. I retain the impression that most of the positive results arise from rules that are price-insensitive and for which the equilibria are what one would expect, and remain wistful for insight into the impossibility landscape when voters approval windows are defined by upper bounds only.\n\nI appreciate the authors engagement through rebuttal and came away with a better appreciation for the role of the experimental results in the submission. Based on this balance of factors and the overall positive reception this submission received, I will be leaving my positive score unchanged.", "rebuttal": "REVIEWER'S COMMENTS   \n\n1. At a high level, some of the positive results are unsurprising. For rules that iteratively build the winning slate and are insensitive to project cost, it makes perfect sense that each project should maximize its reported cost, conditioned on not 'falling off' of the end of the budget.\n\nANSWER: While some of the positive results may appear intuitive, omitting them would make the paper incomplete. Our positive results are used to showcase differences between voting rules, which in our view are not always obvious.\n\n2. If strategic behavior is evident, why is it empirically so far from best response or equilibrium? If it is because of incomplete information in practice, are Nash equilibria the right way to model this phenomenon?\n\nANSWER: Some PB instances, for example the instances from Wroclaw, often follow the NE predicted for BasicAV. In other cities, proposers may also be taking into account various other considerations than simply maximizing project cost (such as their unwillingness to propose very large scale projects or their attitude towards public funds being spent efficiently). Finally, most PB instances in Pabulib employ the BasicAV rule, so we cannot hope to see equilibra for other rules, except for a few cases of MES-Cost. In this case, there were so few elections that employ MES that the voters might have simply not gotten to the point of understanding the rule sufficiently well to act in an optimal strategic way.\n\n3. I found the notational choices somewhat confusing. Should $c(p_i)$ on line 173.5 in fact be $c_i$? If $c$ and $d$ are both project-dimensional cost vectors, why not make their `type' and notation symmetric?\n\nANSWER: Thank you for your suggestions, we will incorporate them in the final version!\n\n4. I also found some of the technical language -- particularly the order of quantifiers -- around results relating to tie-breaking unclear. For instance, does (b) in the statement of Corollary 4.6 mean 'for all A/D TBOs' ... or 'there exists an A/D TBO...'? \n\nANSWER: Thank you for this comment, we will make sure to clarify our technical language! In this particular case, Corollary 4.6(b) follows from Theorem 4.4., so we mean 'for all A/D TBOs'.\n\n5. More discussion of why rules with PSNEs are normatively preferable would be helpful. This is especially true since the assumption that all votes are common knowledge is quite strong. When are these PSNEs such that they can be played without perfectly knowing all voters' approved projects beforehand?\n\nANSWER: We view the existence of a pure Nash equilibrium as a certain measure of predictability of the value towards which the cost might gravitate. Furthermore, it also provides an information about the qualities of particular voting rules, and incentives that they create for project proposers. For instance, we can observe that Method of Equal Shares promotes cheaper or more expensive projects depending on its variant, which gives us an additional information about benefits and consequences of applying the specific variant of the rule. In this sense, we view the NE analysis as the way of understanding PB rules, and their effect on project proposers' behaviour.\n\nFurthermore, the amount of information regarding voters' preferences needed for strategic play is not equal among the voting rules. For instance, BasicAV or AV/Cost do not require knowledge about individual ballots. Instead, under them it is enough to know the sizes of particular projects' support sets, which is a much weaker requirement.\n\n\nQUESTIONS\n\n1) Why did you choose this particular form of proposer utility (line 173.5)? Since all rules are deterministic, this is a full-information setting, and you're after pure strategies, it seems like you might need only (i) that proposers are indifferent between being funded below the minimum and receiving no funding, and (ii) for c > d utility is monotonically increasing. Does this check out? If so, I think it strengthens the case for this model.\n\nANSWER: We believe that what the reviewer suggests is correct and generalizes our model. In our model a proposer would never submit a cost below the delivery one. This, in essence, translates to being indifferent between being funded below the minimum or not being funded at all, as in the reviewer's suggestion. The generalization follows from assuming an arbitrary monotonic increase of the utility when one gets funded. Our arguments, currently using a linear increase of utility, would remain valid for this case of strictly monotonic ones---the proposer wants as much money as possible to get and the specific rate of growth of the utility is not relevant (as long as the project remains funded). Thus, overall, both approaches are strategically equivalent.\n\n2) In Section 6 and the discussion following Theorem 6.1, the more general model you contrast against seems to allow voters to have both different minimum and maximum thresholds for project costs, outside of which they will not vote for the project. An intermediate choice (and perhaps a more reasonable one for value-conscious voters) might be that they share a common minimum equal to the project's minimum cost, and have different maximum thresholds. Does Theorem 6.1 remain true in this intermediate model, or do some rules still admit PSNEs?\n\nANSWER: Thanks for this suggestion! First, it is worth observing that setting a common lower threshold for support is analogous to setting its delivery price (it is never profitable for a proposer to set the cost of a project below the threshold). The properties of this intermediate model are not obvious, so we cannot give precise information at the moment.\n\n\n3) For what proportion of runs did your heuristic PSNE-finding algorithm fail to converge? For the rules where you do not prove there is a unique PSNE, did you find evidence of multiple distinct PSNEs? Multiple substantially different PSNEs?\n\n\nANSWER: Generally, we got a qualitatively the same result for every run of our heuristic and we did not observe evidence of nonunique PSNE. However, the computations rarely \"fully converged\" in the sense that often a small number of fairly cheap and not widely supported projects could still be funded if we decreased their cost by a tiny amount. We believe that we could reach full convergence if we dynamically adjusted the cost-change ranges, but we were satisfied with the qualitative results."}, {"review_id": "dYud2BWUpo", "reviewer": "Reviewer_9ESW", "summary": "The paper studies the following game-theoretical problem related to participatory budgeting (PB): \nThe input consists of a PB instance with approval preferences where each project has a distinct proposer and minimum cost (delivery cost) and the proposers are the players such that the utility of a player is equal to the suggested cost minus the delivery cost if the  project is winning; otherwise the utility is zero.\n\nThe paper is interested in finding out whether there exits a strategy profile (i.e., cost per project that is at least the delivery cost) that is a Nash equilibrium for each some commonly studied PB rules.\n\nThe authors show the following\n(1) For approval voting (AV) with a fixed tie-breaking order, there is an NE where the profile with the most approvals reports the whole budget as its cost and is the only winner. \n\n(2) For AV/Cost, i.e., approval voting where the approvals are divided by the project cost, they show that if the minimum delivery costs over all the projects are less than the budget, then all the projects are funded. More generally, a NE always exists for some tie-breaking rule. \n\n(3) Phragmén-rule may not admit a NE. \n\n(4)There is a polynomial-time algorithm that computes a near-unique NE for MES with cost utilities, whereas for MES with approval utilities, an NE may not exist.\n\n(5) The authors show experimentally that under AV, the game converges to NE where the winner takes the whole budget. For AV/Cost, Phragmén, and MES with approval utilities, projects report costs that are proportional to their support, while MES with cost utilities has a few projects who report higher costs.", "questions": "Line 28: \"This happens, e.g., ...\": Without knowing more details, this sentence reads unconvincing. For instance, if the price of a project is too unrealistic, it would lose votes. Could you elaborate more why the rules you mentioned encourage submitting more expensive proposals?\n\nIf you have any further justification for your model and/or against the models you decided not to study in detail, I would like to hear it.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength: The paper appears technically sound. The assumptions and setting are described clearly. The paper studies a quite interesting problem and presents an interesting angle for judging different PB rules. \n\nWeakness: It's not clear why the player's utility is precisely how much money the project additionally brings. For instance, it could be that the proposers care first and foremost about getting the project funded to the smallest feasible amount, and the extra money after that is far less important – so something akin to the extended utility function of Remark 3.1.\n\nSecondly, the arguments against cost-interval games in PB (Section 6) sees not very convincing as well. I think your example of “voter approves building a bike path for at most $25000 when others do so only if it costs above $75000” is not any more unrealistic than assuming that the proposer is indifferent between their project being approved for the minimum feasible amount and it not being approved at all. Honestly, the former seems plausible to me because people can consider the same project to have a different worth. Even if we agree this is unrealistic, one could study how the restriction that does not allow this behaves. This is naturally outside the scope of the project, but it could be discussed as a possible avenue of future work.\n\nDetailed remarks:\nLine 12: “One natural question that the proposers face is … ?” This sentence is not a question, so it should not have a question mark.\n\nLines 121 and 131: Tie breaking is named in one case but not in the other, also the first time it is not entirely clear whether $\\succ$ is given or obtained from somewhere.\n\nLine 137: \"have cost(p) funds..\" What does it mean?\n\nLine 154: Are plurality preferences not a special case of party list preferences? Would be good to note this.\n\nSection 3: Please formally define NE. Also, to connect better, one should say that the strategy profile c will set the cost function for the PB rule. \n\nLines 172-173: The utility function needs justification. \n\nLine 174: minimal -> minimum? \n\nLine 176: “In particular, the proposers do not receive funds equal to the utility values.” I do not understand this sentence. Are the utilities not assumed to be the amount of money the projects are allocated?\n\nDefinition 4.1. The profile ap is unique, right? It could be emphasized in the definition.\nTable 1: The double circle in the legend does not seem to be used.\n\nLine 212: Why are you interested Definition 4.1. It would be great to discuss a bit more instead of referring to some other papers.\n\nExample 4.3: The example has tie-breaking p2 > p1. But later you said p1 > p2. Please justify. Also, please state directly how a AV/Cost-NE with your original tie-breaking looks like.\n\nFigures 1 and 2: The text is the figures are too tiny to read. Please don't abuse the font sizes in such extend. \n\nLine 273: “… there are instances with no equilibria, even for very small instances” clumsy.", "was_revised": true, "final_justification": "See my last comment.", "rebuttal": "REVIEWER'S COMMENTS\n\n1. It's not clear why the player's utility is precisely how much money the project additionally brings. For instance, it could be that the proposers care first and foremost about getting the project funded to the smallest feasible amount, and the extra money after that is far less important – so something akin to the extended utility function of Remark 3.1.\n\nANSWER: If the proposers only cared about getting the project funded at the minimum cost, then we would miss the strategic interaction---the proposers would simply submit the lowest cost, without regard for what the others do. On the other hand, if their utility improves above the minimal cost in some monotonic way (e.g., a sublinear one, if one is after a slow rate of growth), then this is equivalent to the current setting (see our response to Reviewer Ewmz). As for Remark 3.1., if one likes this approach, then all the results still hold for it. \n\n2. Secondly, the arguments against cost-interval games in PB (Section 6) sees not very convincing as well. I think your example of “voter approves building a bike path for at most 25000 while others do so only if it costs above 75000” is not any more unrealistic than assuming that the proposer is indifferent between their project being approved for the minimum feasible amount and it not being approved at all. Honestly, the former seems plausible to me because people can consider the same project to have a different worth. Even if we agree this is unrealistic, one could study how the restriction that does not allow this behaves. This is naturally outside the scope of the project, but it could be discussed as a possible avenue of future work.\n\nANSWER: Thanks for this remark! Regarding the example against cost-interval games, our critique is that the broad possibility of setting approval ranges allows for quite implausible, unreasonably low, or unreasonably high selections.  We will discuss the direction you suggest in the final version of the paper! On the other hand, we view the indifference between a project being funded for the minimum feasible amount and it not being funded at all as a boundary condition.\n\n\nQUESTIONS\n\n1) Line 28: \"This happens, e.g., ...\": Without knowing more details, this sentence reads unconvincing. For instance, if the price of a project is too unrealistic, it would lose votes. Could you elaborate more why the rules you mentioned encourage submitting more expensive proposals?\n\nANSWER: BasicAV rule selects projects based on the number of voters that approve them, without taking the projects' costs into consideration. Therefore, proposers of the most popular projects are incentivized to raise their price.  Indeed, while unrealistic prices may discourage the voters, we assume that together with the cost, the proposers also extend the scopes of their projects. Hence, the projects maintain reasonable cost given the scope. Notably, in Pabulib one can observe that more expensive projects tend to receive more votes than the cheap ones.  We will make sure to clarify that in the final version.\n\n2) If you have any further justification for your model and/or against the models you decided not to study in detail, I would like to hear it.\n\nANSWER: One argument is that the current model is the baseline that one should start this line of research with. We feel that only with the current set of results in place, one can look for further refinements of the model."}, {"review_id": "6GbX4WMFcA", "reviewer": "Reviewer_qHNA", "summary": "This paper evaluates several Participatory Budgeting (PB) algorithms based on the equilibrium induced by these rules when strategic proposers act rationally. Authors also provide extensive experimental analysis on publicly available datasets. The important results in the paper are:\n\n1) MES with cost utilities always admit a Pure Nash Equilibrium (PNE). The resultant project selection under this rule leads to a larger number of project approvals. \n\n 2) The BasicAV algorithm also admits PNE under which a single largest project is approved.  \n\n3) Other rules, such as AV/Cost, Phragmen and  MES with approval utilities, do not guarantee PNE.", "questions": "1. I could not fully understand the end goal here. While equilibrium analysis in the paper is mostly predictive analysis, it will help if the authors comment on the prescriptive angle of the analysis as well. As a proposer deciding how to set project prices, what information do I need for different selection rules, and how realistic is it to obtain and/or process the information? \n\n2. Can authors comment on the rules that induce the desired equilibrium point in the Nash strategy (or dominant strategy) profile? In other words, do there exist mechanisms that induce the desired equilibrium outcome?\n\n3. The paper lacks robustness studies. How robust are the equilibrium notions to miscalculation by a single or/few agents?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: The paper is well written and easy to follow. The problem studied in the paper is rooted in real-world applications. Authors also do a commendable job in providing real-world instances of the settings studied in the paper. The mathematical analysis and experimental analysis are rigorous. \n\nWeaknesses: I do not find any significant flaws in the paper. However, intuitive explanations of some of the results in the paper will improve its readability, especially in Section 4.4. Further weaknesses include a lack of robustness analysis and a lack of practical relevance of the proposed solution in the real world.", "was_revised": false, "final_justification": "", "rebuttal": "REVIEWER'S COMMENTS\n\n1. Intuitive explanations of some of the results in the paper will improve its readability, especially in Section 4.4. \n\nANSWER: Thank you, we will make sure to clarify the intuition behind our results in the final version!\n\n2. Further weaknesses include a lack of robustness analysis and a lack of practical relevance of the proposed solution in the real world.\n\nANSWER: The analysis of robustness of equilibria is indeed a good avenue for future research, which is further related to, e.g., our assumptions of perfect knowledge of the players. Regarding the practical relevance of our results, we believe that the strongest value of the paper is in understanding differences between the incentives provided by the rules. In particular, we observe a significant difference between MES-cost and MES-Apr/Phragmen, where the former is guaranteed to have NE, and in experiments selects fewer, more expensive projects. This makes MES-cost a more appealing proportional rule from the perspective of cities---implementing fewer, more expensive projects is logistically easier for them.\n\n\nQUESTIONS\n\n1. I could not fully understand the end goal here. While equilibrium analysis in the paper is mostly predictive analysis, it will help if the authors comment on the prescriptive angle of the analysis as well. As a proposer deciding how to set project prices, what information do I need for different selection rules, and how realistic is it to obtain and/or process the information?\n\nANSWER: In general (for exceptions see the answer to comment 5 for reviewer Ewmz), in our setting, a proposer is required to know the approval sets of the voters, projects' delivery costs, and the voting rule (including the tie-breaking rule). We acknowledge that the perfect knowledge assumption is an idealization. However, the voting rule is known from the setup of an election. Further, we assume that an estimation of delivery costs can be made through an analysis of the proposals. Finally, an estimation for voters' ballots can be obtained, e.g., through reliable polls. But, foremost, we view the value of our results to be in the improved understanding of the analyzed rules.\n\n\n2. Can authors comment on the rules that induce the desired equilibrium point in the Nash strategy (or dominant strategy) profile? In other words, do there exist mechanisms that induce the desired equilibrium outcome?\n\nANSWER: Thank you for this suggestion! In our work we aimed at understanding the properties of most popular voting rules in the context of strategic cost selection. The mechanism design approach to this problem is of natural interest, but we defer it to future work.\n\n3. The paper lacks robustness studies. How robust are the equilibrium notions to miscalculation by a single or/few agents?\n\nANSWER: Generally, if some of the proposers submit slightly lower costs than prescribed in an NE, then the remaining ones can either submit slightly higher ones or maintain NE ones without losing too much. If some voters overshoot their costs, then their projects may end up not funded and there might be a very large difference in the results. See also the answer to Comment 2."}, {"review_id": "DcIDmRTI8Y", "reviewer": "Reviewer_aPJA", "summary": "This paper studies a \"meta game\" of participatory budgeting: when all the preference is known, what is a stable pricing for each alternatives if their makers are self-interested? It use a game theoretical approach to address this question and analyze equilibria under different participatory budgeting rules and restricted or general preferences domains. Results vary from case to case. For example, the most popular alternative takes all in BasicAV, while rules that emphasizes more on fairness (such as MES) may have more averaged equilibrium. There are also many negative results where a stable outcome does not exists. The paper also provides experiements that supports the theoretical findings.", "questions": "1. How will exact ground truth / noisy information on voters' preferences affect the existence of an equilibrium? Do you at least have some guesses or conjectures?\n\n2. In remark 2.1, you mentioned that you complement MES by Phragmen rules to use up the budget as much as possible. Will this complementary process affect the equilibrium?\n\n3. In the second paragraph of the intro, there are sentences like \"Among 25% instances, half of them XXX; in another 50%, more than 30% YYY\". This kind of expression looks counterintuitive to me. Why not count the properties based on the whole dataset? \n\n4. I would like to hear more potential applications or insights this paper could give on future research or voting practices.", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strength:\nThe paper provides a very interesting perspective to examine PB mechanisms and games, different from the previous ones which focus on the vote itself. This inspires us to look into the problem more thoroughly. The theoretical characterizations are clean and complete, characterizing a wider range of common rules. I don't check most of the proofs, but some of them seem non-trivial to me. \n\nWeaknesses:\nThe paper indeed has many assumptions and restrictions in its modelling, which it also discusses in the introduction. I am generally satisfied with the second one (project do not affect approvals). Yet for the first one, I will expect more explanations. For example, it remains unclear to me whether a 100% percent sure Ground Truth versus a partial knowledge /noisy signal makes a different in the existence of equilibria.", "was_revised": true, "final_justification": "The author's response addresses my questions. I am happy to maintain a positive score.", "rebuttal": "REVIEWER'S COMMENT\n\n\n1. It remains unclear to me whether a 100% percent sure Ground Truth versus a partial knowledge /noisy signal makes a different in the existence of equilibria.\n\nANSWER: See answer to Question 1.\n\n\n\nQUESTIONS\n\n\n1. How will exact ground truth / noisy information on voters' preferences affect the existence of an equilibrium? Do you at least have some guesses or conjectures?\n\nANSWER: We conjecture that the noise in the information can have a strong impact on the equilibria, especially regarding the complexity of their computation. In particular, noise and partial information would require different equilibrium notions, possibly relaxed in some ways. We suspect that there are variants of partial information setting that would maintain many of our results (e.g., if the votes come from some known distribution), but we are quite certain that one can come up with definitions under which equilibria disappear completely. Nevertheless, we leave the answer to this question as a compelling direction for future research.\n\n2. In remark 2.1, you mentioned that you complement MES by Phragmen rules to use up the budget as much as possible. Will this complementary process affect the equilibrium?\n\nANSWER: In a typical setting, the MES-cost completion does not matter, because under NE MES-cost is exhaustive: Each project requests the full endowment from the voters that approve it (and did not yet spend their money on projects considered in previous iterations). The NE may not be exhaustive either if some voters do not approve any projects---which is very unlikely---or when a project's delivery cost is higher than the endowment held by the voters at the time when a given project is considered. In this latter case, the completion method can, indeed, affect the equilibrium (but one could also argue that in such a setting the project would withdraw, as it would have no chance of funding, and we would be back to an exhaustive equilibrium; that goes beyond our model, though).\n\n\n3. In the second paragraph of the intro, there are sentences like \"Among 25% instances, half of them XXX; in another 50%, more than 30% YYY\". This kind of expression looks counterintuitive to me. Why not count the properties based on the whole dataset?\n\nANSWER: These sentences look somewhat complicated because we compute fractions of three types. The first percentage regards the number of PB instance (in Wroclaw or in Pabulib overall), the second percentage refers to the number of projects within these PB instances, and the final percentage refers to the cost of these projects, as a fraction of the highest allowed cost. We will look for ways to express these statistics in a clearer way.\n\n4. I would like to hear more potential applications or insights this paper could give on future research or voting practices.\n\nANSWER: As far as insights go, we find the following three to be most important:\n\na) MES-cost leads to very different equilibria than MES-Apr (which, on the other hand, leads to similar resutls to Phragmen). Specifically, MES-cost leads to funding fewer, more expensive projects. This is important for city officials as handling fewer projects is easier logistically. In particular, we would suggest that if one wanted to focus on only a single MES variant, then looking at MES-cost is more appealing than looking at MES-apr. \n\nb) Looking at the Pabulib instances, typically projects undershoot their costs (in the sense that under a best response they could request significantly more, provided they would not discourage voters from supporting them). This means that, typically, proposers should focus on designing the best, most appealing projects, without overly worrying about the costs.\n\nc) Since MES-cost is typically exhaustive under an equilibrium, it might be interesting to see how the assumption on choosing equilibrium costs affects the complexity of various problems. For example, deciding if there is a tie under MES is NP-complete (L. Janeczko, P. Faliszewski, Ties in Multiwinner Approval Voting, IJCAI 2023) but does it remain NP-complete under NE costs?"}]

Author rebuttal:

Meta-review: The paper analyzed existence of PSNE of games of participatory budgeting under different rules and provided algorithms for experimental verifications in real-world PB data. 

Reviewers are all positive about the paper and engaged in discussions. They appreciated the interesting game theoretic angle of an important problem and the comprehensive theoretical and empirical analysis. Reviewers also raised relatively minor points, such as setting being specific and results being not all surprising, which prevents the paper from receiving higher recommendations.
Decision: Accept (poster)