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:
- Highest averages methods
- Largest remainders methods
- Single Transferable Vote
- Australian Federal Senate rules (unweighted inclusive Gregory method)
- See STV rules
- Random ballots (randomly sampling ballots)
- Cardinal methods
- Thiele interpretation
- Sequential Proportional Approval voting
- Reweighted Range voting (proportional score voting)
- Monroe interpretation
- Vote unitarity interpretation
- Phragmen's interpretation
- Thiele interpretation
You may want to read Nicky Case's To Build a Better Ballot first.
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.
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 is basically total_votes/total_seats. But do you leave it as a decimal or turn it into an integer?
- Brazil rounds the fraction (article 106)
- Hong Kong floors the fraction (49(6))
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 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.
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.
See performance-findings.md. Specific timings might be outdated but they should remain true in general
There are other very important factors that the graphs do not emphasize enough or just ignores.
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.
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.
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.
There are some problems with all PR systems (compared to majoritarian systems):
- Small kingmaker parties can wield a lot of power to extract policy concessions from larger parties in return for confidence or coalition
- The usual convention is that the largest party gets the first attempt to form a government, giving the plurality winner an advantage in participating in the eventual government. This may encourage tactical voting towards larger parties, in hopes that one's preferred coalition is in a stronger position.
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.
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.
- Results for whole program benchmarks, not allocation method benchmarks
- Rough times I get on my computer (Intel i7-8550U) with 8 cores of multithreading (I didn't close all other programs)
- All except 10,000 voters 7 candidates are ran with the
intrinsicsfeature andtarget-cpu=native - Note that these times includes the time to read the Dhall config file, so performance seems to increase with more voters. This is because the time spent reading the config becomes negligible for longer running times.
- Most of the running time is used to randomly generate voters and count their ballots. The actual allocation methods are much faster than this, so this is actually mostly measuring how fast you can generate a random normal distribution, calculate distances, and write results to a file, but not how fast the allocation methods are.
| Number of voters | Time (s) | Total votes | Votes per second |
|---|---|---|---|
| 100 | 1.5 | 16,000,000 | 10,666,666 |
| 1,000 | 2.2 | 160,000,000 | 72,727,272 |
| 10,000 | 10 | 1,600,000,000 | 160,000,000 |
- The total votes are calculated by
4 * 200 * 200 * n_voters. There are 4 allocation methods, 200 rows, and 200 columns.4 * 200 * 200is the total number of elections ran, and every election hasn_votersnumber of votes
| Number of voters | Number of candidates | Time (s) | Total votes | Total marks | Votes per second | Marks per second |
|---|---|---|---|---|---|---|
| 100 | 7 | 2.7 | 4,000,000 | 28,000,000 | 1,481,481 | 10,370,370 |
| 100 | 12 | 3.2 | 4,000,000 | 48,000,000 | 1,250,000 | 15,000,000 |
| 1,000 | 7 | 9.5 | 40,000,000 | 280,000,000 | 4,210,526 | 29,473,684 |
| 1,000 | 12 | 14.8 | 40,000,000 | 480,000,000 | 2,702,703 | 32,432,432 |
| 10,000 | 7 | 78 | 400,000,000 | 2,800,000,000 | 5,128,205 | 35,897,436 |
| 10,000 | 12 | 127 | 400,000,000 | 4,800,000,000 | 3,149,606 | 37,795,276 |
- Total marks is the number of votes times the number of candidates
- All voters rank all candidates, so every vote has a mark for every candidate
- This metric is here as a reminder that STV potentially looks at a single vote multiple times, so the number of candidates are as important as the number of voters
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.
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.
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.
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)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.
- Install requirements for plotting
pip install -r python/requirements.txt - Edit
config/config.dhallas you please. The schema is inconfig/lib/schema.dhall. - Statically type-check and validate the config with
dhall resolve --file config/config.dhall | dhall normalize --explain - Compile with optimizations with
cargo build --release target/release/approportionment config/config.dhallpython 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.
By default, cargo build will enable the binary feature only.
binary: build the binary with dhall config and feather outputwasm: builds only the library functions needed for the WebUI- also enables
voters_sample
- also enables
wasm_debug: enables thedebugfunction for debugging the WebUI- also enables
wasm
- also enables
intrinsics: replace mathematical operators in distance calculation with compiler intrinsics, which speeds up the program. Nightly Rust only and intrinsics will never be stabilized.fma_non_stv: use fused mul add for non STV methods. Ignored ifintrinsicsis enabledfma_stv: use fused mul add for STV methods. Ignored ifintrinsicsis enabledprogress_bar: Enables indicatif to display a progress bar in the consolevoters_sample: Enables returning a sample of 100 voters for every election. Does nothing for binaries even if enabledtest_real_stv: enables unit tests that compare STV against real world elections. The blt files must be downloaded torust/stv/tests/real/data/.
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.
- If you're willing to use nightly rust, you can use intrinsics to speed up the program. Remove the
.samplefromrust-toolchain.toml.sample. Runcargo build --release --features intrinsics - You can also enable optimizations for your CPU. Prepend cargo with
RUSTFLAGS='-C target-cpu=native'. This can be combined with the intrinsics feature for even better performance.- But this was slower for me in STV for 10,000 voters and >7 parties
- Fused multiply add (fma) might speed up the program. Quick benchmarks for me showed that it was faster for non STV methods but slower for STV, which is why there are two separate feature toggles.
- Try using Profile-guided optimizations. There's no code to add so it's up to you to provide samples and recompile. I suggest
config/config.dhallandconfig/stv.dhallas they have a variety of methods and parties/candidates. I used 1000 voters for both configs, and saw a 35% speed up forconfig.dhalland a 5% speed up for STV [0]. Try using a more varied set of candidates for STV.
[0] This might be outdated now
Run tests with
cargo test --features wasmThere 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_stvBenchmarks 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 benchUse 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,oldThe 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.
Run cargo clippy -- -W clippy::integer_arithmetic to see all warnings. Not all of them are relevant but some do point out numerical limitations:
-
Max number of seats for all methods =
usize::MAX- Number of seats are stored in a
usize
- Number of seats are stored in a
-
Max number of voters for all methods =
isize::MAX- Ballots are stored in a vector and allocations in Rust/LLVM cannot exceed this number
-
Max number of parties for feather =
usize::MAX / (200 * 200)- The number of rows are limited by
usize::MAX, each party needs to duplicated for every200 * 200points
- The number of rows are limited by
-
Max number of parties =
isize::MAX- The number of seats for each party is stored in a vector and allocations in Rust/LLVM cannot exceed this number
-
All numbers are inclusive, meaning "less than or equal" is safe
-
The minimum for seats, voters, and parties are
0 -
usizeandisizedepends on if you are compiling for a 32-bit or 64-bit machine. See the documentation (usize, isize) -
usize::MAXis2^64 − 1for 64-bit -
isize::MAXis2^63 − 1for 64-bit
- https://github.com/ParkerFriedland/TernaryPlot
- https://web.archive.org/web/20211128200121/https://forum.electionscience.org/t/apportionment-algorithems-visualized/569
- https://bolson.org/voting/sim_one_seat/20090810/4b.html
Too many to list, but here's one of mine: https://github.com/akazukin5151/electoral-systems
- Both single and multi winner, with better mathematical evaluation tools: https://github.com/simberaj/votelib
- https://www.howtofixtheelection.com/ballot/proportional/
- Proportional representation visualizations, for candidate based methods. Has more detail for strategy and impacts on the individual voters. (This project focuses more on proportionality by parties, not the impact on individual voters)
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:
-
Catch exceptions from event handlers (top-level try-catch only catches exceptions throw in initial setup code, not event handlers)
-
display a spinner on page load, and remove when it has finished loading
-
The voter sample and stv party discipline probability does not use the seed
-
STAR-PR
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.
-
https://en.wikipedia.org/wiki/Single_transferable_vote#Transfers_of_surplus_votes
-
https://en.wikipedia.org/wiki/Counting_single_transferable_votes
-
- Ceiling the largest remainders necessary to reach the surplus, and floor the rest (121.6c)
-
Scotland, councils (simple english)
- Like Australia, but has fractional transfers up to 5 decimal places
- Re-transfers from an eliminated candidate uses their original transfer value. (If a vote was transferred to a candidate, it becomes a fractional vote, and that candidate is eliminated, then the fractional vote is transferred as the fraction)
-
Malta, page 117
- All ballots examined, reduce the value, round down, and transfer. If rounding down causes less transfers than needed, round the highest decimals up until the entire surplus is transferred.
- Decimals in the share of surplus are rounded to favour the larger party
- If there are multiple surpluses, transfer the one that appeared first in the counts. Eg candidate A has a surplus, candidate B gains a bigger surplus in another count, candidate A's surplus should still be transferred first.
- Transfer of surpluses only considers the batch of votes that was transferred the soonest. Eg A's count is made up of first and second preferences. A's surplus is transferred from the second preferences first. If after such transferral there is still a surplus, the remaining surplus are exhausted.
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)
- Surplus to distribute is from the last parcel of votes that bought the candidate over the quota.
- Except, if all of those votes were first preference votes for that candidate (in other words, none of the votes were previously transferred; this is always true in the second count), then all votes will be examined
Consider the food election example from wikipedia.
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:
- Section 9 governs surplus transfers, and the transfer value in such cases is always for the current candidate. It won't look at the transfer values of previous transfers
- Section 12 says treat transferred votes as if it was a first preference. This again implies transfer values of previous transfers is disregarded, after all there can't be previous transfers if we pretend the current tally are of first preference votes.
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.
Part XVIII section 273 subsection (21) says transfer the largest surplus first
- Ireland (pdf): Fianna Fáil and Fine Gael usually runs half the district magnitude (2-3), but sometimes either runs 1 in less popular districts. Sinn Féin usually runs 1, and 2 for popular districts. Other parties usually run just one candidate. Note that Sinn Féin ran too few candidates in the 2020 election; they would have won more seats if they ran more.
- Australia: The ballot allows voters to rank candidates as usual, but also to vote for a pre-determined rank endorsed by a party. Nevertheless, Australia has a two-party system as the lower house does not have proportional representation, so the two main parties runs all or nearly all of the district's available seats, while other parties run only a handful of candidates.
- Malta has a two-party system despite having STV, because the district magnitudes are too small, resulting in a ridiculously high effective electoral threshold that only the two main parties can cross. Anyway, the two main parties fill the ballots with way more candidates than in the entire house.
- Scotland: SNP usually runs 2 seats and the rest runs 1. Sometimes Labour runs 2, eg in Glasgow and Fife. See also Aberdeen, Highlands (SNP running 1 candidate in some wards in Highlands)
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
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.