Home

Awesome

<p align="center"> <img src="animated_favicon.svg" alt="animated_favicon" width="150px"> </p>

Approportionment for proportional representation

WebUI playground and sandbox (Everything runs on your computer, nothing on the server)

Yee diagrams for multi-winner electoral methods designed for proportional representation.

Electoral methods:

You may want to read Nicky Case's To Build a Better Ballot first.

equilateral

equilateral

The x and y coordinates is a spatial representation of voters and parties. The coloured circles are the parties. The diamond is the party whose seats are colored.

Every coordinate is the voter mean. A normal distribution is generated around that mean coordinate. Every voter casts a ballot and the ballots are counted. The color of a coordinate is the number of seats won by the diamond party.

In general, the closer the coordinate is to the diamond party, more voters like that party, so it would win more seats. The further away, the less seats it would win, but it is rarely 0 seats unless if the distance is large enough, because proportional representation awards seats to less popular parties as well.

colinear1

colinear1

two_close_right

two_close_right

two_close

two_close

colinear2

colinear2

square

square

tick

tick

on_triangle

on_triangle

middle_four

middle_four

stv 8 candidates stdev 1.0

stv-8-1.0-normal

stv 8 candidates stdev 1.0 with min party discipline

stv-8-1.0-min

stv 8 candidates stdev 1.0 with avg party discipline

stv-8-1.0-avg

stv 8 candidates stdev 0.5

stv-8-0.5-normal

stv 8 candidates stdev 0.5 with min party discipline

stv-8-0.5-min

stv 8 candidates stdev 0.5 with avg party discipline

stv-8-0.5-avg

stv 13 candidates stdev 1.0

stv-13-1.0-normal

stv 13 candidates stdev 1.0 with min party discipline

stv-13-1.0-min

stv 13 candidates stdev 1.0 with avg party discipline

stv-13-1.0-avg

stv 13 candidates stdev 0.5

stv-13-0.5-normal

stv 13 candidates stdev 0.5 with min party discipline

stv-13-0.5-min

stv 13 candidates stdev 0.5 with avg party discipline

stv-13-0.5-avg

Election methods findings

Divisor methods dividing to 0

