Method of Equal Shares

From electowiki
(Redirected from MES)
Wikipedia has an article on:

The Method of Equal Shares [1] (sometimes referred to as MES) is a proportional method of counting ballots that applies to participatory budgeting and to committee elections.[2][3] MES ideally uses rated ballots, but the authors also detail ways to use MES with ranked or approval ballots.

Motivation

The method is an alternative to knapsack voting 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 completely ignore the wishes of the 49%.[4] In contrast, the method of equal shares would pick 5 blue and 5 red projects.

The method guarantees proportional representation: it satisfies the strongest known variant of the justified representation axiom that is known to be satisfiable in participatory budgeting.

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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{D}} received most votes, and it is selected in the first round. If we divided the cost of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{D}} equally among the voters, who supported Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{D}} , each of them would pay Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \$200/66 \approx \$3.03} . In contrast, if we selected, e.g., Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{E}} , then the cost per voter would be Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{H}} was selected even though there were projects which were supported by more voters, say Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{E}} . This is because, the money that the supporters of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{E}} had the right to control, was used previously to justify the selection of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{D}} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{A}} , and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{C}} . On the other hand, the voters who voted for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{H}} form 20% of the population, and so shall have right to decide about 20% of the budget. Those voters supported only Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P = \{p_1, p_2, \ldots, p_m\}} , and a set of voters Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N = \{1, 2, \ldots, n\}} . For each project Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p \in P} let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{cost}(p)} denote its cost, and let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b} denote the size of the available municipal budget. For each voter Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i \in N} and each project Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p \in P} let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle u_i(p) } denote the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} 's cardinal ballot on Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} , that is the number that quantifies the level of appreciation of voter Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} towards project Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rho \ge 0} , we say that a not-yet-selected project Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rho} -affordable if
    Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \sum_{i \in N} \min\left( b_i, u_i(p) \cdot \rho \right) = \mathrm{cost}(p) \text{.} \end{align}}
    Intuitively, if a project Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rho} .
  2. If there are no Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rho} -affordable projects then the method of equal shares finishes. This happens when for each not-yet selected project Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} the remaining amount of money in the private accounts of those voters who submitted a positive ballot on Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} is lower than the cost of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} : Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textstyle\sum_{i \in N\colon u_i(p) > 0} b_i < \mathrm{cost}(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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} starting from those with the lowest ratio Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{cost}(p)/\textstyle\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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rho} -affordable project, the method selects the project Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} that is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rho} -affordable for the lowest value of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rho} (the project that minimises the price-per-utility that the voters need to pay). The voters' budgets are updated accordingly: for each Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i \in N} the method sets Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 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 with knapsack voting, and typically results in selecting fewer more expensive projects.
  2. Setting if project is approved by voter , and 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

For ranked ballots, MES uses a method related to the expanding approvals rule. Like EAR, it passes proportionality for solid coalitions.

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 depends on the position of project in the voter's ranking, and that , whenever ranks as more preferred than .

Formally, the method 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 ().

Each voter is initially assigned an equal part of the budget . The rule proceeds in rounds, in each round:

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

  2. If no project is affordable the rule stops. This happens when the total remaining budget of the voters 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 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:
    1. If then we find Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rho} such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textstyle \sum_{i \in N \colon \mathrm{pos}_i(p) =\delta} \min(\rho, b_i) =\mathrm{cost}} and for each voter Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i \in N} with we set .
    2. Otherwise, we update the cost: . We charge the voters: for each voter with we set , and move to the next position .


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 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 (Bloc Score Voting): the projects are selected in the order of 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.
  3. Other Cardinal PR systems: The remaining winners can be found with the use of other Cardinal PR systems. Sequentially Spent Score would be a natural completion since it maintains the concept of spending.

Implementation

Below there is a Python implementation of the method.

import math

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

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

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 method_of_equal_shares(N, C, cost, u, b):
    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

References

  1. In early papers the method has been also referred to as Rule X.
  2. Peters, Dominik; Skowron, Piotr (2020). "Proportionality and the Limits of Welfarism". Proceedings of the 21st ACM Conference on Economics and Computation. EC'20: 793–794. arXiv:1911.11747. doi:10.1145/3391403.3399465. ISBN 9781450379755.
  3. Pierczyński, Grzegorz; Peters, Dominik; Skowron, Piotr (2020). "Proportional Participatory Budgeting with Additive Utilities". Proceedings of the 2021 Conference on Neural Information Processing Systems. NeurIPS'21. arXiv:2008.13276.
  4. 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.