The method of equal shares was first discussed in the context of committee elections in 2019, initially under the name "Rule X".121314 From 2022, the literature has referred to the rule as the method of equal shares, particularly when referring to it in the context of participatory budgeting algorithms.1516 The method 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).17
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 percent of the population support 10 red projects and 49 percent support 10 blue projects, and the money suffices only for 10 projects, the knapsack budgeting will choose the 10 red supported by the 51 percent, and ignore the 49 percent altogether.18 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.19 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 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.
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 D {\displaystyle \mathrm {D} } received most votes, and it is selected in the first round. If we divided the cost of D {\displaystyle \mathrm {D} } equally among the voters, who supported D {\displaystyle \mathrm {D} } , each of them would pay $ 200 / 66 ≈ $ 3.03 {\displaystyle \$200/66\approx \$3.03} . In contrast, if we selected, e.g., E {\displaystyle \mathrm {E} } , then the cost per voter would be $ 200 / 46 ≈ $ 4.34 {\displaystyle \$200/46\approx \$4.34} . The method selects first the project that minimises the price per voter.
Note that in the last step project H {\displaystyle \mathrm {H} } was selected even though there were projects which were supported by more voters, say E {\displaystyle \mathrm {E} } . This is because, the money that the supporters of E {\displaystyle \mathrm {E} } had the right to control, was used previously to justify the selection of D {\displaystyle \mathrm {D} } , A {\displaystyle \mathrm {A} } , and C {\displaystyle \mathrm {C} } . On the other hand, the voters who voted for H {\displaystyle \mathrm {H} } form 20 percent of the population, and so shall have right to decide about 20 percent of the budget. Those voters supported only H {\displaystyle \mathrm {H} } , and this is why this project was selected.
For a more detailed example including cardinal ballots see Example 2.
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 P = { p 1 , p 2 , … , p m } {\displaystyle P=\{p_{1},p_{2},\ldots ,p_{m}\}} , and a set of voters N = { 1 , 2 , … , n } {\displaystyle N=\{1,2,\ldots ,n\}} . For each project p ∈ P {\displaystyle p\in P} let c o s t ( p ) {\displaystyle \mathrm {cost} (p)} denote its cost, and let b {\displaystyle b} denote the size of the available municipal budget. For each voter i ∈ N {\displaystyle i\in N} and each project p ∈ P {\displaystyle p\in P} let u i ( p ) {\displaystyle u_{i}(p)} denote the i {\displaystyle i} 's cardinal ballot on c {\displaystyle c} , that is the number that quantifies the level of appreciation of voter i {\displaystyle i} towards project p {\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, b i = b / n {\displaystyle b_{i}=b/n} . In each round the method selects one project according to the following procedure.
The following diagram illustrates the behaviour of the method.
This section provides a discussion on other variants of the method of equal shares.
The method of equal shares can be used with other types of voters 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):
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 u i ( p ) {\displaystyle u_{i}(p)} depends on the position of project p {\displaystyle p} in the voter's i {\displaystyle i} ranking, and that u i ( p ) / u i ( p ′ ) → ∞ {\displaystyle u_{i}(p)/u_{i}(p')\to \infty } , whenever i {\displaystyle i} ranks p {\displaystyle p} as more preferred than p ′ {\displaystyle p'} .
Formally, the method is defined as follows.
For each voter i ∈ N {\displaystyle i\in N} let ≻ i {\displaystyle \succ _{i}} denote the ranking of voter i {\displaystyle i} over the projects. For example, Y ≻ i X ≻ i Z {\displaystyle Y\succ _{i}X\succ _{i}Z} means that Y {\displaystyle Y} is the most preferred project from the perspective of voter i {\displaystyle i} , X {\displaystyle X} is the voter's second most preferred project and Z {\displaystyle Z} is the least preferred project. In this example we say that project Y {\displaystyle Y} is ranked in the first position and write p o s i ( Y ) = 1 {\displaystyle \mathrm {pos} _{i}(Y)=1} , project X {\displaystyle X} is ranked in the second position ( p o s i ( X ) = 2 {\displaystyle \mathrm {pos} _{i}(X)=2} ), and Z {\displaystyle Z} in the third position ( p o s i ( Z ) = 3 {\displaystyle \mathrm {pos} _{i}(Z)=3} ).
Each voter is initially assigned an equal part of the budget b i = b / n {\displaystyle b_{i}=b/n} . The rule proceeds in rounds, in each round:
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 b {\displaystyle b} can be interpreted as the number of candidates in the committee that should be selected.
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:
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)).2021 The difference between the two methods can be described as follow.
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.2526 The methods compare as follows:
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.3334 MES further extends to participatory budgeting.35
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.
Fairstein, Meir and Gal36 extend MES to a setting in which some projects may be substitute goods.
Fairstein, Benade and Gal37 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 to 50 percent of the population participates in the election.
Fairstein, Meir, Vilenchik and Gal38 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.
Lackner, Martin; Skowron, Piotr (2023). Multi-Winner Voting with Approval Preferences. SpringerBriefs in Intelligent Systems. arXiv:2007.01795. doi:10.1007/978-3-031-09016-5. ISBN 978-3-031-09015-8. S2CID 244921148. 978-3-031-09015-8 ↩
Peters, Dominik; Pierczyński, Grzegorz; Skowron, Piotr (2021). "Proportional Participatory Budgeting with Additive Utilities". Proceedings of the 2021 Conference on Neural Information Processing Systems. NeurIPS'21. arXiv:2008.13276. https://openreview.net/pdf?id=5rm0b_fsNZ ↩
Peters, Dominik; Skowron, Piotr (2020). "Proportionality and the Limits of Welfarism". Proceedings of the 21st ACM Conference on Economics and Computation. EC'20. pp. 793–794. arXiv:1911.11747. doi:10.1145/3391403.3399465. ISBN 9781450379755. S2CID 208291203. 9781450379755 ↩
Freeman, Rupert; Kahng, Anson; Pennock, David (2020). "Proportionality in Approval-Based Elections with a Variable Number of Winners". Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence. IJCAI'20. Vol. 1. pp. 132–138. doi:10.24963/ijcai.2020/19. ISBN 978-0-9992411-6-5. S2CID 211052991. 978-0-9992411-6-5 ↩
Conitzer, Vincent; Freeman, Rupert; Shah, Nisarg (2017). "Fair Public Decision Making". Proceedings of the 2017 ACM Conference on Economics and Computation. EC'17. pp. 629–646. arXiv:1611.04034. doi:10.1145/3033274.3085125. ISBN 9781450345279. S2CID 30188911. 9781450345279 ↩
"Zielony Milion - rusza nowatorski projekt BO w Wieliczce [WIDEO]". Głos24 (in Polish). 2023-03-09. Retrieved 2023-03-11. https://glos24.pl/zielony-milion-rusza-nowatorski-projekt-bo-w-wieliczce-wideo ↩
Stadt Aarau. "Abstimmungsphase - Stadtidee Aarau". stadtidee.aarau.ch. Retrieved 2023-03-11. https://www.stadtidee.aarau.ch/abstimmungsphase.html/1937 ↩
Rey, Simon; Maly, Jan (2023-03-08). "The (Computational) Social Choice Take on Indivisible Participatory Budgeting". arXiv:2303.00621 [cs.GT]. /wiki/ArXiv_(identifier) ↩
Aziz, Haris; Lee, Barton E. (2019). "Proportionally Representative Participatory Budgeting with Ordinal Preferences". arXiv:1911.00864 [cs.GT]. /wiki/ArXiv_(identifier) ↩
Fluschnik, Till; Skowron, Piotr; Triphaus, Mervin; Wilker, Kai (2019-07-17). "Fair Knapsack". Proceedings of the AAAI Conference on Artificial Intelligence. 33: 1941–1948. doi:10.1609/aaai.v33i01.33011941. ISSN 2374-3468. https://doi.org/10.1609%2Faaai.v33i01.33011941 ↩
Aziz, Haris; Brill, Markus; Conitzer, Vincent; Elkind, Edith; Freeman, Rupert; Walsh, Toby (2017). "Justified representation in approval-based committee voting". Social Choice and Welfare. 48 (2): 461–485. arXiv:1407.8269. doi:10.1007/s00355-016-1019-3. S2CID 8564247. https://ideas.repec.org/a/spr/sochwe/v48y2017i2d10.1007_s00355-016-1019-3.html ↩
Peters, Dominik; Pierczynski, Grzegorz; Shah, Nisarg; Skowron, Piotr (2021). "Market-Based Explanations of Collective Decisions". Proceedings of the AAAI Conference on Artificial Intelligence. AAAI'21. 35 (6): 5656–5663. doi:10.1609/aaai.v35i6.16710. S2CID 222132258. https://ojs.aaai.org/index.php/AAAI/article/view/16710 ↩
Janson, Svante (2018-10-12). "Phragmen's and Thiele's election methods". arXiv:1611.08826 [math.HO]. /wiki/ArXiv_(identifier) ↩
Brill, Markus; Freeman, Rupert; Janson, Svante; Lackner, Martin (2017-02-10). "Phragmén's Voting Methods and Justified Representation". Proceedings of the AAAI Conference on Artificial Intelligence. 31 (1). arXiv:2102.12305. doi:10.1609/aaai.v31i1.10598. ISSN 2374-3468. S2CID 2290202. https://ojs.aaai.org/index.php/AAAI/article/view/10598 ↩
Brill, Markus; Laslier, Jean-François; Skowron, Piotr (2018). "Multiwinner Approval Rules as Apportionment Methods". Journal of Theoretical Politics. 30 (3): 358–382. arXiv:1611.08691. doi:10.1177/0951629818775518. S2CID 10535322. /wiki/ArXiv_(identifier) ↩
Fairstein, Roy; Meir, Reshef; Gal, Kobi (2021). "Proportional Participatory Budgeting with Substitute Projects". arXiv:2106.05360 [cs.GT]. /wiki/ArXiv_(identifier) ↩
Fairstein, Roy; Benadè, Gerdus; Gal, Kobi (2023). "Participatory Budgeting Design for the Real World". arXiv:2302.13316 [cs.GT]. /wiki/ArXiv_(identifier) ↩
Fairstein, Roy; Meir, Reshef; Vilenchik, Dan; Gal, Kobi (2022). "Welfare vs. Representation in Participatory Budgeting". arXiv:2201.07546 [cs.GT]. /wiki/ArXiv_(identifier) ↩