Method of equal shares

Motivation

The method is an alternative to the knapsack algorithm which is used by most cities even though it is a disproportional method. For example, if 51% of the population support 10 red projects and 49% support 10 blue projects, and the money suffices only for 10 projects, the knapsack budgeting will choose the 10 red supported by the 51%, and ignore the 49% altogether. In contrast, the method of equal shares would pick 5 blue and 5 red projects.

The method guarantees proportional representation: it satisfies a strong variant of the justified representation axiom adapted to participatory budgeting. This says that a group of X% of the population will have X% of the budget spent on projects supported by the group (assuming that all members of the group have voted the same or at least similarly).

Intuitive explanation

In the context of participatory budgeting the method assumes that the municipal budget is initially evenly distributed among the voters. Each time a project is selected its cost is divided among those voters who supported the project and who still have money. The savings of these voters are decreased accordingly. If the voters vote via approval ballots, then the cost of a selected project is distributed equally among the voters; if they vote via cardinal ballots, then the cost is distributed proportionally to the utilities the voters enjoy from the project. The rule selects the projects which can be paid this way, starting with those that minimise the voters' marginal costs per utility.

Example 1

The following example with 100 voters and 9 projects illustrates how the rule works. In this example the total budget equals $1000, that is it allows to select five from the nine available projects. See the animated diagram below, which illustrates the behaviour of the rule.

The budget is first divided equally among the voters, thus each voters gets $10. Project ${\displaystyle \mathrm{D}}$ received most votes, and it is selected in the first round. If we divided the cost of ${\displaystyle \mathrm{D}}$ equally among the voters, who supported ${\displaystyle \mathrm{D}}$, each of them would pay ${\displaystyle \mathrm{\$}200/66\approx \mathrm{\$}3.03}$. In contrast, if we selected, e.g., ${\displaystyle \mathrm{E}}$, then the cost per voter would be ${\displaystyle \mathrm{\$}200/46\approx \mathrm{\$}4.34}$. The method selects first the project that minimises the price per voter.

Note that in the last step project ${\displaystyle \mathrm{H}}$ was selected even though there were projects which were supported by more voters, say ${\displaystyle \mathrm{E}}$. This is because, the money that the supporters of ${\displaystyle \mathrm{E}}$ had the right to control, was used previously to justify the selection of ${\displaystyle \mathrm{D}}$, ${\displaystyle \mathrm{A}}$, and ${\displaystyle \mathrm{C}}$. On the other hand, the voters who voted for ${\displaystyle \mathrm{H}}$ form 20% of the population, and so shall have right to decide about 20% of the budget. Those voters supported only ${\displaystyle \mathrm{H}}$, and this is why this project was selected.

For a more detailed example including cardinal ballots see Example 2.

Definition

This section presents the definition of the rule for cardinal ballots. See discussion for a discussion on how to apply this definition to approval ballots and ranked ballots.

We have a set of projects ${\displaystyle P=\{p_1,p_2,\dots ,p_m\}}$, and a set of voters ${\displaystyle N=\{1,2,\dots ,n\}}$. For each project ${\displaystyle p\in P}$ let ${\displaystyle \mathrm{c}\mathrm{o}\mathrm{s}\mathrm{t}(p)}$ denote its cost, and let ${\displaystyle b}$ denote the size of the available municipal budget. For each voter ${\displaystyle i\in N}$ and each project ${\displaystyle p\in P}$ let ${\displaystyle u_i(p)}$ denote the ${\displaystyle i}$'s cardinal ballot on ${\displaystyle c}$, that is the number that quantifies the level of appreciation of voter ${\displaystyle i}$ towards project ${\displaystyle p}$.

The method of equal shares works in rounds. At the beginning it puts an equal part of the budget, in each voter's virtual bank account, ${\displaystyle b_i=b/n}$. In each round the method selects one project according to the following procedure.