Divisor methods (eg D'Hondt, Sainte-Lague) can fail catastrophically if there is a very low number of voters, because it quickly divides the number of remaining votes to 0. When all or most parties have 0 votes, there is no meaningful way to find the party with the most votes to award a seat to.

The hare quota should remain a decimal

The Hare Quota is basically total_votes/total_seats. But do you leave it as a decimal or turn it into an integer?

Both are vulnerable to giving more seats than the total seats possible. It's best to leave the quota as a decimal.

Largest remainder methods might encounter more remaining seats than parties

See forum discussion here

Largest remainder methods works by first allocating seats based on the floor of a party's quota. The number of automatic seats given this way is usually less than the number of parties. It then gives an extra seat to parties with the largest remainder in their quota, until all seats have been filled.

However, it is possible to have a situation to allocate too few automatic seats. In this situation, giving every party 1 extra seat will still not reach the required seats to fill.

Toby Pereria's proposed solution is to give 1 extra seat for the party with the lowest seats_won - votes_won / quota until all seats have been filled.

Numerically large quotas like the Droop quota seems to be more vulnerable to this than the Hare quota.

Number of voters and the participation criterion

IRV and STV fails the participation criterion. This means increasing or decreasing the number of voters can unexpectedly cause different results, especially if the turnout change is concentrated to supporters of a particular party/candidate.

Performance findings

See performance-findings.md. Specific timings might be outdated but they should remain true in general

Limitations

There are other very important factors that the graphs do not emphasize enough or just ignores.

District magnitude

The district magnitude (total number of seats) must be large enough, otherwise they will not be proportional enough no matter what allocation method is used. There just aren't enough seats to represent everyone fairly. Fortunately you can adjust the district magnitude for these simulations, so do use it to inform your choice. Small district magnitudes effectively increases the natural threshold, which brings us to the next point.

Thresholds

This project does not simulate thresholds as they are usually nationwide, but the districts here are not necessarily nationwide. Thresholds obviously distort proportionality. Thresholds do not always prevent extremists from winning seats, in fact they might amplify their influence. See The threshold of political pain: How a tiny reform radicalized Israeli politics. In my opinion, the entire point of proportional representation is to give representation to "unpopular" parties, so using thresholds to prevent "unpopular" parties from winning seats is contradictory and undemocratic.

A threshold at 5% sounds reasonable, after all if a party wins just 5%, isn't it unpopular enough to not win any seats? But it doesn't work like that because multiple parties will fail to reach the threshold. Suddenly your mere 5% threshold turns to be twice as effective and deprived 16% of the population from representation. In the most extreme case in Turkey, a mere 10% threshold was five times as effective and deprived 47% of the population from representation, and the AKP nearly won a 66% supermajority with only 34.28% of the vote.

If you're going to have an explicit threshold, I would reverse this and guarantee that most of the population will be represented. For example, "aim to represent at least 95% of the popular vote", aiming to represent as much parties as possible to hit 95% of the vote. No matter if 1 party or 10 parties failed to enter parliament, at most 5% of the population would be unrepresented.

Levelling seats and nationwide proportionality

Finally, this project models a single constituency only and does not have levelling seats. This can be a single nationwide district like the Netherlands. This can also be a local constituency district (eg Dublin Central, Södermanlands län). All methods here are proportional only within their district. For local constituency districts, this means the results are only semi-proportional nationwide. For party list PR systems, levelling seats are often used to ensure the nationwide seats are proportional. None of the countries that use STV for the national legislature (Ireland, Australia, Malta) has nationwide compensatory seats. Proportional methods cannot be naively combined across districts.

This presents another problem for STV, because it is difficult to do nationwide compensatory seats. A nationwide STV district in parallel with local districts will not work because this is not compensatory. Either the STV used in local districts has to be modified to depend on nationwide rankings, or a party list system has to be used to provide levelling seats. The latter is problematic as it is no longer party agnostic and it is unclear how to give compensatory seats for independents. The former would add even more complexity to the already complex STV.

Weaknesses of PR in general

There are some problems with all PR systems (compared to majoritarian systems):

In my opinion, these are the two biggest problems with PR, and they also happen to neatly cancel out (a bit/somewhat/almost).

The second problem is more of a symptom of the plurality mindset that many people are still stuck with, despite having a PR system. If the plurality winner was not systematically and institutionally advantaged, the problem will be less serious.

STV district magnitudes

https://teddit.net/r/EndFPTP/comments/wmur9s/if_you_had_to_choose_would_you_pick_stv_or/ikl6sj9/#c

The STV system used in Northern Ireland and Ireland can actually have a centrist bias if the district magnitude is low enough and the extremist parties doesn't run enough candidates.

It is possible for extremist parties to win a large enough vote share that would entitle it more seats under a party list system. However, STV cannot allocate more seats if the party did not run enough, so surplus transfers could flow to a more moderate candidate. The opposite happened in Belfast West though, so it's not a guarantee.

Performance

Allocation methods only

See ./benches/README.md

Whole program

Non-STV (D'Hondt, Sainte-Lague, Hare, and Droop combined)

Number of votersTime (s)Total votesVotes per second
1001.516,000,00010,666,666
1,0002.2160,000,00072,727,272
10,000101,600,000,000160,000,000

STV

Number of votersNumber of candidatesTime (s)Total votesTotal marksVotes per secondMarks per second
10072.74,000,00028,000,0001,481,48110,370,370
100123.24,000,00048,000,0001,250,00015,000,000
1,00079.540,000,000280,000,0004,210,52629,473,684
1,0001214.840,000,000480,000,0002,702,70332,432,432
10,000778400,000,0002,800,000,0005,128,20535,897,436
10,00012127400,000,0004,800,000,0003,149,60637,795,276

Q&A

What about mixed compensatory systems?

Mixed compensatory systems include MMP (New Zealand) and AMS (Scotland). It does not include non-compensatory systems like parallel voting (Japan) or mixed-member majoritarian (Italy).

Fundamentally, these simulations are for one electoral district. This can be one subnational district or one nationwide district. Mixed proportional systems has two types of seats, constituency and list seats. The two seats may follow different district boundaries, so these simulations cannot take arbitrarily different districts without doubling in scope.

Subject to the constitutional court's ruling, Germany is changing its MMP system into a form of semi-open, district local party list PR, approportioned nationwide. The Bundestag will be fixed in size and there will be a constituency and list vote on the ballot. Parties are first allocated seats based on their list vote. Constituency candidates are elected to fill their party's allocated seats, prioritising candidates with larger pluralities first. Constituency candidates who won a plurality might not be elected if their party did not win enough list votes. This prevents overhang seats, and therefore removes the need for levelling seats (which compensates for overhang seats). Notably, the nationwide 5% threshold applies to the party list vote, so any party that miss the threshold will win 0 seats, even if they have a plurality in constituencies. The current 3-seat buffer to qualify for PR will be abolished.

Effectively this becomes a semi-open list system (voters may influence the ranking of candidates within their constituency, but not in other constituencies), a district local list (each constituency has a unique list of candidates), approportioned nationwide (district local lists are approportioned nationwide, not per district).

This project will be able to model Germany's new system, as approportionment by parties are solely determined by the nationwide vote share (ignoring the threshold). It will not model the exact MPs elected from the constituency vote, but this is fine as the focus is not on individual MPs but approportionment of seats between parties.

Why not use binary formats instead of JSON for the webui's import/export?

JSON is faster than the pure Javascript msgpack and cbor library. V8 is amazing! The large file size is indeed a limitation, but those binary formats couldn't significantly decrease the file size either.

Protobuf doesn't have official support for Javascript/Typescript. Flatbuffers requires compiling a C++ program, dragging in an entire language toolchain.

Usage

WebUI

Go to https://akazukin5151.github.io/approportionment/ if you just want to use it. Alternatively you can run the WebUI entirely offline, as the website is entirely offline. Follow the instructions below for this, or for development.

Requirements

Build

wasm-pack build --target web -- --features wasm
cd webui
npm ci
npm run dev  # or npm run build

# Launch an http server (or use your preferred method)
cd dist
python -m http.server 8000
# Open http://0.0.0.0:8000/ in your browser (faster on chromium)

Binary program

The binary program is not entirely offline because it uses Dhall to pass settings, and uses the Dhall standard library, which is imported from its online repository.

  1. Install requirements for plotting pip install -r python/requirements.txt
  2. Edit config/config.dhall as you please. The schema is in config/lib/schema.dhall.
  3. Statically type-check and validate the config with dhall resolve --file config/config.dhall | dhall normalize --explain
  4. Compile with optimizations with cargo build --release
  5. target/release/approportionment config/config.dhall
  6. python python/main.py

Both the rust and python programs are lazy - if their output file exists they will not do anything, no matter if the output file is valid or not. For a clean run, remove all output directories (default: out)

You can run an STV example using the config/stv.dhall config and python/stv.py script to plot.

Compilation features

By default, cargo build will enable the binary feature only.

Ties are currently broken by selecting the first party/candidate. For a proper tiebreak implementation (random choice for non-STV and looking at previous rounds for STV), see the tiebreak branch. Alternatively, to just get data on how many ties there are, see the report-ties branch. They weren't merged because I think it's not worth the extra code and performance, and also difficult to add as a cargo feature.

Speeding it up

[0] This might be outdated now

Development

Run tests with

cargo test --features wasm

There are also tests that runs the STV algorithm with real world election data, which needs to be downloaded first.

cd rust/stv/tests/real/data/
wget $(cat urls.txt)
unzip 'CHttpHandler.ashx*'
cd ../../../../..  # repo root
cargo test real --features test_real_stv

Benchmarks uses the current date and hour as a seed for deterministic, comparable runs. There will be a new seed every day at midnight. Alternatively, it also reads the SEED environment variable. Run the benchmarks with:

cargo bench

Use hyperfine to compare two versions with something like

# Just compiling two versions and renaming the binaries
# Git branches are examples
git checkout old
cargo b --release
mv target/release/approportionment/ target/release/approportionment-old

git checkout new
cargo b --release
mv target/release/approportionment/ target/release/approportionment-new

# optionally set a fixed seed for deterministic data
# (the binary does not use a seed based on the day of the year)
# export SEED='1234'

hyperfine --prepare 'rm -rf out' 'target/release/approportionment-{name} config/benchmark.dhall' -L name new,old

Correctedness

Accuracy

The STV algorithm is tested by a combination of unit tests, property based tests, regression tests. It is also compared to the Glasgow Council elections, passing tests for 22 out of 23 wards. The single ward that did not pass was because Australian STV truncate values early, while Scottish STV keeps 5 decimal places.

Min and max bounds

Run cargo clippy -- -W clippy::integer_arithmetic to see all warnings. Not all of them are relevant but some do point out numerical limitations:

Prior art

Multi winner methods

Single winner methods

Too many to list, but here's one of mine: https://github.com/akazukin5151/electoral-systems

See also

Ballot counting libraries

The ballot counting functions here are specifically optimized for the single purpose of simulating many anonymous elections. While it is fast, it is not ergonomic for counting an election, and does not support common output files (like .blt). Consider these instead:

TODO

WebUI

Features

STV rules

You think STV is simple? I wish...

This is my best effort interpretation of the legal text. I don't have a lawyer so my interpretation can be wrong. I used legal text instead of academic papers because I wanted to have a faithful implementation according to a real-world system. STV is actually a system of different methods and all of them are different.

Which ballots to transfer?

Australian Federal Senate

All ballots are transferred, just at a fractional value. The transfer value remains as a decimal number, though when it is multiple to the ballots, the result is truncated (Part XVIII section 273 number 9b)

Ireland Dáil

How to transfer a count made up of first preferences and preferences that were transferred?

Consider the food election example from wikipedia.

Australian Federal Senate

All 7 votes for #1 is transferred to #2. It is multiplied by the transfer value of 1/7, making it 1, so the total votes for #2 is now 1 + 1 = 2.

Then #2 is eliminated. The single original vote for #2, and all 7 votes that were transferred from #1, is transferred again to #3. Is this 8 full votes being transferred to #3? Or 1 full vote to #3 and 7 partial votes to #3?

First, let us clarify two types of transfers: surplus transfers and elimination transfers. The former is due to surplus votes from an elected candidate; the latter is due to votes to an eliminated candidate. My interpretation is:

But elimination transfers have different rules:

Section 13AA(a) says that the transfer value is 1 full vote for both actual first preference and transferred first preferences. This implies 8 full votes for the above example.

However, 13AA(b)(ii) implies that for transferring eliminated candidates, if it has received transfers previously, then those votes must be multiplied by their transfer value first, before being transferred away. This is indeed what wikipedia describes here as "compounded fractional value"

So for surplus transfers, the transfer value only depends on the candidate being transferred out of. For elimination transfers, the transfer value for the current candidate is 1, but the overall transfer value is a compounded one, meaning it is the product of all previous transfer values that were applied to the ballot.

Going back to the example scenario, this is 1 full vote to #3 and 7 partial votes to #3. The transfer value for those 7 votes is the product of all previous and current transfer values: 1/7 * 1. The transfer value for the single vote is 1. So #3 ultimately gets 1 + 1/7*7 = 2 new votes, and the new count is 4 + 2 = 6 votes. #3 is elected without a surplus and the problem ends here.

But what if there was a surplus? My interpretation is that only section 13 talks about multiplying previous transfer values before transferring, and section 13 is only for elimination transfers. So surplus transfers does not use compounded fractional votes. If #3 had a surplus, all votes for #3 would be transferred using #3's transfer value. Which can be larger than the surplus if there were enough votes that was previously transferred (which was weighted to be below the previous surplus), and no longer weighted when it is transferred out again.

This is consistent with Wikipedia's description of the Australian STV rules as unweighed inclusive Gregory - it is not not weighted for surplus transfers.

The full quote from section 9 says the transfer value is (emphasis mine):

the number of surplus votes of the elected candidate shall be divided by the number of first preference votes received by the candidate and the resulting fraction shall be the transfer value

Comparing to Scottish councils, section 48.3 says the transfer value is (emphasis mine):

the value which is calculated by multiplying the surplus of the transferring candidate by the value of the ballot paper when received by that candidate [divided by] the total number of votes credited to that candidate

Australia just uses the surplus, while Scotland weights the surplus by the compounded transfer value first.

Western Australia's upper house weights the surplus as well. Schedule 1 says that the first quota transfer work as usual, but there are different rules if a ballot is further transferred. Section 5 says (emphasis mine):

(a) the number of surplus votes of the elected candidate shall be divided by the number of votes received by him and the resulting fraction shall be the surplus fraction; (b) in relation to any particular ballot papers for surplus votes of the elected candidate, the surplus fraction shall be multiplied by the transfer value at which those ballot papers were transferred to the elected candidate, or by one if they expressed first preference votes for the elected candidate, and the product shall be the continued transfer value of those particular ballot papers;

The "continued transfer value" is just the compounded transfer value.

If multiple candidates reach quota, which surplus to transfer first?

Australian Federal Senate

Part XVIII section 273 subsection (21) says transfer the largest surplus first

How many candidates should a party run in STV?

Current STV implementation bypasses this by forcing you to specify each individual candidate. In practice, it will be very tedious, hopefully teaching you how important this problem is. The plots will only show how successful a single candidate is, not the party they represent. In the WebUI, the solution is to group candidates in a coalitions. For party-list methods, this would be useful to analyze whether a governing coalition has a majority. For STV, this would be essential to analyzing how many seats a party has overall.

Currently the coalition feature works for the WebUI. For local plotting with python, the coalition feature is only available for STV

Further extensions

Panachage

Panachage is when voters can vote for multiple candidates, across party lists if possible. The exact number of votes depends, but a common one is the value of the district magnitude. The votes are tallied according to normal PR list rules and candidates are elected according to the number of votes they won. Due to panachage there will be more votes than voters.