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. ◻

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. ◻

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. ◻

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. ◻

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.

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.

Having proven , we completed the argument for the correctness of  and . ◻

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. ◻

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. ◻

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):

1. \(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'\).

2. The approvals for the projects in \(P''\) are analogous, except that they are approved by the voters from \(V''\).

We set the delivery costs \(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)\).

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:

1. 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).

2. 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.

3. 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.

4. 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).

4.10.0.1 Case A

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.

4.10.0.2 Case B\('\)

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:

1. 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}}'\)).

2. 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.

4.10.0.3 Case B\(''\)

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:

1. 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}}'\)).

2. 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. ◻

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:

1. 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)\).

2. 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).

3. 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'\).

4. Remove all supporters of \(p^*\) from \(V'\) and remove \(p^*\) from \(P'\).

5. 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}}\).

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))\). ◻

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. ◻

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. ◻

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. ◻

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.

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. ◻

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. ◻