1. For each not-yet-selected project ${\displaystyle p\in P}$ the method tries to spread the cost of the project proportionally to the cardinal ballots submitted by the voters, taking into account the fact that some voters might have already run out of money. Formally, for ${\displaystyle \rho \ge 0}$, we say that a not-yet-selected project ${\displaystyle p}$ is ${\displaystyle \rho }$-affordable if ${\displaystyle \begin{array}{c}\sum _{i\in N}min\left(b_i,u_i(p)\cdot \rho \right)=\mathrm{c}\mathrm{o}\mathrm{s}\mathrm{t}(p)\text{.}\end{array}}$ Intuitively, if a project ${\displaystyle p}$ is ${\displaystyle \rho }$-affordable then, the cost of the project can be spread among the voters in a way that each voter pays the price-per-utility of at most ${\displaystyle \rho }$.
2. If there are no ${\displaystyle \rho }$-affordable projects then the method of equal shares finishes. This happens when for each not-yet selected project ${\displaystyle p}$ the remaining amount of money in the private accounts of those voters who submitted a positive ballot on ${\displaystyle p}$ is lower than the cost of ${\displaystyle p}$: ${\displaystyle \sum _{i\in N:u_i(p)>0}{b}_i<\mathrm{c}\mathrm{o}\mathrm{s}\mathrm{t}(p)\text{.}}$ It might happen that when the method finishes, there is still some money left that would allow to fund a few more projects. This money can be spent using the simple greedy procedure that select the remaining projects ${\displaystyle p}$ starting from those with the lowest ratio ${\displaystyle \mathrm{c}\mathrm{o}\mathrm{s}\mathrm{t}(p)/\sum _{i\in N}{u}_i(p)}$, until the budget is exhausted. Yet, the method of equal shares keeps most of its properties independently of how the remaining budget is spent.
3. If there is at least one not-yet-selected ${\displaystyle \rho }$-affordable project, the method selects the project ${\displaystyle p}$ that is ${\displaystyle \rho }$-affordable for the lowest value of ${\displaystyle \rho }$ (the project that minimises the price-per-utility that the voters need to pay). The voters' budgets are updated accordingly: for each ${\displaystyle i\in N}$ the method sets ${\displaystyle b_i:=max(0,b_i-u_i(p)\cdot \rho )}$.

Example 2

The following diagram illustrates the behaviour of the method.

Discussion

This section provides a discussion on other variants of the method of equal shares.

Other types of ballots

The method of equal shares can be used with other types of voters ballots.

Approval ballots

The method can be applied in two ways to the setting where the voters vote by marking the projects they like (see Example 1):

1. Setting ${\displaystyle u_i(p)=\mathrm{c}\mathrm{o}\mathrm{s}\mathrm{t}(p)}$ if project ${\displaystyle p}$ is approved by voter ${\displaystyle i}$, and ${\displaystyle u_i(p)=0}$ otherwise. This assumes that the utility of a voter equals the total amount of money spent on the projects supported by the voter. This assumption is commonly used in other methods of counting approval ballots for participatory budgeting, for example in the knapsack algorithm, and typically results in selecting fewer more expensive projects.
2. Setting ${\displaystyle u_i(p)=1}$ if project ${\displaystyle p}$ is approved by voter ${\displaystyle i}$, and ${\displaystyle u_i(p)=0}$ otherwise. This assumes that the utility of a voter equals the number of approved selected projects. This typically results in selecting more but less expensive projects.

Ranked ballots

The method applies to the model where the voters vote by ranking the projects from the most to the least preferred one. Assuming lexicographic preferences, one can use the convention that ${\displaystyle u_i(p)}$ depends on the position of project ${\displaystyle p}$ in the voter's ${\displaystyle i}$ ranking, and that ${\displaystyle u_i(p)/u_i(p^{\prime })\to \mathrm{\infty }}$, whenever ${\displaystyle i}$ ranks ${\displaystyle p}$ as more preferred than ${\displaystyle p^{\prime }}$.

Formally, the method is defined as follows.

For each voter ${\displaystyle i\in N}$ let ${\displaystyle {\succ }_i}$ denote the ranking of voter ${\displaystyle i}$ over the projects. For example, ${\displaystyle Y{\succ }_{i}X{\succ }_{i}Z}$ means that ${\displaystyle Y}$ is the most preferred project from the perspective of voter ${\displaystyle i}$, ${\displaystyle X}$ is the voter's second most preferred project and ${\displaystyle Z}$ is the least preferred project. In this example we say that project ${\displaystyle Y}$ is ranked in the first position and write ${\displaystyle {\mathrm{p}\mathrm{o}\mathrm{s}}_i(Y)=1}$, project ${\displaystyle X}$ is ranked in the second position (${\displaystyle {\mathrm{p}\mathrm{o}\mathrm{s}}_i(X)=2}$), and ${\displaystyle Z}$ in the third position (${\displaystyle {\mathrm{p}\mathrm{o}\mathrm{s}}_i(Z)=3}$).

Each voter is initially assigned an equal part of the budget ${\displaystyle b_i=b/n}$. The rule proceeds in rounds, in each round:

