Method of equal shares

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.^[9]

In contrast, MES guarantees proportional representation. Specifically, it satisfies an extended variant of the justified representation axiom, adapted to participatory budgeting.^[3] 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.

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 b_i units of virtual money; usually, b_i 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.

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 ${\displaystyle \rho \geq 0}$, we say that project ${\displaystyle p}$ is ${\displaystyle \rho }$-affordable if

${\displaystyle {\begin{aligned}\sum _{i\in N,i{\text{ approves }}p}\min \left(b_{i},\rho \right)=\mathrm {cost} (p){\text{.}}\end{aligned}}}$

Here, each supporter i with too little virtual money pays b_i, whereas all other supporters pay ${\displaystyle \rho }$. 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 ${\displaystyle \rho }$-affordable for the smallest ${\displaystyle \rho }$. That is, we chose a project that minimizes the maximum amount paid by a single supporter.

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 ${\displaystyle P=\{p_{1},p_{2},\ldots ,p_{m}\}}$, and a set of voters ${\displaystyle N=\{1,2,\ldots ,n\}}$. For each project ${\displaystyle p\in P}$ let ${\displaystyle \mathrm {cost} (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 p}$, that is the number that quantifies the level of appreciation of voter ${\displaystyle i}$ towards project ${\displaystyle p}$. For any ${\displaystyle \rho \geq 0}$, we say that project ${\displaystyle p}$ is ${\displaystyle \rho }$-affordable if

${\displaystyle {\begin{aligned}\sum _{i\in N}\min \left(b_{i},\rho \cdot u_{i}(p)\right)=\mathrm {cost} (p){\text{.}}\end{aligned}}}$

Intuitively, if a project p is ${\displaystyle \rho }$-affordable, then its cost can be spread among the voters in a way that each voter pays the price-per-utility of at most ${\displaystyle \rho }$ (voters with enough money will pay ${\displaystyle \rho \cdot u_{i}(p)}$, and the other voters will pay their entire remaining money b_i).

If there is at least one not-yet-selected ${\displaystyle \rho }$-affordable project, MES selects the project 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 above description of MES with approval ballots can be seen as a special case of MES with cardinal ballots where agents have binary utilities, ${\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 definition typically results in selecting more but less expensive projects, as a project with a lower cost will typically be ${\displaystyle \rho }$-affordable for a smaller value of ${\displaystyle \rho }$.

Alternatively, one can assume cost utilities, ${\displaystyle u_{i}(p)=\mathrm {cost} (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.

Suppose 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')\to \infty }$, whenever ${\displaystyle i}$ ranks ${\displaystyle p}$ as more preferred than ${\displaystyle p'}$. In this case, MES 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 {pos} _{i}(Y)=1}$, project ${\displaystyle X}$ is ranked in the second position (${\displaystyle \mathrm {pos} _{i}(X)=2}$), and ${\displaystyle Z}$ in the third position (${\displaystyle \mathrm {pos} _{i}(Z)=3}$).

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 {cost} (p)}$:

${\displaystyle {\begin{aligned}\sum _{i\in N\colon \mathrm {pos} _{i}(p)\leq \delta }b_{i}\geq \mathrm {cost} (p){\text{.}}\end{aligned}}}$

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 {cost}$ :=\mathrm {cost} (p)} , and proceed in the loop:

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)).^[10][2] 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^[2] 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.^[11]
4. 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.^[3]

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.^[12][13] The methods compare as follows:

1. Both methods are computable in polynomial time, both are priceable,^[2] and both may fail Pareto-optimality.^[1]
2. MES satisfies EJR, while the Phragmen's sequential rule satisfies proportional justified representation, a weaker variant of the property.^[3][12]
3. The Phragmen's sequential rule satisfies committee monotonicity, while MES fails the property.^{[1]: Appendix A}
4. MES extends to participatory budgeting with cardinal ballots, which is not the case for the Phragmen's sequential rule.^[3]

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.^[14][2] MES further extends to participatory budgeting.^[3]

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.

import math

