How to compute the results?
Online computation tool
We provide an online tool for computing the results of the Method of Equal Shares. It is available at https://equalshares.net/tools/compute. The tool is free to use and does not require any registration or installation.
Open the online computation tool →The tool allows the user to upload a data file containing all the votes using the standard .pb
format from pabulib.
It then computes the results of the Method of Equal Shares and displays them in a table, and also displays some additional statistics and information.
The tool supports all standard variants of the Method of Equal Shares.
No data is sent to any server; all computation is done locally in the user's browser. Users can disconnect from the internet after loading the page, and the tool will continue to work.
The tool only supports approval voting.
About the .pb
file format
The .pb
file format is a standard format for storing participatory budgeting data.
It is used by the pabulib library.
The format is a simple text format that can be edited with any text editor.
It contains information about the election instance (e.g. the location, date, and budget of the election),
about the projects (e.g. their names and costs), and about the votes (e.g. which projects each voter supports).
Here is a small example of a .pb
file:
META
key;value
description;Example election
num_projects;3
num_votes;4
budget;100000
vote_type;approval
PROJECTS
project_id;name;cost
1;Project 1;5000
2;Project 2;10000
3;Project 3;85000
VOTES
voter_id;vote
1;1,2
2;1
3;3
4;1,2,3
The pabutools
package
The pabutools
package is a free and open-source Python package that contains implementations of several voting rules for participatory budgeting, including the Method of Equal Shares.
It is available on GitHub.
The package can be installed via PyPI using pip
:
pip install pabutools
You can use the package to read a pabulib file and compute the results of the Method of Equal Shares as follows:
from pabutools.election import parse_pabulib, Cost_Sat
from pabutools.rules import method_of_equal_shares
instance, profile = parse_pabulib("filename.pb")
winners = method_of_equal_shares(
instance,
profile.as_multiprofile(),
sat_class=Cost_Sat,
voter_budget_increment=1 # use the completion method Add1
)
print(winners)
More details are available in the package documentation.
Code generator
Here, we provide short code snippets for computing the results of the Method of Equal Shares using Python or JavaScript. You can select the specific variant of the method that you wish to implement.
Language: Python
Ballot type: Approval ballots
Tie breaking: In favor of lower cost, then higher vote count
Completion method: Repeated increase of voter budgets by 1 currency unit
Comparison step: None
Numerical accuracy: Use floating point numbers
def equal_shares(voters, projects, cost, approvers, total_budget):
"""
Computes the Method of Equal Shares for Participatory Budgeting.
Args:
voters (list): A list of voter names.
projects (list): A list of project IDs.
cost (dict): A dictionary mapping project IDs to their respective costs.
approvers (dict): A dictionary mapping project IDs to the list of voters who approve them.
total_budget (int): The total budget available.
Returns:
list: A list of project IDs that are selected by the Method of Equal Shares.
Example:
>>> equal_shares(
>>> voters=["v1", "v2", "v3"],
>>> projects=["p1", "p2", "p3"],
>>> cost={"p1": 100, "p2": 50, "p3": 50},
>>> approvers={"p1": ["v1", "v2"], "p2": ["v1"], "p3": ["v3"]},
>>> total_budget=150)
["p1", "p3"]
"""
mes = equal_shares_fixed_budget(voters, projects, cost, approvers, total_budget)
# add1 completion
# start with integral per-voter budget
budget = int(total_budget / len(voters)) * len(voters)
current_cost = sum(cost[c] for c in mes)
while True:
# is current outcome exhaustive?
is_exhaustive = True
for extra in projects:
if extra not in mes and current_cost + cost[extra] <= total_budget:
is_exhaustive = False
break
# if so, stop
if is_exhaustive:
break
# would the next highest budget work?
next_budget = budget + len(voters)
next_mes = equal_shares_fixed_budget(voters, projects, cost, approvers, next_budget)
current_cost = sum(cost[c] for c in next_mes)
if current_cost <= total_budget:
# yes, so continue with that budget
budget = next_budget
mes = next_mes
else:
# no, so stop
break
return mes
def break_ties(voters, projects, cost, approvers, choices):
remaining = choices.copy()
best_cost = min(cost[c] for c in remaining)
remaining = [c for c in remaining if cost[c] == best_cost]
best_count = max(len(approvers[c]) for c in remaining)
remaining = [c for c in remaining if len(approvers[c]) == best_count]
return remaining
def equal_shares_fixed_budget(voters, projects, cost, approvers, total_budget):
budget = {i: total_budget / len(voters) for i in voters}
remaining = {} # remaining candidate -> previous effective vote count
for c in projects:
if cost[c] > 0 and len(approvers[c]) > 0:
remaining[c] = len(approvers[c])
winners = []
while True:
best = []
best_eff_vote_count = 0
# go through remaining candidates in order of decreasing previous effective vote count
remaining_sorted = sorted(remaining, key=lambda c: remaining[c], reverse=True)
for c in remaining_sorted:
previous_eff_vote_count = remaining[c]
if previous_eff_vote_count < best_eff_vote_count:
# c cannot be better than the best so far
break
money_behind_now = sum(budget[i] for i in approvers[c])
if money_behind_now < cost[c]:
# c is not affordable
del remaining[c]
continue
# calculate the effective vote count of c
approvers[c].sort(key=lambda i: budget[i])
paid_so_far = 0
denominator = len(approvers[c])
for i in approvers[c]:
# compute payment if remaining approvers pay equally
max_payment = (cost[c] - paid_so_far) / denominator
eff_vote_count = cost[c] / max_payment
if max_payment > budget[i]:
# i cannot afford the payment, so pays entire remaining budget
paid_so_far += budget[i]
denominator -= 1
else:
# i (and all later approvers) can afford the payment; stop here
remaining[c] = eff_vote_count
if eff_vote_count > best_eff_vote_count:
best_eff_vote_count = eff_vote_count
best = [c]
elif eff_vote_count == best_eff_vote_count:
best.append(c)
break
if not best:
# no remaining candidates are affordable
break
best = break_ties(voters, projects, cost, approvers, best)
if len(best) > 1:
raise Exception(f"Tie-breaking failed: tie between projects {best} could not be resolved. Another tie-breaking needs to be added.")
best = best[0]
winners.append(best)
del remaining[best]
# charge the approvers of best
best_max_payment = cost[best] / best_eff_vote_count
for i in approvers[best]:
if budget[i] > best_max_payment:
budget[i] -= best_max_payment
else:
budget[i] = 0
return winners
General considerations
Algorithmic trick to speed up the computation
During the computation, the algorithm needs to repeatedly compute the "effective vote count" of each project, which is an expensive step. This part can be sped up by only recalculating the effective vote count if it matters.
The main observation is that the effective vote count can only decrease as the algorithm proceeds. What we do in the implementation is the following: we start with the project which had the highest effective vote count in the previous round. We re-calculate the effective vote count of this project. Then we compare its new effective vote count with the effective vote count of the project with the second-highest effective vote count in the previous round. If the new effective vote count is higher than the effective vote count of the second-highest project, then we know that we have found the project with the highest effective vote count in the current round (because all the other projects previously had a lower effective vote count, which in the mean time could only have decreased even further). Thus, we can immediately select it.
This optimization is used in all the code snippets on this page.
Numerical accuracy: using floats or fractions?
When computing the winners of an election that uses the Method of Equal Shares, we need to perform some calculations that involve fractions. For example, we need to divide the cost of a project by the number of its supporters to find out how much each supporter should contribute to the project. Computers typically represent numbers using "floating-point numbers", which are not exact representations of real numbers (for example, 1/3 cannot be represented exactly as a floating-point number because it has an infinite decimal expansion). This means that if we use floating-point numbers, we may get inexact results in some (rare) cases. In particular, when there is a tie (i.e. two projects have the same effective vote count), the floating-point implementation may assign a slightly different effective vote count to each project, and thus may select a different winner than the exact implementation.
To avoid this problem, we can use a rational number implementation, which represents numbers as fractions of integers.
Such implementations are typically slower (by about 4-10x) than floating-point implementations, but they are exact.
The code generator above allows you to choose between a floating-point implementation and a rational number implementation.
We recommend using the rational number implementation if you are computing official results, and using the floating-point implementation if you are just doing a quick test.
The pabutools
package uses the rational number implementation by default.
Comparison to academic literature
In the academic literature, the Method of Equal Shares is often mathematically defined in such a way that it tends to select projects in order of decreasing cost-effectiveness (i.e. vote count divided by cost). In contrast, the method as described on this website tends to select projects in order of decreasing vote count. In the formal literature, this version of the method is sometimes referred to as using "cost utilities", because the version we are discussing here can be seen as using the cost of a project as a proxy for its utility for voters who approve it. It is important to keep this distinction in mind when comparing descriptions and pseudocode that are available in the academic literature.