Proportional runoff (old version!)

This is an old version of the "Proportional runoff" algorithm. Please check out the new version

On this page, I want to present an idea for a simple vote counting system producing proportional rankings. It is also possible to use the system as a replacement for STV (single transferrable vote), by using the first ranks up to the number of seats.

Design criteria

deterministic, except for tie-breaking (no random drawing of ballots)
easy to understand (only basic knowledge of mathematics is needed)
invulnerability to Woodall Free Riding (it doesn't help to rank a hopeless candidate first)
creation of an ordered list with ranks, allowing to fill vacancies later
droop proportionality: a candidate voted by more voters than the droop-quota (voters/(N+1)), reaches at least rank N

Definition

Each ballot contains an ordered list of candidates. Let P be a big integer constant, e.g. 1000000. Proceed as follows:

All candidates are marked as non-eliminated.
The smallest quota Q is determined, for which the ballot distribution (see below) on all non-eliminated candidates creates a loser L.
The loser L is marked as eliminated and is assigned the next rank, starting from the worst rank.
Steps 2 and 3 are repeated until all candidates are eliminated.

Ballot distribution with quota Q:

Every non-eliminated candidate is assigned a vote count of zero.
The vote count of all non-eliminated candidates is memorized.
For each ballot: Determine the first non-eliminated candidate on the ballot, which had a lower count than Q in step 2, and increase this candidates vote count by one, if existent.
Steps 2 and 3 are repeated P times.
If one non-eliminated candidate has a lower vote count than Q, then this is the loser. If more than one non-eliminated candidate has a lower vote count than Q, then one of the candidates with lower vote count is randomly chosen to be the loser. If all candidates have a vote count of at least Q, then there is no loser.

Implementation notes

The smallest quota Q, which creates a loser, can be found by binary search. The ballot distribution can done more efficiently by increasing the vote count for the corresponding candidates by more than 1 per ballot in each step: The smallest possible number, which causes at least one new candidate to reach a vote count of Q can be used instead of 1, if the number of remaining repetitions is reduced respectively.

Proportionality

If there are N+1 or more non-eliminated candidates left in the process, then a candidate getting more than 1/(N+1) of all votes can't be eliminated. Thus his/her rank will be N or better.

Free Riding

The method is invulnerable to Woodall Free Riding, as the count is restarted after a candidate gets eliminated. However it is NOT invulnerable to Hylland Free Riding and Vote Management. There are other systems, which are much better in this regard, i.e. the more complicated Schulze STV method can prevent Hylland Free Riding and Vote Management, except in those cases where the droop proportionality would have been violated otherwise.

Software implementation

proportional_runoff.v0.0.2.lua (supports tie-breaking using extra file)
proportional_runoff.v0.0.1.lua

Example case

Candidates:
- A
- B
- C

Voters:
- Ballot #1: A;B
- Ballot #2: A;B
- Ballot #3: B;A
- Ballot #4: B;A
- Ballot #5: C;B
- Ballot #6: C;B
- Ballot #7: C;B

Log of counting:

Non-eliminated candidates: A; B; C
Initial ballot weight: 1000000
Quota: 2222222
Used ballot weight: 740741
Remaining ballot weight: 1000000 - 740741 = 259259
Votes for candidate A: 0 + 2 * 740741 = 1481482
Votes for candidate B: 0 + 2 * 740741 = 1481482
Votes for candidate C: 0 + 3 * 740741 = 2222223 (passed)
Used ballot weight: 148148
Remaining ballot weight: 259259 - 148148 = 111111
Votes for candidate A: 1481482 + 2 * 148148 = 1777778
Votes for candidate B: 1481482 + 5 * 148148 = 2222222 (passed)
Votes for candidate C: 2222223 (passed)
Used ballot weight: 111111
Remaining ballot weight: 111111 - 111111 = 0
Votes for candidate A: 1777778 + 4 * 111111 = 2222222 (passed)
Votes for candidate B: 2222222 (passed)
Votes for candidate C: 2222223 (passed)
All candidates have passed.
Ballot weight exhausted.
No loser.
Non-eliminated candidates: A; B; C
Initial ballot weight: 1000000
Quota: 2222223
Used ballot weight: 740741
Remaining ballot weight: 1000000 - 740741 = 259259
Votes for candidate A: 0 + 2 * 740741 = 1481482
Votes for candidate B: 0 + 2 * 740741 = 1481482
Votes for candidate C: 0 + 3 * 740741 = 2222223 (passed)
Used ballot weight: 148149
Remaining ballot weight: 259259 - 148149 = 111110
Votes for candidate A: 1481482 + 2 * 148149 = 1777780
Votes for candidate B: 1481482 + 5 * 148149 = 2222227 (passed)
Votes for candidate C: 2222223 (passed)
Used ballot weight: 111110
Remaining ballot weight: 111110 - 111110 = 0
Votes for candidate A: 1777780 + 4 * 111110 = 2222220
Votes for candidate B: 2222227 (passed)
Votes for candidate C: 2222223 (passed)
Ballot weight exhausted.
Eliminating loser: A
Non-eliminated candidates: B; C
Initial ballot weight: 1000000
Quota: 3000000
Used ballot weight: 750000
Remaining ballot weight: 1000000 - 750000 = 250000
Votes for candidate B: 0 + 4 * 750000 = 3000000 (passed)
Votes for candidate C: 0 + 3 * 750000 = 2250000
Used ballot weight: 250000
Remaining ballot weight: 250000 - 250000 = 0
Votes for candidate B: 3000000 (passed)
Votes for candidate C: 2250000 + 3 * 250000 = 3000000 (passed)
All candidates have passed.
Ballot weight exhausted.
No loser.
Non-eliminated candidates: B; C
Initial ballot weight: 1000000
Quota: 3000001
Used ballot weight: 750001
Remaining ballot weight: 1000000 - 750001 = 249999
Votes for candidate B: 0 + 4 * 750001 = 3000004 (passed)
Votes for candidate C: 0 + 3 * 750001 = 2250003
Used ballot weight: 249999
Remaining ballot weight: 249999 - 249999 = 0
Votes for candidate B: 3000004 (passed)
Votes for candidate C: 2250003 + 3 * 249999 = 3000000
Ballot weight exhausted.
Eliminating loser: C
Non-eliminated candidates: B
Initial ballot weight: 1000000
Quota: 7000000
Used ballot weight: 1000000
Remaining ballot weight: 1000000 - 1000000 = 0
Votes for candidate B: 0 + 7 * 1000000 = 7000000 (passed)
All candidates have passed.
Ballot weight exhausted.
No loser.
Non-eliminated candidates: B
Initial ballot weight: 1000000
Quota: 7000001
Used ballot weight: 1000000
Remaining ballot weight: 1000000 - 1000000 = 0
Votes for candidate B: 0 + 7 * 1000000 = 7000000
Ballot weight exhausted.
Eliminating loser: B

Ranking:
1. B
2. C
3. A

Feedback wanted

I'd appreciate feedback on this idea (see Kontakt).

(published 2011-11-08, last updated: 2011-12-11)

Back to main page

Kontakt