July 25, 2024
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 \(\text{AV/Cost}\), \(\text{Phragm\'en}\), and Method of Equal Shares rules. Furthermore, we report an experimental study of strategic cost selection on real-life PB election data.
A certain city decided to implement participatory budgeting [1]–[3]. The city council fixed the budget and invited the citizens to propose projects that might be implemented, letting them know that the funding decisions will be made by voting. Soon, three groups of activists formed, one focused on cycling infrastructure, one committed to making the city greener, and one dedicated to improving the quality of life for senior citizens. Each group decided to submit a single project, but they quickly realized that they have many options to choose from. For example, cycling enthusiasts could propose repainting the markings on a few bike paths, which would be very cheap, or they could request one or more new bike paths, which would cost more, or—with the full available budget—they could greatly improve the whole biking infrastructure while also offering free bikes for rent. In other words, they could spend any amount of money on cycling (at least if it were above a certain necessary minimum) and the more they could get, the better a project they could offer. Not surprisingly, the other groups reached similar conclusions. But how much money could they ask for, realistically?
If the city had a long history of participatory budgeting elections, the activists could assess the level of support for their causes based on past experience. In our case, they simply ran a survey. While they could not ask about the support for specific projects—after all, they were not sure what to propose yet—they found out that many people would simply vote for biking-, ecology-, or seniors-oriented projects, irrespecitve of their costs; they simply wanted improvements on these fronts (or even several of them). The survey showed that biking enthusiasts have the largest vote share, but other groups also had strong support.
With this information in hand, choosing a project’s cost largely depends on the voting rule used. For example, if the city used the \(\text{BasicAV}\) rule,1 which greedily selects those projects that are approved by the largest numbers of voters (provided they still fit in the remaining budget), then the biking enthusiasts could have their dream project funded. On the other hand, if the city were to use a proportional rule, such as the Method of Equal Shares (\(\text{MES}\)) [5], [6] or \(\text{Phragm\'en}\) [7], [8], then each group would have to analyze how the other ones might act, and choose their strategies based on that. Our goal is to analyze this game-theoretic nature of project cost selection under various participatory budgeting rules (in particular, our work is different from that of [9], who consider how voters pool their funds; see also the work of [10]).
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). Each project is controlled by a different proposer choosing its cost so that it is as high as possible, while ensuring that the project is selected.2 However, each project also has a 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. Importantly, whether a voter approves a project or not, does not depend on its cost. The projects are chosen according to a given rule, such as \(\text{BasicAV}\), \(\text{AV/Cost}\), \(\text{Phragm\'en}\), or \(\text{MES}\) (see for details). In other words, we consider a game where project proposers (or, for simplicity, the projects) are the players, project costs are their strategies, and costs of selected projects (minus their delivery costs) are their payoffs. We analyze whether these games have pure Nash equilibria and, if so, what costs are reported under these equilibria. Studying strategic cost selection is also a natural direction in market analysis and is present, e.g.,in the context of the Hotelling-Downs model (e.g.,in the work of [11]).
Naturally, our game presents a simplified view of reality. However, due to abstracting away from excessive complexities, our study led to finding interesting, and yet technically challenging to identify, basic phenomena. By this our model lays the foundations and sets expectations for more sophisticated scenarios. Multiple natural extensions of our games will become apparent, after we explain below our most important assumptions and their limitations:
In real-life PB there typically is a period of time during which one can propose projects and their costs. During this period, proposers are not necessarily aware of other submitted projects, but if two proposers do realize that their projects are similar, they might, for example, merge them or present them as less related. By fixing the set of project, our model is not capable of covering such dynamics.
While analyzing imperfect or probabilistic knowledge scenarios is beyond the scope of our model, in reality, neither the accurate identities of the voters nor their votes are available to project proposers at the time of submitting the projects. At best, one might suspect what level of support a project would get based on past experience or polls.
Our games are not suited to reflect that some voters might base their approval decisions on project costs and, for example, refuse to vote for projects that are either too cheap or too expensive. However, notably, such an effect is debatable and seems to depend on a voting rule in use [2], [12]. Further, performing the value-for-money analysis by voters is emprically cognitively costly; see e.g., the experimental study of [13].
Relaxing any of our assumptions would give rise to a more general class of games. As much as such models are interesting, they go far beyond the the scope of our paper. For example, allowing the proposers to cooperate, would require to apply techniques and solution concepts from coalitional game theory, whereas dropping the common knowledge assumption incurs modeling the uncertainty of information. As we initiate the study of strategic cost selection in participatory budgeting, we feel it is best to start with a clean, simple model, to obtain a baseline.
We initiate a study of strategic behavior of project proposers in the context of participatory budgeting. We do so by defining a new class of cost games and analyzing the existence of pure Nash equilibria under various participatory budgeting rules and types of votes (such as plurality ones, where each voter approves a single project, or party-list, and unrestricted ones, which have increasingly more complex structure), under various delivery costs (considering the cases in which they are equal to zero or are arbitrary), and under various tie-breaking orders. Among others, we find that \(\text{MES}\) with cost utilities always has equilibria irrespective of tie-breaking, as opposed to \(\text{AV/Cost}\), \(\text{Phragm\'en}\), and \(\text{MES}\) with approval utilities.
We supplement our theoretical study with an experimental analysis of Nash equilibria in real-life scenarios from Pabulib [14]. One of our findings is that \(\text{Phragm\'en}\) and \(\text{MES}\) based on approval utilities are very different from \(\text{MES}\) based on cost utilities. The former two rules lead to a smoother distribution of costs, with many cheap projects, and the latter to fewer, more expensive projects.
We define a PB instance (also sometimes referred to as a PB election) as a tuple \(E=(P,V,B,\mathit{cost})\), where \(P=\{p_1, \dots, p_m\}\) is a set of projects, \(V= \{v_1, \dots, v_n \}\) is a set of voters, \(B\in {\mathbb{R}}_+\) is the available budget, and \(\mathit{cost}\colon P \rightarrow {\mathbb{R}}_+\) is a function specifying the cost of each project. Each voter \(v_i\) casts a nonempty approval ballot \(A(v_i) \subseteq P\), containing the set of projects that he or she approves (see, for example, the work of [13] for a discussion of other ballot formats). Note that a 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(\cdot)\) notation so that for a project \(p_i\), \(A(p_i)\) is the set of voters that approve \(p_i\). Then, \(|A(p_i)|\) is the approval score of \(p_i\). For each project \(p_i\), we assume that \(|A(p_i)| \geq 1\). Given a subset of projects \(P'\), we let \(\mathit{cost}(P')\) be their total cost, that is, \(\mathit{cost}(P') = \sum_{p' \in P'}\mathit{cost}(p')\).
Further, each PB instance comes with a tie-breaking order \(\succ\) over the projects, used by the PB rules to resolve internal ties. While tie-breaking can have significant influence on voting [15], [16] and PB [4], and can happen fairly often in small elections [17], in large-enough PB instances we do not expect many of them (see, for example, the work of [18] for a discussion of the likelihood of ties in large ordinal elections).
A PB rule is a function \(f\) that for some PB instance \(E=(P,V,B,\mathit{cost})\) outputs a set \(f(E) \subseteq P\) of projects, with total cost not exceeding the budget. We refer to the projects in \(f(E)\) as winning (or, alternatively, as selected or funded). Note that our rules are resolute, that is, their outcomes are unique. We focus on the following rules, denoting by \(E = (P,V,B,\mathit{cost})\) the instance we consider:
It starts with \(W = \emptyset\) and considers all the projects in the order of their nonincreasing approval scores (with ties broken using \(\succ\)), inserting a considered project \(p\) into \(W\) if \(\mathit{cost}(W \cup \{p\}) \leq B\). When done, it outputs \(W\).
It is like \(\text{BasicAV}\), except that for each project \(p\) it computes its approval-to-cost ratio \(\frac{|A(p)|}{\mathit{cost}(p)}\) and considers the projects in the nonincreasing order of these values.
\(\text{Phragm\'en}\) starts with \(W = \emptyset\) and fills it as follows. Initially, the voters have empty virtual bank accounts, but they continuously earn money at the rate of one unit of budget per one unit of time. When there is a project \(p\) such that the voters who approve it have \(\mathit{cost}(p)\) funds and the project is within the remaining budget (that is, \(\mathit{cost}(W \cup \{p\}) \leq B\)), these voters purchase it, that is, \(p\) is included in \(W\), the bank accounts of voters in \(A(p)\) are reset to zero, and \(p\) is removed from consideration. If \(\mathit{cost}(W \cup \{p\}) > B\), then \(p\) is removed from consideration without being included in \(W\). If several projects could be purchased simultaneously, the rule picks one using the tie-breaking order. The rule stops and outputs \(W\) when all projects are removed from consideration.3
First, each voter receives the same amount \(\frac{B}{|V|}\) of money. Then we let \(W = \emptyset\) and proceed iteratively: Within each iteration, for each project \(p\) not in \(W\) we compute its affordability coefficient \(\alpha_p\) as the smallest number such that the following holds (\(b_i\) is the money that voter \(v_i\) currently has): \[\label{eq:mes} \textstyle \sum_{v_i \in A(p)} \min( b_i, \alpha_p \cdot \mathit{cost}(p)) = \mathit{cost}(p).\tag{1}\] If no such value exists (that is, the voters approving \(p\) cannot afford it) then we set \(\alpha_p = \infty\). If \(\alpha_p = \infty\) for all projects not in \(W\), then we terminate and output \(W\). Otherwise, we choose project \(p'\) with the lowest affordability coefficient (using the tie-breaking order, if needed), include \(p'\) in \(W\), and take \(\alpha_{p'} \cdot \mathit{cost}(p')\) money from each voter in \(A(p')\) (or all the remaining funds, if the voter had less than \(\alpha_{p'}\cdot \mathit{cost}(p')\)). Due to the use of \(\mathit{cost}(p)\) in Equation 1 , this variant of \(\text{MES}\) is also called \(\text{MES}\) with cost utilities.4
This rule, which was introduced by the same authors as \(\text{{MES\text{-}Cost}}\), works in the same way, except that it replaces Equation 1 with: \[\textstyle \sum_{v_i \in A(p)} \min( b_i, \alpha_p ) = \mathit{cost}(p).\] So, while in \(\text{{MES\text{-}Cost}}\) the affordability coefficients are between \(0\) and \(1\), under MESApr they can be as large as \(B\).
Remark 1. Both considered variants of \(\text{MES}\) might output a set of projects that can be extended without exceeding the budget. Following [6], in our experiments we use \(\text{Phragm\'en}\) completion: When a \(\text{MES}\) variant finishes, we extend its output by running \(\text{Phragm\'en}\) with voters’ bank accounts initiated with their then-current amounts of money. This defines the \(\text{MES\text{-}Cost/Ph}\) and \(\text{MES\text{-}Apr/Ph}\) rules.
Many authors also study other PB rules (see, for example, the works of [2], [19], [20]); for an overview we point to the works of [3] and [21] (the latter regards multiwinner elections, where projects have unit costs). \(\text{BasicAV}\) is commonly used in practice, \(\text{{MES\text{-}Cost}}\) also was recently used by several cities (see https://equalshares.net), whereas the other rules are mostly studied theoretically.
From time to time we focus on plurality profiles, where each voter approves exactly one project, and on party-list profiles, where the projects are grouped into “parties” and each voter approves all projects from a single party. Some cities require plurality profiles (such as Wrocław, Poland; see the datasets in Pabulib [14]) whereas the party-list ones are interesting theoretically.
Definition 1. Consider a set 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_i)| = 1\) for each voter \(v_i\), (2) party-list preferences, if either \(A(v_i) = A(v_j)\) or \(A(v_i) \cap A(v_j) = \emptyset\) for each two voters \(v_i\) and \(v_j\).
For a party-list profile and a project \(p\), by \({\mathit{party}}(p)\) we mean the set of projects approved by the same voters as \(p\). illustrates the types of preferences.
Figure 1: Examples of plurality (left), party list (middle), and unrestricted (right) preferences. Projects are depicted as boxes. Each voter approves those projects that are drawn directly above.
In this section we define our main object of study, participatory budgeting cost games (PB games). Formally, a PB game is a tuple \((P,V,B,d)\), where \(P\) 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\colon P \rightarrow {\mathbb{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 \(p_i\), \(d(p_i) \leq B\). In this game, the projects are the players and each of them needs to report its cost. That is, a strategy profile is a tuple \(\mathbf{c}=(c_1, \dots, c_n)\), with a cost \(c_i \in {\mathbb{R}}_+\) for each project \(p_i\). As is standard, we write \((\mathbf{c}_{-i},c')\) to denote a strategy profile that is identical to \(\mathbf{c}\) except that project \(p_i\) reports cost \(c'\). We often write \(\mathbf{c}(p_i)\) to denote the cost reported by \(p_i\) under strategy profile \(\mathbf{c}\) (and we use strategy profiles as \(\mathit{cost}\) functions in PB instances).
Let us fix a PB rule \(f\) and a PB game \(G = (P,V,B,d)\). For a strategy profile \(\mathbf{c}\), the associated PB instance is \(E(\mathbf{c}) = (P,V,B,\mathbf{c})\) and the payoff of each project \(p_i \in P\) is: \[u_{i}(\mathbf{c}) = \begin{cases} \mathbf{c}(p_i) - d(p_i) & \text{ if p_i \in f\big(E(\mathbf{c})\big),}\\ 0 & \text{ otherwise}. \end{cases}\] The interpretation is as follows: Each project \(p\) has a minimal delivery cost \(d(p)\), which is the lowest price under which it can be implemented. Yet, with more money the project can be better and the proposer prefers this. Our utility costs are defined to implement this preference. In particular, the proposers do not receive funds equal to the utility values. As a special case, we often consider delivery costs equal to zero.
For a PB rule \(f\) and a PB game \(G = (P,V,B,d)\), we are interested whether this game has Nash equilibria (NE). We say that a strategy profile \(\mathbf{c}\) for this game is a Nash equilibrium under \(f\) (is an \(f\)-NE) if for every project \(p_i \in P\) and every cost \(c' \in {\mathbb{R}}_+\) it holds that \(u_{i}(\mathbf{c}) \geq u_i(\mathbf{c}_{-i},c')\). In other words, no project has a profitable deviation, that is, it cannot benefit by reporting a different cost than that chosen in an \(f\)-NE (as long as no other project changes its reported cost).
Example 1. Take \(\text{AV/Cost}\) and a PB game with projects \(p_1\), \(p_2\), voters \(v_1, \ldots, v_5\), budget \(10\), and zero delivery costs. We have \(A(p_1) = \{v_1,v_2\}\) and \(A(p_2) = \{v_3,v_4,v_5\}\), so this is a plurality profile. Then, the strategy profile \(\mathbf{c}\) where \(\mathbf{c}(p_1) = 4\) and \(\mathbf{c}(p_2) = 6\) is an NE. Indeed, according to \(\text{AV/Cost}\), under these costs \(p_1\) and \(p_2\) are tied, because \(\frac{|A(p_1)|}{\mathbf{c}(p_1)} = \frac{|A(p_2)|}{\mathbf{c}(p_2)} = \frac{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. If it reports a higher cost, it is not selected and its utility drops to zero.
From time to time we use specific approval-to-delivery-cost (A/D) tie-breaking orders, which favor projects with larger ratios of their approvals to delivery costs. So, \(\succ\) is A/D if projects with zero delivery costs are ranked highest, while \(\frac{A(p_i)}{d(p_i)} > \frac{A(p_j)}{d(p_j)}\) implies \(p_i \succ p_j\) if \(d(p_i) \cdot d(p_j) >0\). Since some projects may have equal approval-to-delivery cost ratios, there may be several different A/D tie-breaking orders in a given setting.
ballots | Plurality | PartyList | Unrestricted | |||
\(d\equiv 0\) | \(\textrm{arb. } d\) | \(d\equiv 0\) | \(\textrm{arb. } d\) | \(d\equiv 0\) | \(\textrm{arb. } d\) | |
\(\text{BasicAV}\) | ||||||
\(\text{AV/Cost}\) | \(\raisebox{1px}{\blacksquare}^\dagger\) | \(\raisebox{1px}{\blacksquare}^\dagger\) | ||||
, | , | , | ||||
\(\text{Phragm\'en}\) | \(\raisebox{1px}{\blacksquare}^\dagger\) | ? | ||||
MESApr | ||||||
, | ||||||
\(\text{{MES\text{-}Cost}}\) | ||||||
Our theoretical results, summarized in , focus on the existence of NE in PB games. We mostly show that either: (1) There always is an equilibrium, for any tie-breaking order; (2) There always is an equilibrium for some A/D tie-breaking order; or (3) There is a PB game with no equilibrium for any tie-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), is incomparable to a result of type (2), and implies that a result of type (1) does not exist. Pragmatically, it is most important to know whether a result of type (1) holds or not in a given setting; the other types of results indicate various levels of bad news that we may be facing regarding the existence of Nash equilibria.
We are interested in strategy profiles that are proportional in some way (for a discussion of fairness in PB see, for example, the works of [22] and [23], as well as the works defining \(\text{MES}\) and \(\text{Phragm\'en}\)). Below we define a basic type of such a profile, where project costs are proportional to the numbers of approvals they get.
Definition 2 (Approval-Proportional Strategy Profile). Consider a PB game with projects \(P = \{p_1, p_2, \ldots, p_m\}\). We say that strategy profile \(\mathbf{ap}\) is approval-proportional* if for each project \(p\) it holds that \(\mathbf{ap}(p) = B\cdot \frac{|A(p)|}{ \sum_{p' \in P} |A(p')|}\).*
Under plurality preferences, the approval-proportional profile is a natural solution for rules focused on proportionality. For more involved settings, other profiles may be more appropriate (see, for instance, \(\text{{MES\text{-}Cost}}\) and ).
We start our analysis by considering \(\text{BasicAV}\). There is a simple equilibrium where the project with most approvals (preferred in the tie-breaking order, if there is more than one such project) requests the full budget amount.
Proposition 1. For each PB game and each internal tie-breaking order \(\succ\), there is a \(\text{BasicAV}\)-NE where the project with most approvals (best with respect to \(\succ\)) reports cost \(B\).
Proof. Take a PB game and a strategy profile \(\mathbf{c}\) as described in the statement, and let \(p\) be the project such that \(\mathbf{c}(p) = B\). If a project other than \(p\) increases its cost, it still is not selected so this is not a beneficial move. If \(p\) 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, \(\mathbf{c}\) is a \(\text{BasicAV}\)-NE. ◻
In fact, we can additionally observe that the most popular project reports the cost \(B\) (and is selected) under every \(\text{BasicAV}\)-\(\textit{NE}\). Hence, indicates that proposers of projects receiving many approvals have incentive to overstate their costs. Furthermore, proposers of smaller, less popular projects, have an incentive to bundle them together (indeed, in some cities one can observe projects of the form “improvement of infrastructure in areas \(X\), \(Y\), and \(Z\),” which suggests such bundling). So, unsurprisingly, \(\text{BasicAV}\) equilibria in our games are disproportional, highlighting known deficiencies of this rule.
Some shortcomings of \(\text{BasicAV}\) are remedied by \(\text{AV/Cost}\), for which the approval-proportional strategy 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. Then, \(\mathbf{ap}\) is the only equilibrium profile.
Proposition 2. Take a PB game and the corresponding strategy profile \(\mathbf{ap}\). If \(d(p) \leq \mathbf{ap}(p)\) for each project \(p\), then if a profile \(\mathbf{c}\) is an \(\text{AV/Cost}\)-NE for this game, then (1) \(\sum_{p \in P} \mathbf{c}(p) = B\), and (2) \(\text{AV/Cost}\) funds all the projects.
Proof Sketch. Let each project \(p\) have \(d(p) \leq \mathbf{ap}(p)\) and let \(\mathbf{c}\) be a Nash equilibrium. Then, it must be that \(\sum_{p \in P}\mathbf{c}(p) \geq B\). Let \(\sum_{p \in P}\mathbf{c}(p) > B\). As \(\mathbf{c}\) is an equilibrium, all of the funded projects are chosen with the same score and their costs amount to \(B\), while being higher than those reported in \(\mathbf{ap}\). So, some non-funded project \(p\) could be funded with the cost higher than \(d(p)\) — contradiction. Hence, \(\sum_{p \in P} \mathbf{c}(p) = B\). Point \((2)\) follows from the exhaustivity of \(\text{AV/Cost}\). ◻
Proof. Let the notation be as in the statement of the proposition. In the beginning we observe that if \(\sum_{p \in P}\mathbf{c}(p) < B\), then \(\text{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 \(\mathbf{c}\) is not an equilibrium.
Next, let us assume that \(\sum_{p \in P}\mathbf{c}(p) > B\). Let \(P_{\mathit{won}}\) and \(P_{\mathit{lost}}\) be sets of projects that, respectively, are and are not funded. By our assumption, we know that \(P_{\mathit{lost}}\) must be nonempty, and we also note that \(P_{\mathit{won}}\) must be nonempty. Naturally, \(\sum_{p \in P_{\mathit{won}}}\mathbf{c}(p) \leq B\). For each two projects \(p_i\) and \(p_j\) in \(P_{\mathit{won}}\), it must be the case that \(\frac{|A(p_i)|}{\mathbf{c}(p_i)} = \frac{|A(p_j)|}{\mathbf{c}(p_j)}\). For example, if we had \(\frac{|A(p_i)|}{\mathbf{c}(p_i)} > \frac{|A(p_j)|}{\mathbf{c}(p_j)}\) then \(\text{AV/Cost}\) would consider \(p_i\) prior to \(p_j\) and, consequently, it would be beneficial for \(p_i\) to increase its reported cost by a small-enough amount so that it would still be considered (and selected) prior to \(p_j\). This would contradict the assumption that \(\mathbf{c}\) is an equilibrium. Next, since \(\sum_{p \in P}\mathbf{ap}(p) = B\), there must be some project \(p'\) in \(P_{{\mathit{won}}}\) such that \(\mathbf{c}(p') > \mathbf{ap}(p') \geq d(p')\) (otherwise, if each project \(p' \in P_{\mathit{won}}\) reported at most \(\mathbf{ap}(p')\), then any project \(p \in P_{\mathit{lost}}\) would be selected after reducing its cost to \(\mathbf{ap}(p)\), so \(\mathbf{c}\) could not have been \(\text{NE}\)). Further, by definition of the approval-proportional profile, for every project \(p \in P\), we have that \(\frac{|A(p)|}{\mathbf{ap}(p)}\) is the same value and, so, for every project \(q \in P_{\mathit{lost}}\) it holds that \(\frac{|A(q)|}{\mathbf{ap}(q)} = \frac{|A(p')|}{\mathbf{ap}(p')} > \frac{|A(p')|}{\mathbf{c}(p')}\). This means that every project \(q \in P_{\mathit{lost}}\) can improve its utility by reporting cost \(\mathbf{ap}(q)\) and being selected. This contradicts the assumption that \(\mathbf{c}\) is an equilibrium.
Thus it must be the case that \(\sum_{p \in P}\mathbf{c}(p) = B\), which implies that \(\text{AV/Cost}\) selects all projects. ◻
Proposition 3. Irrespective of a tie-breaking order, \(\mathbf{ap}\) is the only \(\mathop{\mathrm{AV/cost}}\)-NE if \(d(p) \leq \mathbf{ap}(p)\) for all \(p \in P\).
Proof. Consider a PB game \((P, V, B, d)\) such that for every \(p_i \in P\) it is true that \(d(p) \leq \mathbf{ap}(p)\).
We argue that strategy \(\mathbf{c}= \mathbf{ap}\) is a \(\text{AV/Cost}\)-NE. Note that the sum of the reported costs in \(\mathbf{c}\) 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_i \in \mathbf{ap}\) and assume that reporting a cost \(c'_i > c_i\) leads to a better payoff. This means that \(p_i\) is funded in the modified election \(E' = (P, V, B,(\mathbf{c}_{-i}, c_i') )\) , that is, \(p_i \in \mathop{\mathrm{AV/cost}}(E')\). Additionally, since by we know that \(\sum_{j \in |P|} c_j = B\), it immediately follows that \(c_i' + \sum_{j \in |P|\setminus\{i\}} c_j > B> \sum_{j \in |P|\setminus\{i\}} c_j\). It is also the case that for each \(j \in |P|\), \(\frac{|A(P_j)|}{c_j} > \frac{|A(P_i)|}{c'_i}\). Hence, in particular, in the run of \(\mathop{\mathrm{AV/cost}}\) for \(E'\), all projects are considered before \(p_i\). Since all of these project are selected, by the time the procedure starts considering \(p_i\), the remaining budget is smaller than \(c_i'\), so \(p_i \not\in \mathop{\mathrm{AV/cost}}(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 \(\succ\).
We now argue that every strategy profile \(\mathbf{c}{}\) other than \(\mathbf{ap}\) is not a \(\mathop{\mathrm{AV/cost}}\)-NE. To this end, we take such a profile \(\mathbf{c}{}\) and assume towards contradiction that it is a \(\mathop{\mathrm{AV/cost}}\)-NE. Observe that since \(\mathbf{c}{} \neq \mathbf{ap}\), there exist two distinct projects \(p_i\) and \(p_j\) such that \(\frac{|A(p_i)|}{c_i} \neq \frac{|A(p_j)|}{c_j}\). Hence one of the projects is considered earlier than the other; we assume without loss of generality that \(p_i\) is considered before \(p_j\). Notably, as \(\mathbf{c}\) is (by our assumption) a \(\mathop{\mathrm{AV/cost}}\)-NE, by , we know that \(\{p_i, p_j \} \subseteq \mathop{\mathrm{AV/cost}}(\mathbf{c}{})\). This implies, however, that \(p_i\) can report a slightly higher price \(c_i'\) and still be selected by \(\mathop{\mathrm{AV/cost}}{}\) thus obtaining a better payoff. Formally, there exists a \(c_i' > c_i\) resulting in the profile \((c_i', \mathbf{c}{}_{-i})\) in which \(\frac{|A(P_i)|}{c_i'} < \frac{|A(P_j)|}{c_j}\). So, \(p_i\) is (still) considered by \(\mathop{\mathrm{AV/cost}}\) before \(c_j\) and the deviation is small enough (that is, \(c_i'-c_i < c_j\)) to guarantee that \(p_i\in \mathop{\mathrm{AV/cost}}(( \mathbf{c}{}_{-i}, c_i'))\). So, \(\mathbf{c}\) is not a \(\mathop{\mathrm{AV/cost}}\)-NE; a contradiction. Again, due to , in each Nash equilibrium, all projects are selected to be funded. Hence, our proof works for every possible tie-breaking. ◻
If (some of) the delivery costs are higher than the costs implied by the approval-proportional strategy, then the situation becomes more complicated. As we show, it is no longer true that an NE exist for all internal tie-breaking orders.
Example 2. Take a PB game \((P, V, B, d)\) with plurality ballots, where \(P=\{p_1, p_2 \}\), \(|A(p_1)| = |A(p_2)|= 5\), \(B= 10\), \(d(p_1) = 0\), \(d(p_2) = 6\), and the tie-breaking order is \(p_2 \succ p_1\). Assume that \(\mathbf{c}\) is an \(\text{AV/Cost}\)-NE. Consider two cases: (1) If \(\mathbf{c}(p_2) \geq 6\), then either (a) \(\mathbf{c}(p_1) \geq \mathbf{c}(p_2)\), where it is better for \(p_1\) to report a cost lower than \(\mathbf{c}(p_2)\) (otherwise \(p_2\) is selected before \(p_1\) and there is no budget left for \(p_1\)), or (b) \(\mathbf{c}(p_1) < \mathbf{c}(p_2)\) and it is better for \(p_1\) to increase its cost (keeping it below \(\mathbf{c}(p_2)\)). (2) If \(\mathbf{c}(p_2) < 6\), then either \(p_2\) is chosen and it prefers to report cost \(6\) (otherwise its payoff is \(\mathbf{c}(p_2)-d(p_2) < 0\)), or \(p_2\) is not selected, meaning that \(\mathbf{c}(p_1) < \mathbf{c}(p_2)\) and it is better for \(p_1\) to increase its cost (keeping it below \(\mathbf{c}(p_2)\)). Yet, if \(p_1 \succ p_2\), then \((6,6)\) is an equilibrium, where only \(p_1\) is funded: Both projects would decrease their payoff by lowering costs and they would not benefit by increasing their costs (\(p_1\) would no longer be selected, and \(p_2\)’s payoff would not change).
Yet, there always is a tie-breaking order yielding an NE.
Theorem 1. For each PB game and A/D tie-breaking order there is an \(\text{AV/Cost}\) computable in polynomial time.
Proof Sketch. The algorithm that we propose computes the claimed profile \(\mathbf{c}\). It runs in iterations. Starting from the situation where each project reports its delivery cost, in each iteration the algorithm selects a 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 reach the 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 full proof is in the appendix. ◻
Figure 2: Finding a Nash equilibrium for \(\mathop{\mathrm{AV/cost}}\).
Proof. Our computes the claimed \(\text{AV/Cost}\).
Let us fix a PB game \(G = (P, V, B, d)\) and some corresponding A/D tie-breaking \(\succ\), as specified in the theorem statement. We first introduce helpful notation and discuss \(\succ\) in more detail. Then, we proceed with presenting a high-level description of that finds the claimed \(\text{AV/Cost}\), which we refer to as \(\mathbf{c}\). Eventually, we prove the correctness of the algorithm using and conclude with proving itself.
Recall that by definition \(\succ\) orders the projects \(p_i\) nonincreasingly according to approval-to-delivery-cost ratios \(\frac{|A(p_i)|}{d(p_i)}\). Crucially, \(\succ\) is always compatible with the order in which \(\text{AV/Cost}\) considers the projects assuming they report their delivery costs, that is, where for all \(p_i \in P\), \(c(p_i) = d(p_i)\). In what follows, for each set of projects \(X \subseteq P\), each \(p_i \in X\), and the corresponding suborder \(\succ_X\) of \(\succ\), we write \(\mathop{\mathrm{pos}}_X(p_i)\) to denote the position of \(p_i\) in \(\succ_X\). Analogously, for some natural number \(x \leq |X|\), we denote by \(\mathop{\mathrm{top}}_X(x)\) the set of top \(x\) projects according to \(\succ_X\).
constructs the \(\text{AV/Cost}\) \(\mathbf{c}\) iteratively, starting from strategy \(\mathbf{c}_0\) in which each project reports its delivery cost (). In each iteration of the while loop, the algorithm selects a 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 \(\text{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 is repeated for the remaining projects, whose prices have not been increased so far. Such projects, albeit worse regarding the delivery-cost-to-support ratio, can still benefit from the increase. The algorithm outputs \(\mathbf{c}\) if one of the updates step lead to the situation in which the whole budget is used or when there is no more projects underreporting their costs.
In the following more detailed description of , we use the notation as specified in the pseudocode and whenever the value \(k\) in an iteration of the loop is smaller than \(|P'|\), we define \(p^* = \mathop{\mathrm{pos}}_{P'}(k+1)\) (assuming the value of \(P'\) from the corresponding iteration). Central to is the while loop. Importantly, due to our basic assumption on the delivery costs of the projects (i.e., that for each \(p \in P\), \(d(p) \leq B\)), initially set \(P_\textrm{p}\) is not empty (), so the while loop runs at least once. of the algorithm guarantees that in each iteration the loop sets the values of \(T\) and \(k\) to: \[\begin{align} \tag{2} &k < |P'| \;\;\textrm{and}\;\; T = \frac{d(p^*)}{A(p^*)} \;\;\textrm{or}\\ \tag{3} &k < |P'| \;\;\textrm{and}\;\; T \cdot \sum_{p_j \in \mathop{\mathrm{top}}_{P'}(k)} |A(p_j)| = B^*, \;\; \textrm {or}\\ \tag{4} &k = |P'| \;\;\textrm{and}\;\; T \cdot \sum_{p_j \in \mathop{\mathrm{top}}_{P'}(k)} |A(p_j)| = B^*.\\ \end{align}\] The aforementioned case distinction is crucial for the following claim.
Claim 1. Right after executing in each iteration of the while loop of , it jointly holds that:
all projects from \(\mathop{\mathrm{top}}_{P'}(k)\) are funded under strategy profile \(\mathbf{c}\) and none of them has a profitable deviation for \(\mathbf{c}\);
either \(k = |P'|\) or there exists a project \(p^* = \mathop{\mathrm{pos}}_{P'}(k+1)\) that is not funded and has no profitable deviation for profile \(\mathbf{c}\);
no project from \(\mathop{\mathrm{top}}_{P'}(k)\) has a profitable deviation for each strategy profile \(\mathbf{c}'\) that differs from \(\mathbf{c}\) only by strategies of projects in \(P_\textrm{p}\) in a way that, for each \(p\in P_\textrm{P}\), \(\mathbf{c}'(p) \geq \mathbf{c}(p)\);
either \(k = |P'|\) or the project \(p^* = \mathop{\mathrm{pos}}_{P'}(k+1)\) has no profitable deviation for each strategy profile \(\mathbf{c}'\) that differs from \(\mathbf{c}\) only on strategies of projects in \(P_\textrm{p}\) such that, for each \(p\in P_\textrm{P}\), \(\mathbf{c}'(p) \geq \mathbf{c}(p)\);
no project in \(P \setminus P_\textrm{p}\) has a profitable deviation in \(\mathbf{c}\).
Note that ends when executing makes \(P_\textrm{p}\) empty. So, by of the algorithm returns profile \(\mathbf{c}\) which is a Nash equilibirum. Clearly, in each iteration \(k>0\), so at least one element is removed from \(P_\textrm{p}\) in every iteration of the loop. Consequently, the algorithm always ends and thus it is correct. To conclude the whole proof it remains to show that indeed holds.
Proof of . We provide an inductive argument over the iterations of the while loop of . For the sake of the argument’s simplicity, instead of thinking of \(\text{AV/Cost}\) considering projects in nonincreasing order of approval-to-cost ratio, we say that it considers projects in nondecreasing 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 hold.
. We first show that each \(p \in \mathop{\mathrm{top}}_{P'}(k)\) is funded in election \(E(\mathbf{c}{})\). Let us denote as \(t(p)\) the ratio \(\frac{\mathbf{c}(p)}{|A(p)|}\). Due to and the following foreach loop, we know that every project in \(\mathop{\mathrm{top}}_{P'}(k)\) is tied to be considered by \(\text{AV/Cost}\) due to the same cost-to-approval ratio \(T\). So, if \(k = |P'|\), then all projects in \(P_\textrm{p} = P\) are tied for consideration. Since, by all project costs sum up to \(B^* = B\), the claim holds. We follow assuming that \(k<|P'|\). In this case, shows that \(p^*\) has cost-to-approval ratio \(t(p^*) \geq T\). Recall that \(\succ\) orders projects nondecreasingly with respect to their cost-to-approval ratio assuming \(\mathbf{c}_0\) and that \(\mathbf{c}\) differs from \(\mathbf{c}_0\) only in strategies of projects in \(\mathop{\mathrm{top}}_{P'}(k)\). Hence, \(p^*\) precedes in \(\mathbf{c}\) each project except of those in \(\mathop{\mathrm{top}}_{P'}(k)\) and all projects in \(\mathop{\mathrm{top}}_{P'}(k)\) are considered before \(p^*\) (the latter holds even in the case of \(t(p^*) = T\) due to \(\succ\)). Eventually, guarantees that the cost of all projects in \(\mathop{\mathrm{top}}_{P'}(k)\) does not exceed the budget. Knowing that, we show that no project in \(\mathop{\mathrm{top}}_{P'}(k)\) has a profitable deviation in \(\mathbf{c}\). To prove it by contradiction, let us assume that some player \(p_i \in \mathop{\mathrm{top}}_{P'}(k)\) has a profitable deviation by reporting cost \(c_i' > c_i\); the opposite case of \(c_i' < c_i\) trivially does not yield a payoff improvement for \(p_i\). As a result, \(p_i\) has to be funded in the corresponding election \(E((\mathbf{c}{}_{-i}, c_i'))\). In this election, \(p_i\) has cost-to-approval ratio \(t' = \frac{c_i'}{|A(p_i)|} > T\). We further split our analysis into the three cases from .
Assuming , project \(p^*\) is also funded in election \(E'\), as it is considered before \(p_i\) due to \(t' > T\). Hence, the funded projects cost at least \[\begin{align} T \cdot \sum_{\substack{p_j \in \mathop{\mathrm{top}}_{P'}(k) \\ p_j \neq p_i}} |A(p_j)| + t'|A(p_i)| + T|A(p^*)| > \\ T \cdot \sum_{p_j \in \mathop{\mathrm{top}}_{P'}(k+1)} |A(p_j)|. \end{align}\] However, due to , we know that \(B^* = B< T \sum_{p_j \in \mathop{\mathrm{top}}_{P'}(k+1)} |A(p_j)|\), which gives the contradiction with the fact that \(p_i\) is funded.
Suppose or hold. Then, given our assumption that \(p_i\) is funded, the total cost of funded projects is \[\begin{align} T \cdot \sum_{\substack{p_j \in \mathop{\mathrm{top}}_{P'}(k)\\ p_j \neq p_i}} |A(p_j)| + t'|A(p_i)| > \\ T \sum_{p_j \in \mathop{\mathrm{top}}_{P'}(k)} |A(p_j)| = B^* = B, \end{align}\] Here, the equality is due to the assumption of or ; which yields the sought contradiction.
. If \(k = |P'|\), then the statement trivially holds. Otherwise, let us consider \(p^*\) in the light of . Due to , we have that
\[\begin{align} B< T \sum_{p_j \in \mathop{\mathrm{top}}_{P'}(k+1)} |A(p_j)| = \\ T \sum_{p_j \in \mathop{\mathrm{top}}_{P'}(k)} |(A(p_j))| + d(p^*). \end{align}\] Hence, since all projects in \(\mathop{\mathrm{top}}_{P'}(k)\) are funded, \(p^*\) is not funded. Naturally, if \(p^*\) reports a cost bigger than \(d(p^*)\) it will not be funded even more, whereas reporting a cost lower than \(d(p^*)\) results in a worse payoff, which finishes the argument for, for . By the condition of , it immediately holds that all projects \(\mathop{\mathrm{top}}_{P'}(k)\) use up the whole budget. As a result, again, \(p^*\) is not funded and, analogously to the case of , \(p^*\) has no profitable deviation. We already observed that trivially holds for \(k = |P'|\), which subsumes .
. Observe that assuming strategy \(\mathbf{c}\), all projects in \(P_\textrm{p}\) are considered after all projects outside of \(P_\textrm{p}\) in election \(E(\mathbf{c})\). This is because order \(\succ\) is compliant with the order of considering the projects by \(\text{AV/Cost}\) and our modifications to the initial strategy profile \(\mathbf{c}\) do not change the order of considering projects (note that we let modified projects be tied for consideration with cost-to-approval ratio \(T\)). Furthermore, note that never decreases the reported costs of the projects and never considers the same project twice, so the projects in \(P_\textrm{p}\) will never be considered before the other ones as a result of further modifications of \(\mathbf{c}\). So, no modification of the profile \(\mathbf{c}{}\) that increases the costs for projects in \(P_\textrm{p}\) can influence the decision made for projects in \(\mathop{\mathrm{top}}_{P'}(k)\) or \(\mathop{\mathrm{top}}_{P'}(k+1)\) (depending on whether \(k<|P'|\)), as the latter are considered by \(\text{AV/Cost}\) earlier than projects in \(P_\textrm{p}\).
. Note that \(P \setminus P_\textrm{p}\) consists only of the following projects: (i) those removed in the foreach loop, that is, \(\mathop{\mathrm{top}}_{P'}(k)\); (ii) \(p^*\) if \(k < |P'|\); and (iii) those removed in . Regarding the first two groups, we have already shown that they do not have a profitable deviation for \(\mathbf{c}\). Let \(\hat{p}\) be \(\mathop{\mathrm{top}}_{P'}(k)\) if \(k < |P'|\) or, otherwise, let \(\hat{p}\) be \(p^*\). The last group \(Y\) consists of these projects \(p \in P'\), for which \(\hat{p} \succ p\) and whose \(d(p) > B^*\). Hence, by \(\succ\), these projects are considered after all projects in \(\mathop{\mathrm{top}}_{P'}(k) \cup \{\hat{p}\}\). However, projects in \(\mathop{\mathrm{top}}_{P'}(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 in \(Y\) has a profitable deviation.
Thus, we have established the base case and we move on to the induction step. Consider \(x>1\) and the \(x\)-th iteration of the while loop, assuming that the base case claims are met for the \((x-1)\)-th iteration. Due to the assumptions for the \((x-1)\)-th iteration together with the fact that our algorithm never changes the order \(\succ\) in which \(\text{AV/Cost}\) considers projects and that it never considers the same project twice, we can ignore all projects processed in previous \((x-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 \(B^*\) representing the remaining budget. Consequently, the arguments for carry on without changes for the \(x\)th iteration of the while loop. The claim from , however, needs more attention. Let \(Q^{(x-1)} = P \setminus P_\textrm{p}^{(x-1)}\) be the set of players without profitable deviations after the \((x-1)\)-th iteration of the loop. Note that \(P' = P_\textrm{p}^{(x-1)}\). We denote by \(R\) the set of projects, that are removed from the initial state of \(P_\textrm{p}\) by . That is, \(R\) consists of all these projecst that—due to and the argument for in the base case—have no profitable deviation in \(\mathbf{c}\). So, we have that \(P_\textrm{p} = P' \setminus R\). We now consider the set \(Q = P \setminus P_\textrm{p}\) of the projects for which we need to show that they have no profitable deviation. Putting the bits together, we observe the following: \[\begin{align} Q = &P \setminus P_\textrm{p} = P \setminus (P' \setminus R) = \\ &P \setminus (P_\textrm{p}^{(x-1)} \setminus R) = (P \cap R) \cup (P \setminus P_\textrm{p}^{(x-1)}). \end{align}\] Since \(P \cap R = R\), we obtained that \(Q = R \cup Q^{(x-1)}\) thus showing that the \(x\)-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 a result, we proved for the \(x\)-th iteration. ◻
Having proven , we completed the argument for the correctness of and . ◻
We conclude our analysis of \(\text{AV/Cost}\) by noting that, as shows, even for plurality preferences the costs of projects selected in an equilibrium can be far from using the entire budget. In fact, they can be arbitrarily far from it.
Proposition 4. For each integer \(\gamma >1\) there is a PB game with plurality preferences and \(\text{AV/Cost}\)-NE profile \(\mathbf{c}\) with the total cost of projects funded under \(\text{AV/Cost}\) at most \(\frac{B}{\gamma}\).
Proof. Take a natural \(\gamma > 1\) and consider a PB game \((P,V,B,d)\) where \(P= \{p_1, p_2, p_3 \}\), \(B= 10\), \(d(p_1) = d(p_2) = 0\), and \(d(p_3) = 10 - \frac{1}{2 \gamma}\). The voters have plurality ballots such that \(|A(p_1)|= |A(p_2)| = 1\) and \(A(p_3) = 20 \gamma -1\). We assume tie-breaking order \(p_1 \succ p_2 \succ p_3\). We claim that strategy profile \(\mathbf{c}\) such that \(\mathbf{c}(p_1) = \mathbf{c}(p_2) = \frac{1}{2 \gamma}\) and \(\mathbf{c}(p_3) = 10 - \frac{1}{2 \gamma}\) is a \(\text{Phragm\'en}\)-NE.
First, we see that if the projects reports costs as in \(\mathbf{c}\) then \(\text{Phragm\'en}\) selects \(p_1\) and \(p_2\). Indeed, we see that at time moment \(\frac{1}{2\gamma}\) the voters supporting each of the projects have exactly as much money as is need to purchase them. Due to tie-breaking, the singleton voters supporting \(p_1\) and \(p_2\) buy these projects and, then, there is not enough budget left for \(p_3\) and the rule finishes.
Second, we observe that no project can benefit by changing its strategy under \(\mathbf{c}\). Indeed, if either \(p_1\) or \(p_2\) decreased their cost, they would obtain lower payoff, and if either of them increased their cost, \(p_3\) would be funded instead and the payoff of the project that increased its cost would drop to zero. If \(p_3\) 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, \(\mathbf{c}\) is \(\text{Phragm\'en}\)-NE.
Finally, we have \(\mathbf{c}(p_1) + \mathbf{c}(c_2) = \frac{1}{\gamma}\), and as \(B = 10\), this is less than \(\frac{B}{\gamma}\). This concludes the proof. ◻
It is easy to verify that for plurality ballots \(\text{AV/Cost}\) and \(\text{Phragm\'en}\) are identical, that is, for every PB instance with plurality ballots (and the same internal tie-breaking) they output the same projects. Thus, the next corollary translates results from the previous section to the case of \(\text{Phragm\'en}\).
Corollary 1. For each PB game with plurality ballots, (a) if \(d(p) \leq \mathbf{ap}(p)\) for all \(p \in P\), then \(\mathbf{ap}\) is the only \(\text{Phragm\'en}\)-NE for every tie-breaking order; (b) otherwise, for an A/D tie-breaking order there is a \(\text{Phragm\'en}\)-NE (and there are PB games and tie-breaking orders with no \(\text{Phragm\'en}\)-NE).
Naturally, also holds for \(\text{Phragm\'en}\). So, there are games with equilibria for which \(\text{Phragm\'en}\) 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 each tie-breaking order. Intuitively, each project \(p\) reports cost proportional to the number of its approvals, divided by the size of its party.
Proposition 5. For every PB game with party-list ballots and zero delivery costs, there is the unique \(\text{Phragm\'en}\text{-}{\text{NE}}\) \(\mathbf{c}\), where for every project \(p\) we have \(\mathbf{c}(p) = B \cdot \frac{|A(p)|}{|V| \cdot |{\mathit{party}}(p)|}\).
Proof. Consider a PB game \(G\) and the strategy profile \(\mathbf{c}\) as defined in the statement of the proposition. We claim that \(\mathbf{c}\) is a \(\mathop{\mathrm{\text{Phragm\'en}}}\)-NE. First, we observe that under \(\mathbf{c}\) \(\mathop{\mathrm{\text{Phragm\'en}}}\) selects all the projects, so it is not beneficial for any of them to report a lower cost. On the other hand, if some project \(p\) reports a higher cost, this project is not selected by \(\mathop{\mathrm{\text{Phragm\'en}}}\). To see why this is the case, consider some project \(p\). Under \(\mathbf{c}\), the total cost of the projects in \({\mathit{party}}(p)\) is \(\frac{B\cdot|A(p)|}{|V|}\). Since 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 \(\frac{B}{|V|}\). This value is independent of \(p\) so, under \(\mathbf{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, it is never beneficial to increase a cost and so, \(\mathbf{c}\) is a \(\mathop{\mathrm{\text{Phragm\'en}}}\)-NE.
It remains to show that \(\mathbf{c}\) is the unique \(\text{Phragm\'en}\text{-}{\text{NE}}\) for our game. To this end, let \(\mathbf{c}'\) be some arbitrary equilibrium for \(G\). By , we know that under \(\mathbf{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 \({\mathit{party}}(p)\) report the same cost. Indeed, if there were two projects, \(p'\) and \(p'' \in {\mathit{party}}(p)\), such that \(\mathbf{c}'(p') < \mathbf{c}'(p'')\), then it would be beneficial for \(p'\) to report a higher cost (but below \(\mathbf{c}'(p'')\)), so that \(\mathop{\mathrm{\text{Phragm\'en}}}\) 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 \({\mathit{party}}(p) \neq {\mathit{party}}(q)\), then, under \(\mathbf{c}'\), the last project from \({\mathit{party}}(p)\) and the last project from \({\mathit{party}}(q)\) are selected by \(\mathop{\mathrm{\text{Phragm\'en}}}\) 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 \(\mathbf{c}\) as defined in the statement of the proposition. ◻
We conjecture that one can adapt the algorithm behind to compute in polynomial-time a tie-breaking order and a corresponding \(\text{Phragm\'en}\text{-}{\text{NE}}\) for party-list profiles and arbitrary delivery costs. The reported cost for each party should be spread equally to all members (as in ). Yet, so far, the respective correctness proof remains elusive.
Unfortunately, party-list preferences with zero delivery costs are where the good news end. Indeed, there are instances with no equilibria, even for very few candidates and voters.
Proposition 6. There is a PB game with six projects and six voters and zero delivery costs, for which there is no \(\text{Phragm\'en}\text{-}{\text{NE}}\) irrespective of the tie-breaking order.
Proof Sketch. Let our project set be \(P = P' \cup P''\), where \(P' = \{p'_1,p'_2,p'_3\}\) and \(P'' = \{p''_1,p''_2,p''_3\}\). Similarly, the set of voters is \(V = V' \cup V''\), where \(V' = \{v_{1}',v_{2}',v_{3}'\}\) and \(V'' = \{v''_1, v''_2,v''_3\}\). Project \(p'_1\) is approved by \(v'_1\), \(p'_2\) by \(v'_2\), and \(p'_3\) by all voters in \(V'\). The approvals for projects in \(P''\) are analogous, but come from voters in \(V''\) (hence our instance can be illustrated by two copies on the right-hand side picture from with \(v_2\) and \(v_3\) swapped).
We first show that in all equilibria all projects report such costs that at the first time some voters can make a purchase, there is a tie between all of them. If \(p'_1 \succ p'_3\), then \(p'_2\) benefits by reporting a higher cost (as \(\text{Phragm\'en}\) funds \(p'_1\) and the supporters of \(p'_3\) need time to collect money for it; meanwhile, \(v'_2\) also gets more money to spend on \(p'_2\)). The cases where \(p'_2 \succ p'_3\), or either \(p''_1\) or \(p''_2\) is preferred to \(p''_3\) are symmetric. If \(p'_3\) is preferred to other members of \(P'\) and \(p''_3\) to other members of \(P''\), then \(p'_3\) (symmetrically, \(p''_3\)) prefers to increase the price, as after \(p'_1\), \(p'_2\), and \(p''_3\) are simultaneously funded, the time needed by \(v''_1\) and \(v''_2\) to collect money for \(p''_1\) and \(p''_2\) suffices for voters in \(V'\) to collect more than enough money for \(p'_3\). The full proof is in the appendix. ◻
Proof. Let our project set be \(P = P' \cup P''\), where \(P' = \{p'_1,p'_2,p'_3\}\) and \(P'' = \{p''_1,p''_2,p''_3\}\). Similarly, the set of voters is \(V = V' \cup V''\), where \(V' = \{v_{1'},v_{2'},v_{3'}\}\) and \(V'' = \{v_{1''},v_{2''},v_{3''}\}\). The approvals are as follows (see also for illustration):
\(p'_1\) is approved by \(v_{1'}\), \(p'_2\) is approved by \(v_{2'}\), and \(p'_3\) is approved by all the voters in \(V'\).
The approvals for the projects in \(P''\) are analogous, except that they are approved by the voters from \(V''\).
We set the delivery costs \(d\) to be zero for every project, and we set the budget \(B\) to be \(1\) (the exact value will be irrelevant as we will operate on times when \(\text{Phragm\'en}\) reaches the costs of particular projects rather than on directly on these costs). We claim that under \(\text{Phragm\'en}\) there are no Nash equilibria for the thus defined PB game \(G = (P,V,B,d)\).
Figure 3: Illustration of the PB game from the proof of . 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 us assume that there is \(\text{Phragm\'en}\text{-}{\text{NE}}\) for \(G\) and let it be \(\mathbf{c}^*\). For each project \(p \in P\), let \({\mathit{time}}(p)\) be the time moment (in the sense of the \(\text{Phragm\'en}\) rule) when the voters approving \(p\) would collect exactly \(\mathbf{c}^*(p)\) amount of money (assuming that neither of these voters spends it on any other projects in between; hence \({\mathit{time}}(p) = \frac{\mathbf{c}^*(p)}{|A(p)|}\)). We make the following observations:
All projects in \(P\) are funded for the reported costs \(\mathbf{c}^*\) (if some project were not funded, it would prefer to report a small nonzero cost that would be at most equal to \(B\) and that would ensure that \(\text{Phragm\'en}\) considers it first).
It must be the case that \({\mathit{time}}(p'_1) = {\mathit{time}}(p'_2)\). Indeed, if we had \({\mathit{time}}(p'_1) < {\mathit{time}}(p'_2)\) then it would be beneficial for \(p'_1\) to slightly increase its cost, but so that \({\mathit{time}}(p'_1)\) would still be below \(p'_2\). Then, irrespective in what order are the other projects funded, \(p'_1\)’s voter would collect enough money to purchase \(p'_1\) before the \(p'_2\)’s voter would, and \(p'_1\) would be bought (since \(p'_2\) would not be selected at this time yet, there would be enough budget left for this). This would contradict that \(\mathbf{c}^*\) is an equilibrium. The case \({\mathit{time}}(p'_2) < {\mathit{time}}(p'_1)\) is symmetric.
It must be the case that \({\mathit{time}}(p'_3) = {\mathit{time}}(p'_1)\) and, hence, also equal to \({\mathit{time}}(p'_2)\). Indeed, if we had \({\mathit{time}}(p'_3) < {\mathit{time}}(p'_1) = {\mathit{time}}(p'_2)\) then it would be beneficial for \(p'_3\) to report slightly higher cost, so that \({\mathit{time}}(p'_3)\) would still be smaller than \({\mathit{time}}(p'_1) = {\mathit{time}}(p'_2)\), yet \(p'_3\)’s cost would not have increased by more than the total costs of \(p'_1\) and \(p'_2\). Then \(p'_3\) would still be selected before \(p'_1\) and \(p'_2\) and there would be sufficient amound of budget left for it. This would contradict that \(\mathbf{c}^*\) is an equilibrium. On the other hand, if \({\mathit{time}}(p'_3) > {\mathit{time}}(p'_1) = {\mathit{time}}(p'_2)\) then it would be beneficial, e.g., for \(p'_1\) to report slightly higher cost, but ensuring that \({\mathit{time}}(p'_1) < {\mathit{time}}(p'_3)\). Indeed, if originally we have \({\mathit{time}}(p'_1) < {\mathit{time}}(p'_3)\), then \(p'_1\) is funded before \(p'_3\) by \(\text{Phragm\'en}\). After the increase, \(p'_1\) would still be purchased before \(p'_3\) and, thus, there would still be sufficient budget for it. This would contradict that \(\mathbf{c}^*\) is an equilibrium.
By a reasoning analogous to the one given above, it must be the case that \({\mathit{time}}(p''_1) = {\mathit{time}}(p''_2) = {\mathit{time}}(p''_3)\).
Given the above observations, we set: \[\begin{align} {\mathit{time}}' &= {\mathit{time}}(p'_1) = {\mathit{time}}(p'_2) = {\mathit{time}}(p'_3), \text{ and} \\ {\mathit{time}}'' &= {\mathit{time}}(p''_1) = {\mathit{time}}(p''_2) = {\mathit{time}}(p''_3). \end{align}\] Note that this implies that \(\mathbf{c}^*(p'_1) = \mathbf{c}^*(p'_2) = {\mathit{time}}'\), \(\mathbf{c}^*(p''_1) = \mathbf{c}^*(p''_2) = {\mathit{time}}''\), \(\mathbf{c}^*(p'_3) = 3\cdot {\mathit{time}}'\), and \(\mathbf{c}^*(p''_3) = 3\cdot {\mathit{time}}''\). We claim that \({\mathit{time}}' = {\mathit{time}}''\). Indeed, let us consider what happens if \({\mathit{time}}' < {\mathit{time}}''\) (the case where \({\mathit{time}}'' < {\mathit{time}}'\) is symmetric). There are two cases two consider (the second case also splits into two).
First, let us assume that at least one of \(p'_1\) and \(p'_2\) is preferred to \(p'_3\) by the tie-breaking order (for the sake of specificity, let this be \(p'_1\)). Then it is beneficial for \(p'_2\) to slightly increase its cost. To see why this is the case, let us consider how \(\text{Phragm\'en}\) operates after this increase. At time \({\mathit{time}}(p'_1) = {\mathit{time}}(p'_3)\), the voters have enough funds to purchase either \(p'_1\) or \(p'_3\) (and not enough to purchase \(p'_2\), who increased its cost). The rule selects \(p'_1\) due to tie-breaking. Consequently, voter \(1'\) pays for \(p'_1\) and his or her virtual bank account is reset to zero. Voters \(2'\) and \(3'\) still have \({\mathit{time}}'\) amount of money. The cost of \(p'_3\) is \(3 \cdot {\mathit{time}}'\), so voters in \(N'\) will have collected enough money for it after further \(\frac{1}{3} {\mathit{time}}'\) amount of time. However, if \(p'_2\) increased its cost from \({\mathit{time}}'\) to an amount a bit below \(\frac{4}{3} \cdot {\mathit{time}}'\) then its voter will have collected this amount earlier, and \(p'_2\) will be purchased before \(p'_3\). This contradicts the fact that \(\mathbf{c}^*\) is an equilibrium.
The second case is that \(p'_3\) is preferred by tie-breaking to both \(p'_1\) and \(p'_2\). Then it is beneficial for \(p'_3\) to slightly increase its cost. Again, let us consider how \(\text{Phragm\'en}\) operates after such a change. If \(p''_3\) is selected prior to both \(p''_1\) and \(p''_2\), then at time \({\mathit{time}}''\) (after the purchase of \(p''_3\)) the voters have the following amounts of money:
Voter \(3'\) has \({\mathit{time}}''\) amount of money and the remaining voters in \(N'\) have nonzero amounts of money (specifically, each of them has \({\mathit{time}}''-{\mathit{time}}'\), because they paid for \(p'_1\) and \(p'_2\) at time \({\mathit{time}}'\)).
All the voters in \(V''\) have empty bank accounts.
Hence, only after another \({\mathit{time}}''\) amount of time will the voters in \(N''\) have enough money to purchase \(p''_1\) and \(p''_2\). Yet, at this time the voters in \(N'\) would, altogether, have more than \(4 {\mathit{time}}''\). So, if \(p'_3\) increased its cost to be between \(3\cdot {\mathit{time}}'\) and \(4\cdot{\mathit{time}}'\) (which is smaller than \(4\cdot {\mathit{time}}''\)), then \(p'_3\) would be funded before \(p''_1\) and \(p''_2\), and there would be sufficient amount of budget left for this.
On the other hand, if at least one of \(p''_1\) and \(p''_2\) is preferred to \(p''_3\) by tie-breaking at time \({\mathit{time}}''\), then both \(p''_1\) and \(p''_2\) 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''_3\), but they do have enough for the other one among \(p''_1\) and \(p''_2\)). Consequently, after \(p''_1\) and \(p''_2\) are purchased at time \({\mathit{time}}''\), only projects \(p'_3\) and \(p''_3\) are not selected yet and the voters have the following amounts of money:
Voter \(v_{3'}\) has \({\mathit{time}}''\) amount of money and the remaining voters in \(V'\) have nonzero amounts of money (specifically, each of them has \({\mathit{time}}''-{\mathit{time}}'\), because they paid for \(p'_1\) and \(p'_2\) at time \({\mathit{time}}'\)).
Voter \(v_{3''}\) has \({\mathit{time}}''\) amount of money and the remaining voters in \(V''\) have no money.
Since voters in \(V'\) have, together, more money than those in \(V''\), but voters from both groups (jointly) earn money at the same rate (as \(|V'| = |V''|\)), if \(p'_3\) increased its cost to be slightly below that of \(p''_3\), it will be funded before \(p'_3\). Consequently, if \(\mathbf{c}^*\) is an equilibrium then we must have \({\mathit{time}}' = {\mathit{time}}''\).
Finally, it suffices to show that the assumption \({\mathit{time}}' = {\mathit{time}}''\) also leads to no equilibrium. W.l.o.g., we assume that \(p'_3\) precedes both \(p'_1\) and \(p'_2\) in the tie-breaking order, and that \(p''_3\) precedes both \(p''_1\) and \(p''_2\) (if this were not the case, then the arguments given in Case A above would still show that \(\mathbf{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 \(\text{Phragm\'en}\) there is no Nash equilibrium in our game. ◻
The mechanics of \(\text{MES}\) might appear similar to those of \(\text{Phragm\'en}\), as all these rules implement the approach in which voters buy the projects they approve. However, contrary to \(\text{Phragm\'en}\), in both types of \(\text{MES}\) voters have limited amounts of budget to spend. Hence, the approval scores of projects give upper-bounds on the maximum costs that the projects might report. That is, since each voter gets an equal share of the budget, projects that cost more than the total budget of their supporters would never be funded.
Observation 1. For every PB game and a strategy profile \(\mathbf{c}\), if there is a project \(p_i \in P\) such that \(\mathbf{c}(p_i) > B\cdot \frac{|A(i)|}{|V|}\), then \(p_i\) is not funded under \(\text{MES}\).
For \(\text{{MES\text{-}Cost}}\), we provide positive results. Specifically, we show that a \(\text{{MES\text{-}Cost}}\) always exists regardless of the tie-breaking order, even for arbitrary delivery costs, it is polynomial-time computable, and uses the entire budget (at least if all the projects have sufficiently low delivery costs).
Theorem 2. For each PB game, there is a polynomial-time computable \(\text{{MES\text{-}Cost}}\) profile \(\mathbf{c}\), unique up to the actions of the projects not selected by \(\text{{MES\text{-}Cost}}\) under \(\mathbf{c}\).
Proof sketch. Let \(p\) be the project with the largest number of approvals (and preferred in the tie-breaking order, should there be other projects with the same number of approvals). We observe that \(p\) can always request the full amount of money that its voters have at the beginning of the execution of \(\text{{MES\text{-}Cost}}\); the rule would fund \(p\) irrespective of the costs of the other projects. Thus, \(p\) reports this amount and is 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. We put the full proof in the appendix. ◻
Proof. Let \((P, V, B, d)\) be a \(\text{{MES\text{-}Cost}}\) PB game.
We provide an iterative algorithm that computes \(\mathbf{c}\). In each iteration, the algorithm fixes selected values of \(\mathbf{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 to consider. Before laying out the details, let us recall that in \(\text{{MES\text{-}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 \(\mathbf{c}\) step by step maintaining the collection \(V'\) of voters to consider and the collection \(P'\) of projects to consider. The algorithm starts with setting \(V' = V\), \(P' = P\) and proceeds as follows:
Remove from \(P'\) all projects \(p_i \in P'\) for which \(|A(p_i) \cap V'| \cdot \frac{B}{|V|}\) is lower than \(d(p_i)\) or equal to zero and let their strategy be \(\mathbf{c}(p_i) = d(p_i)\).
For each project \(p_j \in P'\), let \(\alpha_j = \frac{1}{|A(p_j) \cap V'|}\) (due to Step [stp:thm:mesCostNEGeneral:get-rid-of-impossible-to-select] we avoid dividing by zero) and let \(p^*\) be the project \(p_j \in P'\) with the minimum \(\alpha_j\)-value (in case of a tie, select the first one in the tie-breaking order).
Set the strategy \(\mathbf{c}(p^*)\) to \(|A(p^*) \cap V'| \cdot \frac{B}{|V|}\), that is, such that \(p^*\) reports the cost equal to the total budget of its supporters in \(V'\).
Remove all supporters of \(p^*\) from \(V'\) and remove \(p^*\) from \(P'\).
Repeat Steps [stp:thm:mesCostNEGeneral:get-rid-of-impossible-to-select] to [stp:thm:mesCostNEGeneral:spend-budget] until \(P'\) is empty.
Our algorithm is based on the following useful claim about the decisions made by \(\text{{MES\text{-}Cost}}\).
Claim 2. Let us fix some stage of \(\text{{MES\text{-}Cost}}\) in which every voter with a nonzero budget has the same value of budget and let \(V'\) be these voters. Then, for each \(\alpha'\)-affordable project \(p'\) it holds that that \(\alpha' = \frac{1}{|A(p') \cap V'|}\).
The claim is implied by the definition of \(\text{{MES\text{-}Cost}}\). Observe that if a project \(p\) is \(\alpha\)-affordable, then the voters approving it have enough budget to buy it and \(\alpha\) is the minimum such \(x\) that \(|A(p') \cap V'| \cdot x \cdot \mathit{cost}(p) \leq \mathit{cost}(p)\). The sought \(\alpha\) is then clearly \(\frac{1}{|A(p') \cap V'|}\).
Let us denote by \((p^*_1, p^*_2, \ldots, p^*_k)\) the projects considered in the respective iterations \(1\) to \(k\) of Steps [stp:thm:mesCostNEGeneral:get-rid-of-impossible-to-select]-[stp:thm:mesCostNEGeneral:spend-budget]. In what follows we show that in each Nash equilibrium \(\text{{MES\text{-}Cost}}\) selects exactly projects \((p^*_1, p^*_2, \ldots, p^*_k)\) in the given order and that \(\mathbf{c}\) is a Nash equilibrium. We apply induction over the stages of \(\text{{MES\text{-}Cost}}\).
For the base case, we argue that \(p^*_1\) has to be selected first by \(\text{{MES\text{-}Cost}}\) and has to play \(\mathbf{c}(c^*_1)\) in every Nash equilibirum. Assume for contradiction that some other project \(p'\) is selected first instead of \(p^*_1\) in a Nash equilibrium. Due to and since \(\text{{MES\text{-}Cost}}\) selects \(\alpha\)-affordable projects starting from those with the smallest \(\alpha\), it follows that one of the three holds: (i) \(\frac{1}{|A(p')|} < \frac{1}{|A(p^*_1)|}\), (ii) \(\frac{1}{|A(p')|} = \frac{1}{|A(p^*_1)|}\) and \(p'\) is preferred to \(p^*_1\) by the tie-breaking, or (iii) \(p^*_1\) reports a cost greater than the budget of its supporters. Cases (i) and (ii) yield a clear contradiction to Step [stp:thm:mesCostNEGeneral:selecting-project], which defines \(p^*_1\). In Case (iii), reporting cost \(\mathbf{c}'(p^*_1) = d(p^*_1) + \epsilon \leq B\cdot \frac{|A(p^*_1)|}{|V|}\) (such an \(\epsilon\) always exists due to Step [stp:thm:mesCostNEGeneral:get-rid-of-impossible-to-select]) is a profitable deviation for \(p^*_1\)—a contradiction. Knowing that \(p^*_1\) is selected first in every Nash equilibrium, we observe that if \(p^*_1\) reports a cost \(\mathbf{c}'(p^*_1) < B\cdot \frac{|A(p^*_1)|}{|V|}\), then reporting exactly \(\mathbf{c}(p^*_1) = B\cdot \frac{|A(p^*_1)|}{|V|}\) is always a profitable deviation, which confirms that in every Nash equilibrium \(p^*_1\)’s strategy is \(\mathbf{c}(p^*_1)\) and it is selected first by \(\text{{MES\text{-}Cost}}\).
We move on to the inductive step and thus consider stage \(i\) of \(\text{{MES\text{-}Cost}}\) in which project \(p^*_i\) is selected. Imporantly, as we have shown that player \(p^*_1\) has to report cost \(\mathbf{c}(p^*_1)\) equal to the total budget of \(p^*_1\) 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 a result, holds at the \(i\)-th stage, which we consider. Thanks to this, we apply an analogous exchange argument (pretending that voters outside of \(V'\) do not exist) to that for the base case to show that indeed \(p^*_i\) has to be selected at the \(i\)-th stage. Then, we directly repeat the argument regarding the optimal strategy for \(p^*_1\) applying it to \(p^*_i\). Eventually, we have shown that in each Nash equilibrium for \(\text{{MES\text{-}Cost}}\) projects \((p^*_1, p^*_2, \ldots, p^*_k)\) are selected and report, respectively, costs \((\mathbf{c}(p^*_1), \mathbf{c}(p^*_2), \ldots, \mathbf{c}(p^*_k))\). ◻
For MESApr, the situation is more complicated, as an equilibrium may not exist even for a party-list profile with only three projects and one voter. Nevertheless, it always exists for plurality ballots and for party-list ballots with zero delivery costs (the proofs are in the appendix).
Theorem 3. For every PB game with plurality ballots, there is a polynomial-time computable MESApr regardless of the internal tie-breaking order and delivery costs.
Proof. Let \((P, V, B, d)\) be a MESApr PB game with plurality ballots. In MESApr, like in every \(\text{MES}\) rule, each voter receives \(\frac{B}{|V|}\) money for the whole election process. As each voter approves only one project, each project \(p_i\) can request at most \(M(p_i) = \frac{|A(p_i)| \cdot B}{|V|}\) from its supporters, and will report this cost as they would not spend any money on other projects. Thus, if \(d(p_i) \leq M(p_i)\), project \(p_i\) reports \(M(p_i)\) and gets selected with its maximum possible cost. Otherwise, if \(d(p_i) > M(p_i)\), \(p_i\) cannot be selected with cost covering \(d(p_i)\), so \(p_i\) reports \(d(p_i)\) and is not selected. ◻
Theorem 4. For every PB game with party-list ballots and zero delivery costs, there is a polynomial-time computable MESApr regardless of the internal tie-breaking order.
Proof. Let \((P, N, B, d)\) be a MESApr PB game with party-list ballots and zero delivery costs.
At the beginning, each voter receives \(\frac{B}{|V|}\) money. In a party-list profile, as every two voters have either the same preferences or the disjoint ones, \(A(p_i) = A({\mathit{party}}(p_i))\). The total money the supporters of \({\mathit{party}}(p_i)\) have is \(M({\mathit{party}}(p_i)) = |A(p_i)| \cdot \frac{B}{|V|} = \frac{|A(p_i)| \cdot B}{|V|}\). Therefore, the projects in \({\mathit{party}}(p_i)\) need to somehow distribute this money between them in such a way that no project would complain and change its cost to obtain better outcome.
Since we have cardinal utilities, the \(\alpha\)-value of project \(p_i\) is initially \(\alpha_1(p_i) = \frac{\mathbf{c}(p_i)}{|A({\mathit{party}}(p_i))|}\). For this reason, MESApr 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.
This means that each project should ask for the equal part of the money of party supporters, that it, \(\frac{M({\mathit{party}}(p_i))}{|{\mathit{party}}(p_i)|}\). 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 is already funded.
For this reason, for the profile \(\mathbf{c}\) where each project says \(\mathbf{c}(p_i) = \frac{M({\mathit{party}}(p_i))}{|A({\mathit{party}}(p_i)|}\), we obtain MESApr. ◻
Now we show an example with only three projects and one voter for which MESApr does not exist (recall that each profile with one voter is also a party-list profile).
Example 3. Take a PB game \(G\) with one voter approving projects \(p_1\), \(p_2\), and \(p_3\). Let \(B=6\), \(d(p_1) = 3\), \(d(p_2) = 0\), and \(d(p_3) = 0\), with \(p_1 \succ p_2 \succ p_3\). We show that there is no MESApr-NE in \(G\) (the full proof is in the appendix).
Sketch of an argument: Suppose that \(\mathbf{c}\) is an NE. Then \(\mathbf{c}(p_1) \geq 3\) (otherwise, as it is selected, \(p_1\) improves by reporting \(3\)) and \(\mathbf{c}(p_2), \mathbf{c}(p_3) < \mathbf{c}(p_1) = 3 = \frac{B}{2}\) (otherwise, the more expensive one is not funded). Since \(\mathbf{c}(p_2) + \mathbf{c}(p_3) < B\), \(p_2\) may report \(\frac{(\mathbf{c}(c_1) + \mathbf{c}(c_2))}{2}\) and still be selected, so \(\mathbf{c}\) is not an NE.
Suppose towards contradiction that \(\mathbf{c}\) is such an equilibrium. W.l.o.g.,let \(\mathbf{c}(p_1) \geq d(p_1) = 3\). Otherwise, if \(p_1\) would be selected under these costs (and, hence, received a negative payoff), then it would prefer to report \(d(p_1)\) and receive utility 0. If it was not funded under \(\mathbf{c}\), then \((\mathbf{c}_{-i}, d(p_1))\) also would be an equilibrium. Next, we observe that \(\mathbf{c}(p_1) = 3\). Indeed, if \(p_1\) reported a value greater than \(3\), then one of the projects could obtain a better payoff: If \(p_2\) or \(p_3\) reported a value greater or equal to \(\mathbf{c}(p_1)\), then it would benefit by reporting a smaller one; if \(p_2\) and \(p_3\) reported values that sum up to more than \(B\), then at 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\), \(p_1\) would benefit by reporting \(3\). Hence, we have that \(\mathbf{c}(p_1) = 3 = \frac{B}{2}\). Then, both \(\mathbf{c}(p_2) > 0\) and \(\mathbf{c}(p_3) > 0\) (the project reporting \(0\) would benefit by reporting a larger number). Further, we have that \(\mathbf{c}(p_2) < \mathbf{c}(p_1)\) and \(\mathbf{c}(p_3) < \mathbf{c}(p_1)\). Indeed, if either \(p_2\) or \(p_3\) reported value greater or equal to \(\mathbf{c}(p_1)\) then it would not be selected and, hence, would benefit by reporting a smaller cost. So, \(\mathbf{c}(p_2) + \mathbf{c}(p_3) < 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 \(\mathbf{c}\) is not a MESApr-NE.
We note that the problem in Example 3 is partially caused by the delivery costs and the tie-breaking order. If \(p_1\) were behind \(p_2\) and \(p_3\) in the tie-breaking order, then \(p_2\) and \(p_3\) would have reported cost \(3\), which would be a MESApr. Now we show that for a party-list instance we can efficiently compute an internal tie-breaking order and a corresponding MESApr (the proof is in the appendix).
Theorem 5. For every PB game with party-list ballots and some corresponding A/D tie-breaking order, there is a MESApr computable in polynomial-time.
Proof. Let \((P, V, B, d)\) be a MESApr PB game with party-list ballots. Recall that at the beginning each voter receives \(\frac{B}{|V|}\) money. Then, the total money the supporters of \({\mathit{party}}(p_i)\) have is \(M({\mathit{party}}(p_i)) = |A(p_i)| \cdot \frac{B}{|V|} = \frac{|A(p_i)| \cdot B}{|V|}\).
Let \(\succ\) be the A/D tie-breaking order from the theorem statement. Note that for the case of party-list ballots \(\succ\) 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, \(\succ\) does not impose any specific order with respect to the delivery costs over any two projects of two different parties.
Since in MESApr we consider cardinal utilities, the \(\alpha\)-value of project \(p_i\) is at the beginning: \(\alpha_1(p_i) = \frac{\mathbf{c}(p_i)}{|A({\mathit{party}}(p_i))|}\). For this reason, MESApr will start from the cheapest project in the party to the most expensive one (following the specified 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.
Now we have to consider two cases:
The last in the tie-breaking order project \(p_j \in party(p_i)\) has delivery cost \(d(p_j)\) not exceeding \(\frac{M({\mathit{party}}(p_i))}{|{\mathit{party}}(p_i)|}\). Note that this case is similar to the one in Theorem 4, i.e., each project submits \(\frac{M({\mathit{party}}(p_i))}{|{\mathit{party}}(p_i)|}\), gets funded, and no project benefits from changing its cost.
The last in the tie-breaking order project \(p_j \in {\mathit{party}}(p_i)\) has delivery cost \(d(p_j)\) exceeding \(\frac{M({\mathit{party}}(p_i))}{|{\mathit{party}}(p_i)|}\). In such a case, if every project submitted cost \(d(p_j)\), then \(p_j\) 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 \(p_j\) to be \(d(p_j)\), remove \(p_j\) from consideration, and repeat this procedure as long as the product of the number of yet-remained projects and the delivery cost of the last in the tie-breaking project exceeds \(M({\mathit{party}}(p_i))\). Suppose now that the procedure stopped and project \(p_k\) was the last removed one. Then all \(y\) yet-remaining projects would say cost \(min(\frac{M({\mathit{party}}(p_i))}{y}, d(p_k))\) and be given this funding. Saying more than \(d(p_k)\) would result in being overtaken by project \(p_k\) and thrown out of the outcome due to insufficient budget. Saying more than \(\frac{M({\mathit{party}}(p_i))}{y}\) 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 \(\mathbf{c}\) profiles calculated in the above way for all parties is a MESApr for the given instance. ◻
One might wonder whether there always is a tie-breaking order leading to a MESApr. Unfortunately, as in the case of \(\text{Phragm\'en}\), there is a small game (depicted in the appendix) with no MESApr irrespective of the tie-breaking order.
Proposition 7. There are games with zero delivery costs, for which there is no MESApr regardless of the tie-breaking order, even if we have only \(4\) projects and \(16\) votes.
Proof. We create four projects \(p_1, \ldots, p_4\) and \(16\) voters \(v_1, \ldots, v_{16}\). Project \(p_1\) is approved by voters \(v_1, \ldots, v_5\); project \(p_2\) by voters \(v_{13}, \ldots, v_{16}, v_1\); project \(p_3\) by voters \(v_5, \ldots, v_9\); and project \(p_4\) by voters \(v_9, \ldots, v_{13}\). We set the budget to be some positive integer \(B\) and delivery costs to be \(d\equiv 0\). Please note that we do not specify tie-breaking as we prove nonexistence of MESApr in any tie-breaking.
Figure 4: Approval sets of projects \(p_1, p_2, p_3\), and \(p_4\). Here, each vertex represents a single voter.
For a 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).
Now we will show that there is no MESApr for this instance. Suppose towards contradiction that some profile \(\mathbf{c}\) is a MESApr.
At the beginning, each voter receives \(b = \frac{B}{|V|} = \frac{B}{16}\) money. Therefore, a) no project says cost exceeding \(5b = \frac{5B}{16}\) (otherwise its supporters would never have enough money to buy it, and b) no project says less than \(3b = \frac{3B}{16}\) (as each project has three supporters that contribute only to it, it is nonoptimal to say less than they have). Further, as each project has zero delivery costs, each project must be selected in MESApr, otherwise an unselected project could have decreased its cost to \(0\) and be selected. For this reason, \(\sum_{i=1}^{4}{\mathbf{c}(p_i)} \leq B\).
For the sake of brevity, for yet-unselected project \(p_i\) in iteration \(j\), we denote \(\alpha_j(p_i)\) as minimum value such that project \(p_i\) is \(\alpha_j(p_i)\)-affordable according to MESApr rule (or infinity, if such a value does not exist). By \(\epsilon \in {\mathbb{R}}_+\) 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 \(p_1\) says the lowest cost (i.e., \(\mathbf{c}(p_1) \leq \mathbf{c}(p_2), \mathbf{c}(p_3), \mathbf{c}(p_4)\)) and wins ties if there is more than more project with this cost as well as 2) \(\mathbf{c}(p_2) \leq \mathbf{c}(p_3)\) and \(p_2\) wins ties with \(p_3\). If it was not the case, we can shift or rotate projects and perform analogous reasoning.
Before we move on, let us exclude some cases in which \(\mathbf{c}\) cannot be MESApr.
We point out that if there is no project of the same cost as \(p_1\), then \(p_1\) could have increased its cost by some positive number \(\epsilon\) while still being considered first and getting more, so \(\mathbf{c}\) could not have been MESApr in this case. Therefore, \(p_1\) has the same cost either as 1) \(p_4\), or as 2) \(p_2\) (please note \(\mathbf{c}(p_1) = \mathbf{c}(p_3)\) implies \(\mathbf{c}(p_1) = \mathbf{c}(p_2)\) due to assumption that \(\mathbf{c}(p_2) \leq \mathbf{c}(p_3)\)).
With our assumptions, project \(p_1\) is selected in the first iteration and each of its supporters pays \(\frac{\mathbf{c}(p_1)}{5}\) for \(p_1\). As \(b - \frac{\mathbf{c}(p_i)}{5} \leq \frac{B}{16} - \frac{\frac{3B}{16}}{5} = \frac{\frac{2B}{16}}{5} < \frac{\frac{3B}{16}}{5} \leq \frac{\mathbf{c}(p_j)}{5}\) for any \(p_i, p_j \in P\), voter \(v_1\) has insufficient money to contribute the equal share \(\frac{\mathbf{c}(p_2)}{5}\) to purchase \(p_2\). Therefore, in the second iteration, \(\alpha_2(p_4) = \frac{\mathbf{c}(p_4)}{5}\), \(\alpha_2(p_2) = \frac{\mathbf{c}(p_2) - (b - \frac{\mathbf{c}(p_1)}{5})}{4}\), and \(\alpha_2(p_3) = \frac{\mathbf{c}(p_3) - (b - \frac{\mathbf{c}(p_1)}{5})}{4} \geq \alpha_2(p_2)\). Please note that \(\alpha_2(p_2) = \frac{\mathbf{c}(p_2) - (b - \frac{\mathbf{c}(p_1)}{5})}{4} \geq \frac{\mathbf{c}(p_1) - (\frac{B}{16} - \frac{\mathbf{c}(p_1)}{5})}{4} = \frac{6\mathbf{c}(p_1)}{20} - \frac{B}{64} = \frac{4\mathbf{c}(p_1)}{20} + (\frac{2\mathbf{c}(p_1)}{20} - \frac{B}{64}) \geq \frac{\mathbf{c}(p_1)}{5} + (\frac{2 \cdot \frac{3B}{16}}{20} - \frac{B}{64}) = \frac{\mathbf{c}(p_1)}{5} + \frac{6B-5B}{16 \cdot 20} = \frac{\mathbf{c}(p_1)}{5} + \frac{B}{16 \cdot 20} > \frac{\mathbf{c}(p_1)}{5} = \alpha_1(p_1)\). Thus, as \(\alpha_2(p_2) > \alpha_1(p_1)\), project \(p_4\) would regret saying the same cost as project \(p_1\). Indeed, selecting \(p_1\) in the first iteration significantly increases \(\alpha_2(p_2)\) and \(\alpha_2(p_3)\), so if \(p_4\) said \(\mathbf{c}(p_4) = \mathbf{c}(p_1)\), then it would benefit from slightly increasing the cost by \(\epsilon\) (it would still be before \(p_2\), but it would earn more). For this reason, it cannot be the case that \(\mathbf{c}(p_1) = \mathbf{c}(p_4)\), so due to the former reasoning we know that \(\mathbf{c}(p_1) = \mathbf{c}(p_2)\) and \(\mathbf{c}(p_1) < \mathbf{c}(p_4)\).
So we know that: \(\mathbf{c}(p_1) = \mathbf{c}(p_2)\), \(\mathbf{c}(p_1) < \mathbf{c}(p_4)\), and \(\mathbf{c}(p_2) \leq \mathbf{c}(p_3)\). We have two cases to consider:
Project \(p_4\) is selected in the second iteration. It means that \(\alpha_2(p_4) \leq \alpha_2(p_2)\). We observe that it must be \(\alpha_2(p_4) = \alpha_2(p_2)\), otherwise it would be beneficial for \(p_4\) to slightly increase its cost by \(\epsilon\) in such a way that \(p_4\) is still considered before \(p_2\) and gains more.
In this case, as \(p_2\) and \(p_3\) are approved by disjoint sets of voters and both \(p_1\) and \(p_4\) took the same amount of money from the same number of their supporters, both \(p_2\) and \(p_3\) should request for the same amount of money, that is, all money that their supporters have. Thus \(\mathbf{c}(p_3) = \mathbf{c}(c_2) = 3 \cdot b + (b - \frac{\mathbf{c}(p_1)}{5}) + (b - \frac{\mathbf{c}(p_4)}{5}) = 5b - \frac{\mathbf{c}(p_1)}{5} - \frac{\mathbf{c}(p_4)}{5}\) and \(\mathbf{c}(p_4) = 5 \cdot (5b - \frac{\mathbf{c}(p_1)}{5} - \mathbf{c}(p_2)) = 25b - 5\mathbf{c}(p_2) - \mathbf{c}(p_1)\).
However, we know that \(\mathbf{c}(p_1) = \mathbf{c}(p_2)\), so \(\mathbf{c}(p_1) = \mathbf{c}(p_2) = \mathbf{c}(p_3) = 5b - \frac{\mathbf{c}(p_1)}{5} - \frac{\mathbf{c}(p_4)}{5}\), which implies that \(\mathbf{c}(p_4) = 25b - 5\mathbf{c}(p_2) - \mathbf{c}(p_1) = 25b - 6\mathbf{c}(p_1)\). Therefore, \(\alpha_2(p_4) = \alpha_2(p_2)\) means that \(\frac{\mathbf{c}(p_4)}{5} = \frac{\mathbf{c}(p_2) - (b - \frac{\mathbf{c}(p_1)}{5})}{4} = \frac{6\mathbf{c}(p_1)}{20} - \frac{b}{4}\), which is equivalent to \(\frac{25b - 6\mathbf{c}(p_1)}{5} = \frac{6\mathbf{c}(p_1)-5b}{20} \Rightarrow 100b - 24\mathbf{c}(p_1) = 6\mathbf{c}(p_1) - 5b \Rightarrow 30\mathbf{c}(p_1) = 105b \Rightarrow \mathbf{c}(p_1) = \frac{7b}{2}\). Then we have \(\mathbf{c}(p_1) = \mathbf{c}(p_2) = \mathbf{c}(p_3) = \frac{7b}{2}\) and \(\mathbf{c}(p_4) = 25b - 6\mathbf{c}(p_1) = 25b - 21b = 4b\).
Now imagine that project \(p_1\) changes its cost from \(\mathbf{c}(p_1) = \frac{7b}{2}\) to \(\mathbf{c}'(p_1) = \frac{36b}{10}\). Naturally, projects \(p_2\) and \(p_3\) are selected in first two iterations so voters \(v_1, \ldots, v_5\) supporting \(p_1\) are left with \(b - \frac{\mathbf{c}(c_2)}{5}, b, b, b, b - \frac{\mathbf{c}(p_3)}{5}\) money respectively and they have \(b - \frac{\mathbf{c}(c_2)}{5} + b + b + b + b - \frac{\mathbf{c}(p_3)}{5} = 5b - 2 \cdot \frac{7b}{10} = \frac{36b}{10}\) money in total which they can only spend on project \(p_1\) as they disapprove \(p_4\). So \(p_1\) gets selected with \(\mathbf{c}'(p_1) = \frac{36b}{10} > \frac{7b}{2} = \mathbf{c}(p_1)\) which indicates that \(\mathbf{c}\) could not be MESApr.
Project \(p_2\) is selected in the second iteration. It means that \(\alpha_2(p_2) \leq \alpha_2(p_4)\). We observe that it must be \(\alpha_2(p_2) = \alpha_2(p_4)\), otherwise it would be beneficial for \(p_2\) to slightly increase its cost in such a way that \(p_2\) is still considered before \(p_4\) and gains more (please note that even if \(p_3\) would jump before \(p_2\), it takes money from the disjoint set of voters from \(p_2\)’s supporters, so it does not disprove this argument).
By performing analogous calculations to the previous case and using \(\mathbf{c}(p_1) = \mathbf{c}(p_2)\) we obtain that \(\alpha_2(p_2)= \frac{\mathbf{c}(p_2) - (b - \frac{\mathbf{c}(p_1)}{5})}{4} = \frac{6\mathbf{c}(p_1)}{20} - \frac{b}{4}\), so \(\alpha_2(p_4) = \alpha_2(p_2) \Rightarrow \frac{\mathbf{c}(p_4)}{5} = \frac{6\mathbf{c}(p_1)}{20} - \frac{b}{4} \Rightarrow \mathbf{c}(p_4) = \frac{6\mathbf{c}(p_1)-5b}{4}\).
After \(p_1\) and \(p_2\) are selected, voter \(v_1\) has \(0\) money left, voters \(v_2, \ldots, v_5\) have \(b - \frac{\mathbf{c}(p_1)}{5}\) money left, voters \(v_{13}, \ldots, v_{16}\) have \(b - \alpha_2(p_2) = b - (\frac{6\mathbf{c}(p_1)}{20} - \frac{b}{4}) = \frac{25b-6\mathbf{c}(p_1)}{20}\) money left, and voters \(v_6, \ldots, v_{12}\) have \(b\) money left.
We need to consider two cases:
\(p_3\) is selected before \(p_4\). Then \(\mathbf{c}(p_3) = \mathbf{c}(p_2)\), otherwise (if \(\mathbf{c}(p_2) < \mathbf{c}(p_3)\)) \(p_2\) would increase its cost by \(\epsilon\) in such a way that \(\mathbf{c}(p_2) + \epsilon < \mathbf{c}(p_3)\) and still be selected in the second iteration, but with more money. Because \(\mathbf{c}(p_3) = \mathbf{c}(p_2) = \mathbf{c}(p_1)\) and the supporters of \(p_2\) and \(p_3\) are disjoint and symmetric, after selecting \(p_3\), voter \(v_5\) be left with no money whereas voters \(v_6, \ldots, v_9\) with \(b - \alpha_3(p_3) = b - \alpha_2(p_2) = \frac{25b-6\mathbf{c}(p_1)}{20}\). Further, in the fourth iteration, the supporters of \(p_4\) have together \(3b + 2 \cdot \frac{25b-6\mathbf{c}(p_1)}{20} = \frac{30b+25b-6\mathbf{c}(p_1)}{10} = \frac{55b-6\mathbf{c}(p_1)}{10}\), so \(p_4\) asks for the money they still have in total.
Therefore, \(\mathbf{c}(p_4) = \frac{6\mathbf{c}(p_1)-5b}{4} = \frac{55b-6\mathbf{c}(p_1)}{10} \Rightarrow 30\mathbf{c}(p_1)-25b = 110b-12\mathbf{c}(p_1) \Rightarrow 42\mathbf{c}(p_1) = 135b \Rightarrow \mathbf{c}(p_1) = \frac{135b}{42}\). Thus \(\mathbf{c}(p_4) = \frac{6\mathbf{c}(p_1)-5b}{4} = \frac{6 \cdot \frac{135b}{42} - 5b}{4} = \frac{135b - 35b}{4 \cdot 7} = \frac{100b}{28} = \frac{150b}{42}\).
Imagine what happens if \(p_1\) increases its cost from \(\mathbf{c}(p_1) = \frac{135b}{42}\) to \(\mathbf{c}'(p_1) = \frac{156b}{42}\). Then \(p_2\) gets selected first with cost \(\mathbf{c}(p_2) = \frac{135b}{42}\) and each of its supporters pays \(\frac{\mathbf{c}(p_2)}{5} = \frac{\frac{135b}{42}}{5} = \frac{27b}{42}\). Next, each of \(p_3\)’s supporters will pay \(\frac{27b}{42}\) to purchase \(p_3\) (voters supporting \(p_2\) and \(p_3\) are disjoint). After that, regardless whether \(p_4\) is selected before \(p_1\) or not, the supporters of \(p_1\) have \(3b + 2 \cdot (b - \frac{27b}{42}) = \frac{3 \cdot 42 + 2 \cdot 15b}{42} = \frac{156b}{42}\), so the supporters of \(p_1\) have enough money to purchase \(p_1\). We showed that \(p_1\) could improve its utility by changing its cost, so the proposed \(\mathbf{c}\) is not MESApr in this case.
\(p_4\) is selected before \(p_3\). It means that \(\alpha_3(p_4) \leq \alpha_3(p_3)\). As we know how much money each voter has in the third iteration, \(\alpha_3(p_4) = \frac{\mathbf{c}(p_4)-\frac{25b-6\mathbf{c}(p_1)}{20}}{4} = \frac{20\mathbf{c}(p_4)-25b+6\mathbf{c}(p_1)}{80}\) and \(\alpha_3(p_3) = \frac{\mathbf{c}(p_3)-\frac{\mathbf{c}(p_1)}{5}}{4} = \frac{20\mathbf{c}(p_3)-4\mathbf{c}(p_1)}{80}\). After inserting the exact values we obtain that \(\alpha_3(p_4) \leq \alpha_3(p_3) \Rightarrow \frac{20\mathbf{c}(p_4)-25b+6\mathbf{c}(p_1)}{80} \leq \frac{20\mathbf{c}(p_3)-4\mathbf{c}(p_1)}{80} \Rightarrow 20\mathbf{c}(p_3) \geq 20\mathbf{c}(p_4)-25b+10\mathbf{c}(p_1) \Rightarrow \mathbf{c}(p_3) \geq \mathbf{c}(p_4) + \frac{\mathbf{c}(p_1)}{2} - \frac{5b}{4}\). However, \(\mathbf{c}(p_3) \geq \mathbf{c}(p_4) + \frac{\mathbf{c}(p_1)}{2} - \frac{5b}{4} > \mathbf{c}(p_4) + \frac{3b}{2} - \frac{5b}{4} = \mathbf{c}(p_4) + \frac{b}{4} > \mathbf{c}(p_1) + \frac{b}{4} = \mathbf{c}(p_2) + \frac{b}{4}\), so \(\mathbf{c}(p_3)\) is significantly greater than \(\mathbf{c}(p_2)\). In other words, even when voter \(v_9\) pays a greater share to buy \(p_4\) and is left with less money than \(\frac{\mathbf{c}(p_4)}{5}\), there is still enough money to purchase \(p_3\). Therefore, \(p_2\) can increase its cost from \(\mathbf{c}(p_2) = \mathbf{c}(p_1)\) to \(\mathbf{c}(p_3)-\epsilon\) and lose in the second iteration with \(p_4\), but still be funded before \(p_3\) and obtain more money. For this reason, \(\mathbf{c}\) is not MESApr.
We showed that in no case MESApr exists for this instance. The remaining tie-breaking order are completely analogous due to the instance’s symmetry.
It means that for the given instance there is no tie-breaking for which MESApr exists. ◻
MESApr and \(\text{Phragm\'en}\) might appear similar, as we have guarantees of NE existence only for very restricted domains, examples with nonexisting NE for given delivery costs, and small examples with no NE regardless of the tie-breaking order. However, despite optimizing a similar function (i.e., minimizing the maximum amount of money one voter pays to buy a project), MESApr and \(\text{Phragm\'en}\) differ in terms of both the NE existence and the obtained equilibria. For example, there are instances in which symmetric projects (i.e., projects that have exactly the same sets of supporters) ask for different amounts in a MESApr, but report identical costs under \(\text{Phragm\'en}\). The proof is in the appendix.
Theorem 6. In some instances symmetric projects (w.r.t. their supporters) submit different costs in a MESApr.
Proof. Our example is in fact the example from Proposition 6 narrowed to prim voters and projects.
We have three voters \(v_1, v_2\), and \(v_3\) as well as three projects \(p_1, p_2\), and \(p_3\). Projects \(p_1\) and \(p_2\) are approved by, respectively, voters \(v_1\) and \(v_2\), while project \(p_3\) 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 \(d\equiv 0\). We set the tie-breaking between projects to be \(p_1 \succ p_2 \succ p_3\). For the sake of brevity, for yet-unselected project \(p_i\) in iteration \(j\), we denote \(\alpha_j(p_i)\) as minimum value such that project \(p_i\) is \(\alpha_j(p_i)\)-affordable according to MESApr rule (or infinity, if such a value does not exist).
Let \((\mathbf{c}(p_1) = \frac{7B}{36}, \mathbf{c}(p_2) = \frac{8B}{36}, \mathbf{c}(p_3) = \frac{21B}{36})\) be the costs the projects say. We will show that it is MESApr.
At the beginning, each of three voters receives \(\frac{B}{3} = \frac{12B}{36}\) money.
In the first iteration, \(\alpha_1(p_1) = \frac{\frac{7B}{36}}{1} = \frac{7B}{36}, \alpha_1(p_2) = \frac{\frac{8B}{36}}{1} = \frac{8B}{36}, \alpha_1(p_3) = \frac{\frac{21B}{36}}{3} = \frac{7B}{36}\), so \(p_1\) and \(p_3\) are tied, while \(p_2\) has greater \(\alpha\)-value and is skipped for now. Thus, due to tie-breaking, we select \(p_1\) and voter \(v_1\) pays \(\frac{7B}{36}\) for \(p_1\).
In the second iteration, \(v_1\) has \(\frac{5B}{36}\) money while both \(v_2\) and \(v_3\) have \(\frac{12B}{36}\). Thus, since the budget of \(v_2\) did not change, \(\alpha_2(p_2) = \alpha_1(p_2) = \frac{8B}{36}\). In order to purchase \(p_3\), voter \(v_1\) would need to spend all left money whereas \(v_2\) and \(v_3\) would need to pay more to make up \(v_1\)’s insufficient money. More precisely, \(\alpha_2(p_3) = \frac{\frac{21B}{36} - \frac{5B}{36}}{2} = \frac{\frac{16B}{36}}{2} = \frac{8B}{36}\). So projects \(p_2\) and \(p_3\) are tied and we select \(p_2\) due to tie-breaking (by taking money from \(v_2\)).
Finally, in the third iteration, we will select \(p_3\) as its supporters have \(\frac{5B}{36} + \frac{4B}{36} + \frac{12B}{36} = \frac{21B}{36} = \mathbf{c}(p_3)\), all voters will use use all their money for it.
We showed that each project is selected with the proposed costs so no project benefits from lowering its costs. Next, \(p_3\) will not increase its cost as its supporters would not have enough money to buy it in the last iteration. Further, \(p_2\) will not increase its cost as it would lose with \(p_3\) in the second iteration and its only supporter \(v_2\) would pay \(\frac{8B}{36}\) for \(p_3\), leaving insufficient \(\frac{4B}{36}\) for \(p_2\). Analogously, \(p_1\) will not increase its cost as it would lose with \(p_3\) in the first iteration and its only supporter \(v_1\) would pay \(\frac{7B}{36}\) for \(p_3\), leaving insufficient \(\frac{5B}{36}\) for \(p_1\).
For this reason, \(\mathbf{c}= (\mathbf{c}(p_1) = \frac{7B}{36}, \mathbf{c}(p_2) = \frac{8B}{36}, \mathbf{c}(p_3) = \frac{21B}{36})\) is a MESApr for the given instance.
One can show in an analogous way that \(\mathbf{c}' = (\mathbf{c}'(p_1) = \frac{8B}{36}, \mathbf{c}'(p_2) = \frac{7B}{36}, \mathbf{c}'(p_3) = \frac{21B}{36})\) is also MESApr for the given instance. ◻
Instance | \(|P|\) | \(|V|\) | Budget | Vote Len. | Rule | |
---|---|---|---|---|---|---|
Wesola | 29 | 1182 | \(1 011\)k PLN | 7.87 | \(\text{BasicAV}\) | |
Kleine Wereld | 52 | 426 | 250k EUR | 11.93 | \(\text{BasicAV}\) |
We move on to the experimental analysis of our games for real-life PB instances from Pabulib [14]. 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 are available in . We have also analyzed many other instances from Pabulib. We show some of them in . While all of them lead to similar conclusions, the instances we chose are particularly illustrative.
We perform two experiments. First, we take a given PB instance and the original costs reported for the projects. Then, for each project we compute its best response. Second, we seek equilibiria in the games defined by our instances (with zero delivery costs).
Figure 5: Winning and losing margins in real-life PB. Each bar shows a single project (the projects are ordered by their approval score, shown on the \({x}\) axis). Green and red ones give best responses (where green means a winning margin and red means a losing one). Black rectangles show the original costs, with budget \(1 011\)k PLN for Wesola and 250k EUR for Kleine Wereld..
Take a PB instance \(E\) and a PB rule \(f\). Intuitively, for each project \(p\) its best response \({\mathit{br}}(p)\) is the highest cost such that if we use it instead of \(\mathit{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 \(f\), then we let its winning margin be \({\mathit{br}}(p) - \mathit{cost}(p)\), and if it is losing then we let its losing margin be \(\mathit{cost}(p) - {\mathit{br}}(p)\).
In we show the winning and losing margins (and, hence, the best responses) for all the projects from our two PB instances. For \(\text{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 in Kleine Wereld). In principle, under \(\text{BasicAV}\) if a project receives few votes even making it cheap will not make it funded, unless it is so cheap that it is selected simply because nothing else could fit within the budget left. For \(\text{AV/Cost}\) the best responses roughly correspond to the numbers of approvals each project got; the some, roughly, holds for \(\text{Phragm\'en}\) and \(\text{MES\text{-}Apr/Ph}\). The margins for \(\text{MES\text{-}Cost/Ph}\) are significantly different. In particular, for \(\text{MES\text{-}Cost/Ph}\), several most-approved projects usually have much higher winning margins than the rest, unlike for \(\text{AV/Cost}\), \(\text{Phragm\'en}\) and \(\text{MES\text{-}Apr/Ph}\).
The main general observation is that unless a project received relatively few approvals, then typically its proposers could have reported a much higher cost. This suggests that they should choose reasonable project costs that get their projects completed, rather than minimize the costs as much as possible, with the hope that this would improve their chances. Yet, of course, there are projects where lowering their costs could get them funded (see, e.g, and the first project for Wesola under \(\text{AV/Cost}\), \(\text{Phragm\'en}\), or \(\text{MES\text{-}Apr/Ph}\)).
In the second experiment, our goal was to compute (approximate) equilibria for our two instances under our rules. While for \(\text{BasicAV}\), \(\text{AV/Cost}\), and \(\text{MES\text{-}Cost/Ph}\) we could compute the equilibria using results from the previous section,5 this would not be possible for \(\text{Phragm\'en}\) and \(\text{MES\text{-}Apr/Ph}\). Instead, we simulate certain dynamics (for the rules where we can compute equilibria directly, our dynamics give nearly identical results, so we expect that the results are also meaningful for the other rules, albeit with no guarantees6).
Given a 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 or her project’s cost. Specifically, the proposer chooses a number \(x\) between \(0\) and \(\mathit{cost}/10\) uniformly at random (where \(\mathit{cost}\) is the current project’s cost) and if their project was losing in the previous iteration, then the proposer decreases its cost by \(x\), and if 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 cost). We expect to converge to an NE, if one exists, after running sufficiently many iterations.
In we present the results of the dynamics, that is, the obtained strategy profiles, after \(10 \;000\) iterations. Under \(\text{BasicAV}\), as expected, all the budget goes to the project with the most votes. Under \(\text{AV/Cost}\), every project ends up with a cost proportional to its support. Like in the previous experiment, \(\text{Phragm\'en}\) and \(\text{MES\text{-}Apr/Ph}\) produce similar results, while those of \(\text{MES\text{-}Cost/Ph}\) remain different. For \(\text{BasicAV}\), \(\text{AV/Cost}\), and \(\text{MES\text{-}Cost/Ph}\) most of the projects “reached” the costs predicted by the equilibrium.7
The main conclusion from this experiment (supported also by simulations for other PB instances; see ) is that under \(\text{AV/Cost}\), \(\text{Phragm\'en}\), and \(\text{MES\text{-}Apr/Ph}\) the proposers are incentivized to use costs that mostly reflect the number of approvals they receive. Under \(\text{MES\text{-}Cost/Ph}\), most strongly supported projects, as well as those that are supported by many voters who do not approve other, more popular projects, can request notably higher costs. Consequently, in an equilibrium the \(\text{MES\text{-}Cost/Ph}\) rule funds fewer, more expensive projects than \(\text{AV/Cost}\), \(\text{Phragm\'en}\), and \(\text{MES\text{-}Apr/Ph}\). We view this observation as one of the more important take-home messages from our work, which can be used to favor \(\text{MES\text{-}Cost/Ph}\) in practice (while funding some cheap projects is important, funding only such projects is logistically problematic for cities, as it requires significant effort in coordinating their implementation).
Figure 6: Strategy profiles after \({10 \;000}\) iterations of our dynamics. Bars represent the projects ( in the order of their approval score, depicted on the \({x}\) axis). The green bars show final costs of the winning projects (the brighter part emphasizes the increase, as compared to the original cost). The red bars show final costs of losing projects. Black outlines denote the original costs of the projects. Black triangles mark the originally winning projects. Brown circles denote the equilibrium costs (for rules where we can compute it)..
We have introduced a game-theoretic framework capturing strategic cost selection of projects in participatory budgeting scenarios. Focusing on \(\text{BasicAV}\), \(\text{AV/Cost}\), \(\text{Phragm\'en}\), and \(\text{MES}\) rules, we explored the conditions under which NE exist in such games. Then, using real-life election data, we explored the effects of iterative, profitable changes in projects’ costs. We believe to have set the groundwork for further theoretical and experimental study based on our framework. We envision a number of directions for future work. One is a natural computational question of establishing the complexity of deciding if equilibria exist in our games. Further, studying a more involved class of games emerging from relaxing our basic assumptions seems a very interesting and promising research avenue. In particular, it is compelling to verify whether the increased model complexity still leads to the observed phenomena, or rather introduces new dynamics.
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).
Here, we present experimental results for four additional PB instances held in 2022 in different districts of Warsaw, Poland, i.e., in Bemowo, Bielany, Wilanow, and Wlochy. Details regarding these datasets are presented in . In we present the winning and losing margins in additional real-life PB instances, and in we present the strategy profiles after \(10'000\) iterations of our dynamics.
Moreover, in 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.
Instance | \(|P|\) | \(|V|\) | Budget | Vote Len. | Rule |
---|---|---|---|---|---|
Bemowo | 83 | 5181 | 4854279 | 10.8 | \(\text{BasicAV}\) |
Bielany | 98 | 4957 | 5258802 | 9.8 | \(\text{BasicAV}\) |
Wilanow | 35 | 2359 | 1516962 | 9.59 | \(\text{BasicAV}\) |
Wlochy | 43 | 2221 | 1719224 | 9.51 | \(\text{BasicAV}\) |
Rule | Original Margins | 10000 it. Margins | |||
Winning | Losing | Winning | Losing | ||
\(\text{BasicAV}\) | \(1830 \pm 1283\) | \(122 \pm 182\) | 0 | \(24 \pm 37\) | |
\(\text{AV/Cost}\) | \(150 \pm 104\) | \(225 \pm 257\) | \(1 \pm 3\) | \(0.2 \pm 0.1\) | |
\(\text{Phragm\'en}\) | \(141 \pm 91\) | \(220 \pm 261\) | \(3 \pm 3\) | \(0.9 \pm 0.7\) | |
\(\text{MES\text{-}Apr/Ph}\) | \(150 \pm 95\) | \(223 \pm 264\) | \(3 \pm 4\) | \(2 \pm 2\) | |
\(\text{MES\text{-}Cost/Ph}\) | \(250 \pm 323\) | \(205 \pm 244\) | \(1 \pm 2\) | \(1 \pm 2\) | |
\(\text{BasicAV}\) | \(1447 \pm 1355\) | \(218 \pm 205\) | 0 | \(2 \pm 2\) | |
\(\text{AV/Cost}\) | \(157 \pm 128\) | \(171 \pm 150\) | \(0.9 \pm 2\) | \(0.2 \pm 0.3\) | |
\(\text{Phragm\'en}\) | \(146 \pm 121\) | \(176 \pm 154\) | \(4 \pm 3\) | \(0.9 \pm 0.9\) | |
\(\text{MES\text{-}Apr/Ph}\) | \(148 \pm 121\) | \(176 \pm 151\) | \(3 \pm 4\) | \(1 \pm 2\) | |
\(\text{MES\text{-}Cost/Ph}\) | \(172 \pm 193\) | \(180 \pm 154\) | \(3 \pm 6\) | \(3 \pm 4\) | |
\(\text{BasicAV}\) | \(265 \pm 249\) | \(64 \pm 51\) | 0 | 0 | |
\(\text{AV/Cost}\) | \(86 \pm 27\) | \(55 \pm 31\) | \(0.3 \pm 0.4\) | \(0.2 \pm 0.1\) | |
\(\text{Phragm\'en}\) | \(69 \pm 31\) | \(51 \pm 37\) | \(2 \pm 1\) | \(0.9 \pm 1\) | |
\(\text{MES\text{-}Apr/Ph}\) | \(79 \pm 33\) | \(43 \pm 37\) | \(2 \pm 1\) | \(0.7 \pm 0.7\) | |
\(\text{MES\text{-}Cost/Ph}\) | \(70 \pm 56\) | \(65 \pm 45\) | \(0.1 \pm 0.1\) | \(0.4 \pm 0.5\) | |
\(\text{BasicAV}\) | \(536 \pm 399\) | \(87 \pm 80\) | 0 | 0 | |
\(\text{AV/Cost}\) | \(87 \pm 59\) | \(51 \pm 34\) | \(2 \pm 2\) | \(0.1 \pm 0.0\) | |
\(\text{Phragm\'en}\) | \(77 \pm 52\) | \(66 \pm 41\) | \(2 \pm 2\) | \(0.3 \pm 0.2\) | |
\(\text{MES\text{-}Apr/Ph}\) | \(89 \pm 56\) | \(58 \pm 37\) | \(2 \pm 1\) | \(0.7 \pm 0.8\) | |
\(\text{MES\text{-}Cost/Ph}\) | \(79 \pm 120\) | \(95 \pm 64\) | \(1 \pm 2\) | \(2 \pm 4\) | |
\(\text{BasicAV}\) | \(532 \pm 524\) | \(46 \pm 35\) | 0 | 0 | |
\(\text{AV/Cost}\) | \(107 \pm 49\) | \(56 \pm 48\) | \(0.8 \pm 1.0\) | \(0.1 \pm 0.1\) | |
\(\text{Phragm\'en}\) | \(83 \pm 52\) | \(62 \pm 42\) | \(3 \pm 3\) | \(2 \pm 1\) | |
\(\text{MES\text{-}Apr/Ph}\) | \(85 \pm 53\) | \(64 \pm 45\) | \(2 \pm 2\) | \(1 \pm 1\) | |
\(\text{MES\text{-}Cost/Ph}\) | \(138 \pm 186\) | \(56 \pm 46\) | \(0.2 \pm 0.2\) | \(0.4 \pm 0.5\) | |
\(\text{BasicAV}\) | \(117 \pm 78\) | \(14 \pm 11\) | 0 | \(1.0 \pm 0.0\) | |
\(\text{AV/Cost}\) | \(12 \pm 8\) | \(12 \pm 12\) | \(0.1 \pm 0.1\) | \(0.1 \pm 0.0\) | |
\(\text{Phragm\'en}\) | \(10 \pm 8\) | \(10 \pm 11\) | \(0.5 \pm 0.6\) | \(0.2 \pm 0.2\) | |
\(\text{MES\text{-}Apr/Ph}\) | \(11 \pm 7\) | \(11 \pm 11\) | \(0.4 \pm 0.6\) | \(0.2 \pm 0.2\) | |
\(\text{MES\text{-}Cost/Ph}\) | \(26 \pm 34\) | \(11 \pm 11\) | \(2 \pm 1\) | \(0.1 \pm 0.0\) |
Figure 7: Winning and losing margins in real-life PB. The green bars denote the max-winning cost (with the brighter part depicting the winning margin). The red bars denote the min-losing cost (with the white part depicting the losing margin). Black outlines denote the original costs of the projects..
Figure 8: The results of the game after 10000 iterations. The green bars denote the final costs of the projects that are winning in the 10000th iteration (with the brighter part emphasizing the increase in comparison to the original costs). The red bars denote the final costs of projects that are losing in the 10000th iteration. Black outlines denote the original costs of the projects. Black triangles mark the projects that were winning in the 0th iteration (i.e., the original PB). Brown circles are denoting the NE..
As in the introductory example, we view the notion of a project broadly. By choosing a lower cost means proposing a smaller-scale project and choosing a higher cost means a proposing a larger-scale one, with possibly extra features and higher quality.↩︎
As we assume that each project is approved by at least one voter, upon completion there is no unfunded project that could be included in the outcome without exceeding the budget.↩︎
We note that under the current definition \(\alpha_p\) is unique and so finding the minimum such value is not needed. However, we maintain this formulation for consistency with the literature.↩︎
For \(\text{MES\text{-}Cost/Ph}\) this follows from the fact that, for our instances, the equilibrium for \(\text{{MES\text{-}Cost}}\) is exhaustive.↩︎
For \(\text{Phragm\'en}\) and \(\text{MES\text{-}Apr/Ph}\) there may be no NE. We do not have an immediate way of checking this, but the results suggest that the profiles that we find are, at least, close to being equilibria.↩︎
In the equilibrium, all projects should be winning, so we should observe no red bars. Their existence means that the equilibrium was not reached within 10 000 iterations.↩︎