1. For each not-yet-selected project ${\displaystyle p\in P}$ we say that ${\displaystyle p}$ is ${\displaystyle \delta }$-affordable if the remaining budget of the voters who rank ${\displaystyle p}$ at position ${\displaystyle \delta }$ or better is greater than or equal to ${\displaystyle \mathrm{c}\mathrm{o}\mathrm{s}\mathrm{t}(p)}$: ${\displaystyle \begin{array}{c}\sum _{i\in N:{\mathrm{p}\mathrm{o}\mathrm{s}}_i(p)\le \delta }{b}_i\ge \mathrm{c}\mathrm{o}\mathrm{s}\mathrm{t}(p)\text{.}\end{array}}$
2. If no project is affordable the rule stops. This happens when the total remaining budget of the voters ${\displaystyle \sum _{i\in N}{b}_i}$ is lower than the cost of each not-yet-selected project.
3. If there are affordable projects, then the rule picks the not-yet-selected project ${\displaystyle p}$ that is ${\displaystyle \delta }$-affordable for the lowest value of ${\displaystyle \delta }$. The budgets of the voters are updated accordingly. First, the cost is equally spread among the voters who rank ${\displaystyle p}$ at the first position. If the budgets of these voters are insufficient to cover the cost of the project, the remaining part of the cost is further spread equally among the voters who rank ${\displaystyle p}$ at the second position, etc. Formally we start with ${\displaystyle \delta :=1}$ and ${\displaystyle \mathrm{c}\mathrm{o}\mathrm{s}\mathrm{t}:=\mathrm{c}\mathrm{o}\mathrm{s}\mathrm{t}(p)}$, and proceed in the loop:
   1. If ${\displaystyle \sum _{i\in N:{\mathrm{p}\mathrm{o}\mathrm{s}}_i(p)=\delta }{b}_i\ge \mathrm{c}\mathrm{o}\mathrm{s}\mathrm{t}}$ then we find ${\displaystyle \rho }$ such that ${\displaystyle \sum _{i\in N:{\mathrm{p}\mathrm{o}\mathrm{s}}_i(p)=\delta }min(\rho ,b_i)=\mathrm{c}\mathrm{o}\mathrm{s}\mathrm{t}}$ and for each voter ${\displaystyle i\in N}$ with ${\displaystyle {\mathrm{p}\mathrm{o}\mathrm{s}}_i(p)=\delta }$ we set ${\displaystyle b_i:=max(0,b_i-\rho )}$.
   2. Otherwise, we update the cost: ${\displaystyle \mathrm{c}\mathrm{o}\mathrm{s}\mathrm{t}:=\mathrm{c}\mathrm{o}\mathrm{s}\mathrm{t}-\sum _{i\in N:{\mathrm{p}\mathrm{o}\mathrm{s}}_i(p)=\delta }{b}_i}$. We charge the voters: for each voter ${\displaystyle i\in N}$ with ${\displaystyle {\mathrm{p}\mathrm{o}\mathrm{s}}_i(p)=\delta }$ we set ${\displaystyle b_i:=0}$, and move to the next position ${\displaystyle \delta :=\delta +1}$.

Committee elections

In the context of committee elections the projects are typically called candidates. It is assumed that cost of each candidate equals one; then, the budget ${\displaystyle b}$ can be interpreted as the number of candidates in the committee that should be selected.

Unspent budget

The method of equal shares can return a set of projects that does not exhaust the whole budget. There are multiple ways to use the unspent budget:

1. The utilitarian method: the projects ${\displaystyle p}$ are selected in the order of ${\displaystyle \frac{\sum _{i\in N}{u}_i(p)}{\mathrm{c}\mathrm{o}\mathrm{s}\mathrm{t}(p)}}$ until no further project can be selected within the budget limit.
2. Adjusting initial budget: the initial budget can be adjusted to the highest possible value which makes the method select projects, whose total cost does not exceed the unadjusted budget.

Comparison to other voting methods

In the context of committee elections the method is often compared to Proportional Approval Voting (PAV), since both methods are proportional (they satisfy the axiom of Extended Justified Representation (EJR)). The difference between the two methods can be described as follow.

1. The method of equal shares (MES) is computable in polynomial-time, and PAV is NP-hard to compute. The sequential variant of PAV is computable in polynomial-time, but does not satisfy Justified Representation.
2. PAV is Pareto-optimal, but MES is not.
3. MES is priceable. This means that it is possible to assign a fixed budget to each voter, and split each voter's budget among candidates he approves, such that each elected candidate is 'bought' by the candidates who approve him, and no unelected candidate can be bought by the remaining money of the voters who approve him. MES can be viewed as an implementation of Lindahl equilibrium in the discrete model, with the assumption that the customers sharing an item must pay the same price for the item.
4. MES extends to participatory budgeting and to cardinal ballots, whereas PAV does not satisfy Extended Justified Representation (EJR) when applied to either participatory budgeting or to cardinal ballots.