def method_of_equal_shares(N, C, cost, u, b):
    """Method of Equal Shares

    Args:
      N:     a list of voters.
      C:     a list of projects (candidates).
      cost:  a dictionary that assigns each project its cost.
      b:     the total available budget.
      u:     a dictionary; u[c][i] is the value that voter i assigns to candidate c.
             an empty entry means that the corresponding value u[c][i] equals 0.
    """
    W = set()
    total_utility = {c: sum(u[c].values()) for c in C}
    supporters = {c: set([i for i in N if u[c][i] > 0]) for c in C}
    budget = {i: b / len(N) for i in N}
    while True:
        next_candidate = None
        lowest_rho = float("inf")
        for c in C.difference(W):
            if _leq(cost[c], sum([budget[i] for i in supporters[c]])):
                supporters_sorted = sorted(supporters[c], key=lambda i: budget[i] / u[c][i])
                price = cost[c]
                util = total_utility[c]
                for i in supporters_sorted:
                    if _leq(price * u[c][i], budget[i] * util):
                        break
                    price -= budget[i]
                    util -= u[c][i]
                rho = price / util \
                        if not math.isclose(util, 0) and not math.isclose(price, 0) \
                        else budget[supporters_sorted[-1]] / u[c][supporters_sorted[-1]]
                if rho < lowest_rho:
                    next_candidate = c
                    lowest_rho = rho
        if next_candidate is None:
            break
        W.add(next_candidate)
        for i in N:
            budget[i] -= min(budget[i], lowest_rho * u[next_candidate][i])
    return _complete_utilitarian(N, C, cost, u, b, W)  # one of the possible completions

def _complete_utilitarian(N, C, cost, u, b, W):
    util = {c: sum([u[c][i] for i in N]) for c in C}
    committee_cost = sum([cost[c] for c in W])
    while True:
        next_candidate = None
        highest_util = float("-inf")
        for c in C.difference(W):
            if _leq(committee_cost + cost[c], b):
                if util[c] / cost[c] > highest_util:
                    next_candidate = c
                    highest_util = util[c] / cost[c]
        if next_candidate is None:
            break
        W.add(next_candidate)
        committee_cost += cost[next_candidate]
    return W

def _leq(a, b):
    return a < b or math.isclose(a, b)

Fairstein, Benade and Gal compare MES to greedy aggregation methods.^[15] 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 Gal study variants of MES both on real and synthetic datasets.^[16] They find that these variants do very well in practice, both with respect to social welfare and with respect to justified representation.

In 2023, MES was being used in a participatory budgeting program in the Polish city of Wieliczka.^[17] The program, known as Green Million (Zielony Milion), was set to distribute 1 million złoty to ecological projects proposed by residents of the city.

MES was also used in a participatory budgeting program in the Swiss cities of Aarau in 2023 (Stadtidee)^[18] and Winterthur, as well as the Dutch city of Assen.^[7]

Papasotiropoulos, Pishbin, Skibski, Skowron and Was present several problems with MES, and with the EJR requirement in general.^[19]

Some recent variants of MES can fund not only entire projects but also fractions of projects.

Fractional equal shares

Papasotiropoulos, Pishbin, Skibski, Skowron and Was describe a variant they call FrES (fractional equal shares).^{[19]: App.A} The idea is that, instead of funding an entire project, it is possible to fund a fraction f<1 of a project, for a fraction f of its cost, and for a fraction f of its utility. Formally, for any ${\displaystyle \rho \geq 0}$ and f in (0,1], we say that project ${\displaystyle p}$ is ${\displaystyle (f,\rho )}$-affordable if

${\displaystyle {\begin{aligned}\sum _{i\in N}\min \left(b_{i},\rho \cdot f\cdot u_{i}(p)\right)=f\cdot \mathrm {cost} (p){\text{.}}\end{aligned}}}$

At each round, MES selects a project p that is ${\displaystyle (f,\rho )}$-affordable for the lowest value of ${\displaystyle \rho }$. It then funds the largest possible fraction f of p.

Note that, when f is sufficiently small, the minimum in the above expression will always be ${\displaystyle \rho \cdot f\cdot u_{i}(p)}$. Hence, ${\displaystyle \rho }$ will always be equal to ${\displaystyle {\textrm {cost}}(p)/\sum _{i\in N,b_{i}>0}u_{i}(c)}$, and f will always be the minimum between the yet-unfunded fraction of p, and ${\displaystyle \min _{i\in S}b_{i}/(\rho \cdot u_{i}(p))}$.

They prove that FrES satisfies a fractional variant of EJR, which they call fractional EJR.^{[19]: Thm.1}

• Equal Shares – a website explaining and discussing the method of equal shares in several languages