The method of equal shares (MES) is a participatory budgeting algorithm specifically designed to guarantee extended justified representation (a form of proportional representation). It was originally developed for committee elections (under the name Rule X). It was later adapted to participatory budgeting (PB) and to simultaneous public decisions. It can be used with any available ballot format, including approval ballots, ranked ballots or cardinal ballots. MES has been used for participatory budgeting in various European cities.
MES can be described as a member of a class of voting methods called expanding approvals rules introduced earlier in 2019 by Aziz and Lee for ordinal preferences (that include approval ballots).
Motivation Most cities running participatory budgeting use the knapsack algorithm, 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 there is only funding for 10 projects, knapsack budgeting will choose the 10 red supported by the 51%, and the 49% will go unfunded.
In contrast, MES guarantees proportional representation. Specifically, it satisfies an extended variant of the justified representation axiom, adapted to participatory budgeting. This says that a group of X percent of the population will have X percent 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). In particular, in the above example, MES would pick at least 5 blue and at least 4 red projects (the 10th project could be either red or blue, depending on the completion method used).
In the context of committee elections, there are other rules with similar justified representation guarantees, such as proportional approval voting. However, MES runs in polynomial time, and thus can be applied easily even to realistic elections, with a large number of voters.
Procedure MES has several variants, all of which have the following structure for participatory budgeting:
1. Initialization – The set of "winners" (chosen candidates) is initialized to an empty set. Each voter i is allocated bi units of virtual money; usually, bi equals the total available budget divided by n (the number of voters).
2. Main loop – Each round consists of two steps:
(a) One of the remaining candidates is chosen and added to the set of winners. (b) The chosen candidate is funded by its supporters; that is, each voter who supports it "pays" a certain amount from their virtual money, such that the sum of all payments equals the candidate cost.
As the total virtual money decreases at each round, eventually no more projects can be funded; at that point, the main loop ends.
3. Completion – If the available budget is not exhausted (i.e., some voters still have virtual money, but it is not sufficient to fund any remaining candidate), then some completion method can be used to add some candidates, until no more candidates can be added subject to the budget constraints.
For committee elections the same structure is used, except that the "cost" of each candidate is assumed to be 1, and the total available "budget" is the desired committee size (usually denoted k). So each voter initially receives k/n virtual money units.
MES variants differ in how they choose a candidate in each round, and how they distribute its cost among the agents.
Main loop: approval ballots and binary utilities If the voters vote via approval ballots, then MES aims to distribute the cost of a chosen project p as equally as possible among its supporters. Specifically:
If some s voters approve p, and each of them has at least cost(p)/s virtual money, then each of them pays exactly cost(p)/s. Otherwise, supporters with too little remaining money pay all their remaining money, and the remaining cost is divided equally among the remaining supporters. This means that each of the remaining supporters pays more than cost(p)/s.
Formally, for , we say that project is -affordable if
Here, each supporter i with too little virtual money pays bi, whereas all other supporters pay . Here are some examples.
A project with cost 100 is supported by 4 voters, with virtual money 25, 50, 75 and 100 respectively. As 100/4=25 and all supporters have at least 25 virtual money, all of them will pay 25—the project is 25-affordable. The agents will remain with 0, 25, 50 and 75 virtual money respectively. A project with cost 105 is supported by the same 4 voters, with virtual money 0, 25, 50 and 75. The first cannot contribute at all. The second cannot contribute 100/3, so they contributes their entire remaining 25. The remaining cost is 80. It can be divided equally among the third and fourth supporters, each of whom would pay 40. So the project is 40-affordable. The agents will remain with 0, 0, 10 and 35 virtual money respectively.
At each round, the chosen project is a project that is -affordable for the smallest . That is, we chose a project that minimizes the maximum amount paid by a single supporter.
Example 1 In the following example, there are 9 projects, each of which costs $200. There are 100 voters with approval ballots. The total budget equals $1000, which allows five projects to be selected from the available nine. See the animated diagram below, which illustrates the behaviour of the rule.
The budget is first divided equally among the voters; thus, each voter gets $10. Project received the most votes, and it is selected in the first round. If we divided the cost of equally among the voters who supported , each of them would pay . In contrast, if we selected , then the cost per voter would be . The method selects first the project that minimises the price per voter.
Note that in the last step, project was selected even though there were projects which were supported by more voters, say . This is because, the money that the supporters of had the right to control was used previously to justify the selection of , , and . On the other hand, the voters who voted for form 20 percent of the population and so shall have right to decide about 20 percent of the budget. Those voters supported only , and this is why this project was selected.
For a more detailed example including cardinal ballots, see Example 2.
Main loop: cardinal ballots If the voters vote via cardinal ballots, then MES aims to distribute the cost of a chosen project p proportionally to the utilities the voters enjoy from the project. Formally, we have a set of projects , and a set of voters . For each project let denote its cost and let denote the size of the available municipal budget.
For each voter and each project let denote the 's cardinal ballot on , that is the number that quantifies the level of appreciation of voter towards project . For any , we say that project is -affordable if
Intuitively, if a project p is -affordable, then its cost can be spread among the voters in a way that each voter pays the price-per-utility of at most (voters with enough money will pay , and the other voters will pay their entire remaining money bi).
If there is at least one not-yet-selected -affordable project, MES selects the project p that is -affordable for the lowest value of (the project that minimises the price-per-utility that the voters need to pay).
Example 2
The following diagram illustrates the behaviour of MES with cardinal ballots.
Main loop: approval ballots (again) The above description of MES with approval ballots can be seen as a special case of MES with cardinal ballots where agents have binary utilities, if project is approved by voter , and otherwise. This assumes that the utility of a voter equals the number of approved selected projects. This definition typically results in selecting more but less expensive projects, as a project with a lower cost will typically be -affordable for a smaller value of .
Alternatively, one can assume cost utilities, if project is approved by voter and 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.
Main loop: ranked ballots Suppose voters vote by ranking the projects from the most to the least preferred one. Assuming lexicographic preferences, one can use the convention that depends on the position of project in the voter's ranking, and that , whenever ranks as more preferred than . In this case, MES is defined as follows.
For each voter let denote the ranking of voter over the projects. For example, means that is the most preferred project from the perspective of voter , is the voter's second most preferred project and is the least preferred project. In this example we say that project is ranked in the first position and write , project is ranked in the second position (), and in the third position ().
For each not-yet-selected project we say that is -affordable if the remaining budget of the voters who rank at position or better is greater than or equal to :If there are affordable projects, then the rule picks the not-yet-selected project that is -affordable for the lowest value of . The budgets of the voters are updated accordingly. First, the cost is equally spread among the voters who rank 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 at the second position, etc. Formally we start with and , and proceed in the loop:
Completion methods 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:
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. 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. PAV is Pareto-optimal, but MES is not. 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. MES extends to participatory budgeting and to cardinal ballots, whereas PAV does not satisfy extended justified representation 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:
Both methods are computable in polynomial time, both are priceable, and both may fail Pareto-optimality. MES satisfies EJR, while the Phragmen's sequential rule satisfies proportional justified representation, a weaker variant of the property. The Phragmen's sequential rule satisfies committee monotonicity, while MES fails the property. MES extends to participatory budgeting with cardinal ballots, which is not the case for the Phragmen's sequential rule.