MES is similar to the Phragmen's sequential rule. The difference is that in MES the voters are given their budgets upfront, while in the Phragmen's sequential rule the voters earn money continuously over time. The methods compare as follows:

1. Both methods are computable in polynomial time, both are priceable, and both may fail Pareto-optimality.
2. MES satisfies Extended Justified Representation (EJR), while the Phragmen's sequential rule satisfies Proportional Justified Representation, a weaker variant of the property.
3. The Phragmen's sequential rule satisfies committee monotonicity, while MES fails the property.
4. MES extends to participatory budgeting with cardinal ballots, which is not the case for the Phragmen's sequential rule.

MES with adjusting initial budget, PAV and Phragmen's voting rules can all be viewed as extensions of the D'Hondt method to the setting where the voters can vote for individual candidates rather than for political parties. MES further extends to participatory budgeting.

Implementation

Below there is a Python implementation of the method that applies to participatory budgeting. For the model of committee elections, the rules is implemented as a part of the Python package abcvoting.

<span id="mwAX0"></span><span class="kn" id="mwAX4">import</span> <span class="nn" id="mwAX8">math</span> <span class="k" id="mwAYA">def</span> <span class="nf" id="mwAYE">method_of_equal_shares</span><span class="p" id="mwAYI">(</span><span class="n" id="mwAYM">N</span><span class="p" id="mwAYQ">,</span> <span class="n" id="mwAYU">C</span><span class="p" id="mwAYY">,</span> <span class="n" id="mwAYc">cost</span><span class="p" id="mwAYg">,</span> <span class="n" id="mwAYk">u</span><span class="p" id="mwAYo">,</span> <span class="n" id="mwAYs">b</span><span class="p" id="mwAYw">):</span> <span class="w" id="mwAY0"> </span><span class="sd" id="mwAY4">"""Method of Equal Shares</span> <span class="sd" id="mwAY8"> Args:</span> <span class="sd" id="mwAZA"> N: a list of voters.</span> <span class="sd" id="mwAZE"> C: a list of projects (candidates).</span> <span class="sd" id="mwAZI"> cost: a dictionary that assigns each project its cost.</span> <span class="sd" id="mwAZM"> b: the total available budget.</span> <span class="sd" id="mwAZQ"> u: a dictionary; u[c][i] is the value that voter i assigns to candidate c.</span> <span class="sd" id="mwAZU"> an empty entry means that the corresponding value u[c][i] equals 0.</span> <span class="sd" id="mwAZY"> """</span> <span class="n" id="mwAZc">W</span> <span class="o" id="mwAZg">=</span> <span class="nb" id="mwAZk">set</span><span class="p" id="mwAZo">()</span> <span class="n" id="mwAZs">total_utility</span> <span class="o" id="mwAZw">=</span> <span class="p" id="mwAZ0">{</span><span class="n" id="mwAZ4">c</span><span class="p" id="mwAZ8">:</span> <span class="nb" id="mwAaA">sum</span><span class="p" id="mwAaE">(</span><span class="n" id="mwAaI">u</span><span class="p" id="mwAaM">[</span><span class="n" id="mwAaQ">c</span><span class="p" id="mwAaU">]</span><span class="o" id="mwAaY">.</span><span class="n" id="mwAac">values</span><span class="p" id="mwAag">())</span> <span class="k" id="mwAak">for</span> <span class="n" id="mwAao">c</span> <span class="ow" id="mwAas">in</span> <span class="n" id="mwAaw">C</span><span class="p" id="mwAa0">}</span> <span class="n" id="mwAa4">supporters</span> <span class="o" id="mwAa8">=</span> <span class="p" id="mwAbA">{</span><span class="n" id="mwAbE">c</span><span class="p" id="mwAbI">:</span> <span class="nb" id="mwAbM">set</span><span class="p" id="mwAbQ">([</span><span class="n" id="mwAbU">i</span> <span class="k" id="mwAbY">for</span> <span class="n" id="mwAbc">i</span> <span class="ow" id="mwAbg">in</span> <span class="n" id="mwAbk">N</span> <span class="k" id="mwAbo">if</span> <span class="n" id="mwAbs">u</span><span class="p" id="mwAbw">[</span><span class="n" id="mwAb0">c</span><span class="p" id="mwAb4">][</span><span class="n" id="mwAb8">i</span><span class="p" id="mwAcA">]</span> <span class="o" id="mwAcE">></span> <span class="mi" id="mwAcI">0</span><span class="p" id="mwAcM">])</span> <span class="k" id="mwAcQ">for</span> <span class="n" id="mwAcU">c</span> <span class="ow" id="mwAcY">in</span> <span class="n" id="mwAcc">C</span><span class="p" id="mwAcg">}</span> <span class="n" id="mwAck">budget</span> <span class="o" id="mwAco">=</span> <span class="p" id="mwAcs">{</span><span class="n" id="mwAcw">i</span><span class="p" id="mwAc0">:</span> <span class="n" id="mwAc4">b</span> <span class="o" id="mwAc8">/</span> <span class="nb" id="mwAdA">len</span><span class="p" id="mwAdE">(</span><span class="n" id="mwAdI">N</span><span class="p" id="mwAdM">)</span> <span class="k" id="mwAdQ">for</span> <span class="n" id="mwAdU">i</span> <span class="ow" id="mwAdY">in</span> <span class="n" id="mwAdc">N</span><span class="p" id="mwAdg">}</span> <span class="k" id="mwAdk">while</span> <span class="kc" id="mwAdo">True</span><span class="p" id="mwAds">:</span> <span class="n" id="mwAdw">next_candidate</span> <span class="o" id="mwAd0">=</span> <span class="kc" id="mwAd4">None</span> <span class="n" id="mwAd8">lowest_rho</span> <span class="o" id="mwAeA">=</span> <span class="nb" id="mwAeE">float</span><span class="p" id="mwAeI">(</span><span class="s2" id="mwAeM">"inf"</span><span class="p" id="mwAeQ">)</span> <span class="k" id="mwAeU">for</span> <span class="n" id="mwAeY">c</span> <span class="ow" id="mwAec">in</span> <span class="n" id="mwAeg">C</span><span class="o" id="mwAek">.</span><span class="n" id="mwAeo">difference</span><span class="p" id="mwAes">(</span><span class="n" id="mwAew">W</span><span class="p" id="mwAe0">):</span> <span class="k" id="mwAe4">if</span> <span class="n" id="mwAe8">_leq</span><span class="p" id="mwAfA">(</span><span class="n" id="mwAfE">cost</span><span class="p" id="mwAfI">[</span><span class="n" id="mwAfM">c</span><span class="p" id="mwAfQ">],</span> <span class="nb" id="mwAfU">sum</span><span class="p" id="mwAfY">([</span><span class="n" id="mwAfc">budget</span><span class="p" id="mwAfg">[</span><span class="n" id="mwAfk">i</span><span class="p" id="mwAfo">]</span> <span class="k" id="mwAfs">for</span> <span class="n" id="mwAfw">i</span> <span class="ow" id="mwAf0">in</span> <span class="n" id="mwAf4">supporters</span><span class="p" id="mwAf8">[</span><span class="n" id="mwAgA">c</span><span class="p" id="mwAgE">]])):</span> <span class="n" id="mwAgI">supporters_sorted</span> <span class="o" id="mwAgM">=</span> <span class="nb" id="mwAgQ">sorted</span><span class="p" id="mwAgU">(</span><span class="n" id="mwAgY">supporters</span><span class="p" id="mwAgc">[</span><span class="n" id="mwAgg">c</span><span class="p" id="mwAgk">],</span> <span class="n" id="mwAgo">key</span><span class="o" id="mwAgs">=</span><span class="k" id="mwAgw">lambda</span> <span class="n" id="mwAg0">i</span><span class="p" id="mwAg4">:</span> <span class="n" id="mwAg8">budget</span><span class="p" id="mwAhA">[</span><span class="n" id="mwAhE">i</span><span class="p" id="mwAhI">]</span> <span class="o" id="mwAhM">/</span> <span class="n" id="mwAhQ">u</span><span class="p" id="mwAhU">[</span><span class="n" id="mwAhY">c</span><span class="p" id="mwAhc">][</span><span class="n" id="mwAhg">i</span><span class="p" id="mwAhk">])</span> <span class="n" id="mwAho">price</span> <span class="o" id="mwAhs">=</span> <span class="n" id="mwAhw">cost</span><span class="p" id="mwAh0">[</span><span class="n" id="mwAh4">c</span><span class="p" id="mwAh8">]</span> <span class="n" id="mwAiA">util</span> <span class="o" id="mwAiE">=</span> <span class="n" id="mwAiI">total_utility</span><span class="p" id="mwAiM">[</span><span class="n" id="mwAiQ">c</span><span class="p" id="mwAiU">]</span> <span class="k" id="mwAiY">for</span> <span class="n" id="mwAic">i</span> <span class="ow" id="mwAig">in</span> <span class="n" id="mwAik">supporters_sorted</span><span class="p" id="mwAio">:</span> <span class="k" id="mwAis">if</span> <span class="n" id="mwAiw">_leq</span><span class="p" id="mwAi0">(</span><span class="n" id="mwAi4">price</span> <span class="o" id="mwAi8">*</span> <span class="n" id="mwAjA">u</span><span class="p" id="mwAjE">[</span><span class="n" id="mwAjI">c</span><span class="p" id="mwAjM">][</span><span class="n" id="mwAjQ">i</span><span class="p" id="mwAjU">],</span> <span class="n" id="mwAjY">budget</span><span class="p" id="mwAjc">[</span><span class="n" id="mwAjg">i</span><span class="p" id="mwAjk">]</span> <span class="o" id="mwAjo">*</span> <span class="n" id="mwAjs">util</span><span class="p" id="mwAjw">):</span> <span class="k" id="mwAj0">break</span> <span class="n" id="mwAj4">price</span> <span class="o" id="mwAj8">-=</span> <span class="n" id="mwAkA">budget</span><span class="p" id="mwAkE">[</span><span class="n" id="mwAkI">i</span><span class="p" id="mwAkM">]</span> <span class="n" id="mwAkQ">util</span> <span class="o" id="mwAkU">-=</span> <span class="n" id="mwAkY">u</span><span class="p" id="mwAkc">[</span><span class="n" id="mwAkg">c</span><span class="p" id="mwAkk">][</span><span class="n" id="mwAko">i</span><span class="p" id="mwAks">]</span> <span class="n" id="mwAkw">rho</span> <span class="o" id="mwAk0">=</span> <span class="n" id="mwAk4">price</span> <span class="o" id="mwAk8">/</span> <span class="n" id="mwAlA">util</span> \ <span class="k" id="mwAlE">if</span> <span class="ow" id="mwAlI">not</span> <span class="n" id="mwAlM">math</span><span class="o" id="mwAlQ">.</span><span class="n" id="mwAlU">isclose</span><span class="p" id="mwAlY">(</span><span class="n" id="mwAlc">util</span><span class="p" id="mwAlg">,</span> <span class="mi" id="mwAlk">0</span><span class="p" id="mwAlo">)</span> <span class="ow" id="mwAls">and</span> <span class="ow" id="mwAlw">not</span> <span class="n" id="mwAl0">math</span><span class="o" id="mwAl4">.</span><span class="n" id="mwAl8">isclose</span><span class="p" id="mwAmA">(</span><span class="n" id="mwAmE">price</span><span class="p" id="mwAmI">,</span> <span class="mi" id="mwAmM">0</span><span class="p" id="mwAmQ">)</span> \ <span class="k" id="mwAmU">else</span> <span class="n" id="mwAmY">budget</span><span class="p" id="mwAmc">[</span><span class="n" id="mwAmg">supporters_sorted</span><span class="p" id="mwAmk">[</span><span class="o" id="mwAmo">-</span><span class="mi" id="mwAms">1</span><span class="p" id="mwAmw">]]</span> <span class="o" id="mwAm0">/</span> <span class="n" id="mwAm4">u</span><span class="p" id="mwAm8">[</span><span class="n" id="mwAnA">c</span><span class="p" id="mwAnE">][</span><span class="n" id="mwAnI">supporters_sorted</span><span class="p" id="mwAnM">[</span><span class="o" id="mwAnQ">-</span><span class="mi" id="mwAnU">1</span><span class="p" id="mwAnY">]]</span> <span class="k" id="mwAnc">if</span> <span class="n" id="mwAng">rho</span> <span class="o" id="mwAnk"><</span> <span class="n" id="mwAno">lowest_rho</span><span class="p" id="mwAns">:</span> <span class="n" id="mwAnw">next_candidate</span> <span class="o" id="mwAn0">=</span> <span class="n" id="mwAn4">c</span> <span class="n" id="mwAn8">lowest_rho</span> <span class="o" id="mwAoA">=</span> <span class="n" id="mwAoE">rho</span> <span class="k" id="mwAoI">if</span> <span class="n" id="mwAoM">next_candidate</span> <span class="ow" id="mwAoQ">is</span> <span class="kc" id="mwAoU">None</span><span class="p" id="mwAoY">:</span> <span class="k" id="mwAoc">break</span> <span class="n" id="mwAog">W</span><span class="o" id="mwAok">.</span><span class="n" id="mwAoo">add</span><span class="p" id="mwAos">(</span><span class="n" id="mwAow">next_candidate</span><span class="p" id="mwAo0">)</span> <span class="k" id="mwAo4">for</span> <span class="n" id="mwAo8">i</span> <span class="ow" id="mwApA">in</span> <span class="n" id="mwApE">N</span><span class="p" id="mwApI">:</span> <span class="n" id="mwApM">budget</span><span class="p" id="mwApQ">[</span><span class="n" id="mwApU">i</span><span class="p" id="mwApY">]</span> <span class="o" id="mwApc">-=</span> <span class="nb" id="mwApg">min</span><span class="p" id="mwApk">(</span><span class="n" id="mwApo">budget</span><span class="p" id="mwAps">[</span><span class="n" id="mwApw">i</span><span class="p" id="mwAp0">],</span> <span class="n" id="mwAp4">lowest_rho</span> <span class="o" id="mwAp8">*</span> <span class="n" id="mwAqA">u</span><span class="p" id="mwAqE">[</span><span class="n" id="mwAqI">next_candidate</span><span class="p" id="mwAqM">][</span><span class="n" id="mwAqQ">i</span><span class="p" id="mwAqU">])</span> <span class="k" id="mwAqY">return</span> <span class="n" id="mwAqc">_complete_utilitarian</span><span class="p" id="mwAqg">(</span><span class="n" id="mwAqk">N</span><span class="p" id="mwAqo">,</span> <span class="n" id="mwAqs">C</span><span class="p" id="mwAqw">,</span> <span class="n" id="mwAq0">cost</span><span class="p" id="mwAq4">,</span> <span class="n" id="mwAq8">u</span><span class="p" id="mwArA">,</span> <span class="n" id="mwArE">b</span><span class="p" id="mwArI">,</span> <span class="n" id="mwArM">W</span><span class="p" id="mwArQ">)</span> <span class="c1" id="mwArU"># one of the possible completions</span> <span class="k" id="mwArY">def</span> <span class="nf" id="mwArc">_complete_utilitarian</span><span class="p" id="mwArg">(</span><span class="n" id="mwArk">N</span><span class="p" id="mwAro">,</span> <span class="n" id="mwArs">C</span><span class="p" id="mwArw">,</span> <span class="n" id="mwAr0">cost</span><span class="p" id="mwAr4">,</span> <span class="n" id="mwAr8">u</span><span class="p" id="mwAsA">,</span> <span class="n" id="mwAsE">b</span><span class="p" id="mwAsI">,</span> <span class="n" id="mwAsM">W</span><span class="p" id="mwAsQ">):</span> <span class="n" id="mwAsU">util</span> <span class="o" id="mwAsY">=</span> <span class="p" id="mwAsc">{</span><span class="n" id="mwAsg">c</span><span class="p" id="mwAsk">:</span> <span class="nb" id="mwAso">sum</span><span class="p" id="mwAss">([</span><span class="n" id="mwAsw">u</span><span class="p" id="mwAs0">[</span><span class="n" id="mwAs4">c</span><span class="p" id="mwAs8">][</span><span class="n" id="mwAtA">i</span><span class="p" id="mwAtE">]</span> <span class="k" id="mwAtI">for</span> <span class="n" id="mwAtM">i</span> <span class="ow" id="mwAtQ">in</span> <span class="n" id="mwAtU">N</span><span class="p" id="mwAtY">])</span> <span class="k" id="mwAtc">for</span> <span class="n" id="mwAtg">c</span> <span class="ow" id="mwAtk">in</span> <span class="n" id="mwAto">C</span><span class="p" id="mwAts">}</span> <span class="n" id="mwAtw">committee_cost</span> <span class="o" id="mwAt0">=</span> <span class="nb" id="mwAt4">sum</span><span class="p" id="mwAt8">([</span><span class="n" id="mwAuA">cost</span><span class="p" id="mwAuE">[</span><span class="n" id="mwAuI">c</span><span class="p" id="mwAuM">]</span> <span class="k" id="mwAuQ">for</span> <span class="n" id="mwAuU">c</span> <span class="ow" id="mwAuY">in</span> <span class="n" id="mwAuc">W</span><span class="p" id="mwAug">])</span> <span class="k" id="mwAuk">while</span> <span class="kc" id="mwAuo">True</span><span class="p" id="mwAus">:</span> <span class="n" id="mwAuw">next_candidate</span> <span class="o" id="mwAu0">=</span> <span class="kc" id="mwAu4">None</span> <span class="n" id="mwAu8">highest_util</span> <span class="o" id="mwAvA">=</span> <span class="nb" id="mwAvE">float</span><span class="p" id="mwAvI">(</span><span class="s2" id="mwAvM">"-inf"</span><span class="p" id="mwAvQ">)</span> <span class="k" id="mwAvU">for</span> <span class="n" id="mwAvY">c</span> <span class="ow" id="mwAvc">in</span> <span class="n" id="mwAvg">C</span><span class="o" id="mwAvk">.</span><span class="n" id="mwAvo">difference</span><span class="p" id="mwAvs">(</span><span class="n" id="mwAvw">W</span><span class="p" id="mwAv0">):</span> <span class="k" id="mwAv4">if</span> <span class="n" id="mwAv8">_leq</span><span class="p" id="mwAwA">(</span><span class="n" id="mwAwE">committee_cost</span> <span class="o" id="mwAwI">+</span> <span class="n" id="mwAwM">cost</span><span class="p" id="mwAwQ">[</span><span class="n" id="mwAwU">c</span><span class="p" id="mwAwY">],</span> <span class="n" id="mwAwc">b</span><span class="p" id="mwAwg">):</span> <span class="k" id="mwAwk">if</span> <span class="n" id="mwAwo">util</span><span class="p" id="mwAws">[</span><span class="n" id="mwAww">c</span><span class="p" id="mwAw0">]</span> <span class="o" id="mwAw4">/</span> <span class="n" id="mwAw8">cost</span><span class="p" id="mwAxA">[</span><span class="n" id="mwAxE">c</span><span class="p" id="mwAxI">]</span> <span class="o" id="mwAxM">></span> <span class="n" id="mwAxQ">highest_util</span><span class="p" id="mwAxU">:</span> <span class="n" id="mwAxY">next_candidate</span> <span class="o" id="mwAxc">=</span> <span class="n" id="mwAxg">c</span> <span class="n" id="mwAxk">highest_util</span> <span class="o" id="mwAxo">=</span> <span class="n" id="mwAxs">util</span><span class="p" id="mwAxw">[</span><span class="n" id="mwAx0">c</span><span class="p" id="mwAx4">]</span> <span class="o" id="mwAx8">/</span> <span class="n" id="mwAyA">cost</span><span class="p" id="mwAyE">[</span><span class="n" id="mwAyI">c</span><span class="p" id="mwAyM">]</span> <span class="k" id="mwAyQ">if</span> <span class="n" id="mwAyU">next_candidate</span> <span class="ow" id="mwAyY">is</span> <span class="kc" id="mwAyc">None</span><span class="p" id="mwAyg">:</span> <span class="k" id="mwAyk">break</span> <span class="n" id="mwAyo">W</span><span class="o" id="mwAys">.</span><span class="n" id="mwAyw">add</span><span class="p" id="mwAy0">(</span><span class="n" id="mwAy4">next_candidate</span><span class="p" id="mwAy8">)</span> <span class="n" id="mwAzA">committee_cost</span> <span class="o" id="mwAzE">+=</span> <span class="n" id="mwAzI">cost</span><span class="p" id="mwAzM">[</span><span class="n" id="mwAzQ">next_candidate</span><span class="p" id="mwAzU">]</span> <span class="k" id="mwAzY">return</span> <span class="n" id="mwAzc">W</span> <span class="k" id="mwAzg">def</span> <span class="nf" id="mwAzk">_leq</span><span class="p" id="mwAzo">(</span><span class="n" id="mwAzs">a</span><span class="p" id="mwAzw">,</span> <span class="n" id="mwAz0">b</span><span class="p" id="mwAz4">):</span> <span class="k" id="mwAz8">return</span> <span class="n" id="mwA0A">a</span> <span class="o" id="mwA0E"><</span> <span class="n" id="mwA0I">b</span> <span class="ow" id="mwA0M">or</span> <span class="n" id="mwA0Q">math</span><span class="o" id="mwA0U">.</span><span class="n" id="mwA0Y">isclose</span><span class="p" id="mwA0c">(</span><span class="n" id="mwA0g">a</span><span class="p" id="mwA0k">,</span> <span class="n" id="mwA0o">b</span><span class="p" id="mwA0s">)</span>

Extensions

Fairstein, Meir and Gal extend MES to a setting in which some projects may be substitute goods.

Empirical support

Fairstein, Benade and Gal compare MES to greedy aggregation methods. They find that greedy aggregation leads to outcomes that are highly sensitive to the input format used, and the fraction of the population that participates. In contrast, MES leads to outcomes that are not sensitive to the type of voting format used. This means that MES can be used with approval ballots, ordinal ballots or cardinal ballots, without much difference in the outcome. These outcomes are stable even when only 25%-50% of the population participates in the election.

Fairstein, Meir, Vilenchik and Gal study variants of MES both on real and synthetic datasets. They find that these variants do very well in practice, both with respect to social welfare and with respect to justified representation.