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

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(N, C, cost, approvers, B):`

mes = equal_shares_fixed_budget(N, C, cost, approvers, B)

# add1 completion

# start with integral per-voter budget

budget = int(B / len(N)) * len(N)

current_cost = sum(cost[c] for c in mes)

while True:

# is current outcome exhaustive?

is_exhaustive = True

for extra in C:

if extra not in mes and current_cost + cost[extra] <= B:

is_exhaustive = False

break

# if so, stop

if is_exhaustive:

break

# would the next highest budget work?

next_budget = budget + len(N)

next_mes = equal_shares_fixed_budget(N, C, cost, approvers, next_budget)

current_cost = sum(cost[c] for c in next_mes)

if current_cost <= B:

# yes, so continue with that budget

budget = next_budget

mes = next_mes

else:

# no, so stop

break

return mes

def break_ties(N, C, 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(N, C, cost, approvers, B):

budget = {i: B / len(N) for i in N}

remaining = {} # remaining candidate -> previous effective vote count

for c in C:

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(N, C, cost, approvers, best)

if len(best) > 1:

raise Exception("Tie-breaking failed: tie between projects " + ", ".join(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.