[EM] Biproportional representation (was Re: Preferential voting system where a candidate may win multiple seats)
Vidar Wahlberg
canidae at exent.net
Sun Jul 28 07:37:51 PDT 2013
On Tue, Jul 23, 2013 at 09:29:25PM +0200, Vidar Wahlberg wrote:
> Implementing it is no easy task. It may be that my sources, mainly the
> Wikipedia entry and Olli Salmi's page[2] are a bit short on the topic,
> but one hindrance I've faced is figuring out what the divisor values
> should be during the correction stages. Neither sources elaborate well
> on how they decided the divisor values, and Salmi writes "I have just
> fiddled with the divisor until the total number of seats assigned is
> correct", but that's no good when implementing the algorithm.
An update on this. This mail will be very long, sorry about that.
I gave up on using the article on Wikipedia and Salmi's page, instead I
came across a PDF where the method was explained well, although using
multiplicators rather than divisors. Arguably this only makes the method
easier to explain and produce the same result, so it probably is a
better solution.
The PDF I've used for reference can be found here:
http://www.math.uni-augsburg.de/stochastik/pukelsheim/2008f.pdf
Here's a shot at explaining my implementation (as of this writing I've
not yet implemented preferential election, which I intend to do later).
The code (rough, only intended as "proof of concept") can be found here:
https://github.com/canidae/voting/blob/master/pbpa.d
Upper apportionment:
- Party seats are apportioned using unmodified Sainte-Laguë based on
national votes. If desirable the first divisor may be modified, or a
election threshold may be set to prevent fragmentation, but I've not
done this.
- District seats are determined externally and thus not apportioned in
this implementation.
Lower apportionment:
1. Assign initial seats
Assign initial seats for each party in each district. This is
calculated as:
seats[district][party] = nationalSeats * votes[district][party] / nationalVotes
This will give an incorrect amount of seats, some parties/districts will
receive too few seats, others will receive too many, but this is
corrected in later stages.
2. Calculate party multiplicator for all parties
Find the minimum and maximum multiplicator for each party that we need
to apply in all districts to make each party receive the correct amount
of seats. After this is done for then all parties will have the correct
amount of seats, but each district may not have the correct amount of
seats.
If however both parties and district got the right amount of seats, then
we're done. If not, continue to step 3.
3. Calculate district multiplicator for all districts
Find the minimum and maximum multiplicator for each district that we
need to apply to all parties to make each district receive the correct
amount of seats. After this is done for then all districts will have the
correct amount of seats, but each party may not have the correct amount
of seats.
If however both parties and district got the right amount of seats, then
we're done. If not, go to step 2.
This sounds fairly simple, and sort of, it is, but there are several
pitfalls when implementing this as a computer program.
The biggest problem I encountered was finding the minimum and maximum
multiplicators for each party/district in step 2/3. This was generally
not well explained in any of the sources I used, in addition you'll have
to battle rounding errors of floating numbers. I did eventually find a
decent solution:
Assume 3 parties and 3 districts, we'll only focus on 1 party (Party A).
This is the matrix after the calculation explained in step 1 above:
| Party A | Party B | Party C
-----------+---------+---------+---------
District 1 | 1.3 | 2.2 | 0.3
District 2 | 0.3 | 1.7 | 0.4
District 3 | 0.7 | 0.3 | 0.9
Party A was in the upper apportionment assigned 4 seats, but from the
table above they've only received 2 seats so far (1 in D1, 1 in D3). So
we'll have to find the "borders" where a party received a seat in a
district. These borders are at 0.5, 1.5, 2.5, and so on, we'll need to
find the multiplicators that will place the values in the matrix at
these borders. The multiplicator we need to make 1.3 (D1,PA) become 0.5
is "0.5/1.3 = 0.384615", or to show the full table:
0.5/1.3 = 0.38462 | total seats: 1
1.5/1.3 = 1.15385 | total seats: 3
2.5/1.3 = 1.92308 | total seats: 5
3.5/1.3 = 2.69231 | total seats: 7
0.5/0.3 = 1.66667 | total seats: 4
1.5/0.3 = 5.00000 | total seats: 13
0.5/0.7 = 0.71429 | total seats: 2
1.5/0.7 = 2.14286 | total seats: 6
"total seats" above is calculated by multiplying the result with all the
values in the matrix for the party (1.3, 0.3, 0.7) and rounding to the
nearest integer. Example:
0.38462 * 1.3 = 0.500000 -> 1
0.38462 * 0.3 = 0.115386 -> 0
0.38462 * 0.7 = 0.269234 -> 0
For each district you begin at 0.5 then increase that with 1 until the
total amount of seats assigned minus 1 exceeds the amount of seats the
party should receive. Minus 1 because the maximum multiplier will give
one seat too many, we want the number a tiny fraction below the maximum
numbers, but more on this later.
After this we sort the multiplicators we found, smallest number first:
0.38462 (index 1)
0.71429 (index 2)
1.15385 (index 3)
1.66667 (index 4) <-- this is our minimum multiplier
1.92308 (index 5) <-- this is our maximum multiplier
2.14286 (index 6)
2.69231 (index 7)
5.00000 (index 8)
When we do this, the minimum multiplier will always be at the index
corresponding to the amount of seats the party should receive, and the
maximum multiplier will be on the next index.
The reason I did it like this is because of rounding errors. The minimum
multiplier may give you 3 seats instead of 4, and the maximum multiplier
we actually expect to be 5, but rounding errors may make it 4. I did not
want to increase/decrease these multipliers with a very small value
because that would be error prone, but that means I still have to handle
multipliers that may be a fraction off the optimal value.
The PDF I used as reference says you should use the maximum multiplier
when you're to increase the number of seats, and the minimum multiplier
when you're to decrease the number of seats. I'm not entirely sure why
this is recommended, if someone have insight on this then please share.
Salmi on the other hand mentions using the average of these two
multipliers (or divisors in his case), and this also more or less solves
the problem with multipliers being a fraction of the optimal value, so
for now I'm using the average of the minimum and maximum multipliers.
In this code I've not weighted up votes from districts which in the
current system are weighted up, and I've kept the amount of seats in
each district. This means that there's a theoretical possibility (as
I've discussed earlier) that you can end up with an unresolvable
election, but it should be noted that this possibility is very low.
If there are too many parties/districts and/or there are very small
differences in votes for parties then you may also have a problem with
too low accuracy of floating numbers. This can be solved by using
floating numbers with higher precision if it should become a problem.
That said, this looks like a very solid system for an optimal
biproportional apportionment. Since there are multiplicators for each
party and each district it will also be more resistant to two parties
receiving the exact same amount of votes in the same district.
That each vote is worth equally much regardless of which district the
vote was given is also an appealing thought.
----
So here's the result using data from the Norwegian 2009 election. No
election threshold cause 3 new parties to enter the parliament:
Upper apportionment:
Parties (2009 result in parentheses):
Rødt : 2 ( 0)
Sosialistisk Venstreparti: 11 (11)
Arbeiderpartiet : 60 (64)
Senterpartiet : 10 (11)
Kristelig Folkeparti : 9 (10)
Venstre : 7 ( 2)
Høyre : 29 (30)
Fremskrittspartiet : 39 (41)
Miljøpartiet de Grønne : 1 ( 0)
Kystpartiet : 0 ( 0)
Pensjonistpartiet : 1 ( 0)
Districts (pre-determined):
Akershus : 16
Aust-Agder : 4
Buskerud : 9
Finnmark : 5
Hedmark : 8
Hordaland : 15
More og Romsdal : 9
Nordland : 10
Nord-Trondelag : 6
Oppland : 7
Oslo : 17
Rogaland : 13
Sogn og Fjordane: 5
Sor-Trondelag : 10
Telemark : 6
Troms : 7
Vest-Agder : 6
Vestfold : 7
Ostfold : 9
Lower apportionment:
Initial apportionment:
| Rodt | Sosiali | Arbeide | Senterp | Kristel | Venstre | Hoyre | Fremskr | Miljopa | Kystpar | Pensjon | Total
------------------+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------
Akershus | 0 | 1 | 6 | 1 | 1 | 1 | 4 | 5 | 0 | 0 | 0 | 19/ 16
Aust-Agder | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 3/ 4
Buskerud | 0 | 0 | 3 | 1 | 0 | 0 | 2 | 2 | 0 | 0 | 0 | 8/ 9
Finnmark | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 2/ 5
Hedmark | 0 | 0 | 3 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 6/ 8
Hordaland | 0 | 1 | 5 | 1 | 1 | 1 | 3 | 4 | 0 | 0 | 0 | 16/ 15
More og Romsdal | 0 | 0 | 3 | 1 | 1 | 0 | 1 | 2 | 0 | 0 | 0 | 8/ 9
Nordland | 0 | 1 | 3 | 1 | 0 | 0 | 1 | 2 | 0 | 0 | 0 | 8/ 10
Nord-Trondelag | 0 | 0 | 2 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 4/ 6
Oppland | 0 | 0 | 3 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 6/ 7
Oslo | 1 | 2 | 7 | 0 | 1 | 1 | 4 | 4 | 0 | 0 | 0 | 20/ 17
Rogaland | 0 | 1 | 4 | 1 | 2 | 1 | 3 | 4 | 0 | 0 | 0 | 16/ 13
Sogn og Fjordane | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 3/ 5
Sor-Trondelag | 0 | 1 | 4 | 1 | 0 | 0 | 1 | 2 | 0 | 0 | 0 | 9/ 10
Telemark | 0 | 0 | 2 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 4/ 6
Troms | 0 | 0 | 2 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 4/ 7
Vest-Agder | 0 | 0 | 2 | 0 | 1 | 0 | 1 | 2 | 0 | 0 | 0 | 6/ 6
Vestfold | 0 | 1 | 3 | 0 | 0 | 0 | 2 | 2 | 0 | 0 | 0 | 8/ 7
Ostfold | 0 | 0 | 4 | 0 | 1 | 0 | 1 | 2 | 0 | 0 | 0 | 8/ 9
------------------+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------
Total | 1/ 2 | 8/ 11 | 59/ 60 | 11/ 10 | 8/ 9 | 4/ 7 | 28/ 29 | 39/ 39 | 0/ 1 | 0/ 0 | 0/ 1 | 158/169
Modifying multipliers for parties:
Multiplier for Rodt : 1.50049 (1.16411/1.83687)
Multiplier for Sosialistisk Venstreparti: 1.21536 (1.21415/1.21658)
Multiplier for Arbeiderpartiet : 1.01095 (1.00633/1.01556)
Multiplier for Senterpartiet : 0.866367 (0.838258/0.894477)
Multiplier for Kristelig Folkeparti : 1.21339 (1.187/1.23978)
Multiplier for Venstre : 1.55411 (1.49282/1.61539)
Multiplier for Hoyre : 1.02043 (1.01688/1.02398)
Multiplier for Miljopartiet de Gronne : 5.5117 (4.32657/6.69683)
Multiplier for Pensjonistpartiet : 4.3455 (3.7324/4.9586)
| Rodt | Sosiali | Arbeide | Senterp | Kristel | Venstre | Hoyre | Fremskr | Miljopa | Kystpar | Pensjon | Total
------------------+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------
Akershus | 0 | 1 | 6 | 1 | 1 | 1 | 4 | 5 | 0 | 0 | 0 | 19/ 16
Aust-Agder | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 4/ 4
Buskerud | 0 | 1 | 3 | 0 | 0 | 0 | 2 | 2 | 0 | 0 | 0 | 8/ 9
Finnmark | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 2/ 5
Hedmark | 0 | 1 | 3 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 8/ 8
Hordaland | 1 | 1 | 5 | 1 | 1 | 1 | 3 | 4 | 0 | 0 | 0 | 17/ 15
More og Romsdal | 0 | 0 | 3 | 1 | 1 | 1 | 1 | 2 | 0 | 0 | 0 | 9/ 9
Nordland | 0 | 1 | 3 | 1 | 0 | 0 | 1 | 2 | 0 | 0 | 0 | 8/ 10
Nord-Trondelag | 0 | 0 | 2 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 4/ 6
Oppland | 0 | 0 | 3 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 6/ 7
Oslo | 1 | 3 | 7 | 0 | 1 | 2 | 5 | 4 | 1 | 0 | 0 | 24/ 17
Rogaland | 0 | 1 | 4 | 1 | 2 | 1 | 3 | 4 | 0 | 0 | 0 | 16/ 13
Sogn og Fjordane | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 3/ 5
Sor-Trondelag | 0 | 1 | 4 | 1 | 0 | 1 | 1 | 2 | 0 | 0 | 0 | 10/ 10
Telemark | 0 | 0 | 3 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 5/ 6
Troms | 0 | 0 | 2 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 4/ 7
Vest-Agder | 0 | 0 | 2 | 0 | 1 | 0 | 1 | 2 | 0 | 0 | 0 | 6/ 6
Vestfold | 0 | 1 | 3 | 0 | 0 | 0 | 2 | 2 | 0 | 0 | 0 | 8/ 7
Ostfold | 0 | 0 | 4 | 0 | 1 | 0 | 1 | 2 | 0 | 0 | 0 | 8/ 9
------------------+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------
Total | 2/ 2 | 11/ 11 | 60/ 60 | 10/ 10 | 9/ 9 | 7/ 7 | 29/ 29 | 39/ 39 | 1/ 1 | 0/ 0 | 1/ 1 | 169/169
Modifying multipliers for districts:
Multiplier for Akershus : 0.815298 (0.780579/0.850017)
Multiplier for Buskerud : 1.0353 (1.03245/1.03815)
Multiplier for Finnmark : 2.25041 (2.17715/2.32367)
Multiplier for Hordaland : 0.819152 (0.775819/0.862486)
Multiplier for Nordland : 1.30856 (1.25292/1.36419)
Multiplier for Nord-Trondelag : 1.31607 (1.24314/1.38901)
Multiplier for Oppland : 1.17995 (1.1474/1.2125)
Multiplier for Oslo : 0.75137 (0.741871/0.760869)
Multiplier for Rogaland : 0.820302 (0.765602/0.875002)
Multiplier for Sogn og Fjordane: 1.49343 (1.35079/1.63606)
Multiplier for Telemark : 1.06887 (1.04473/1.093)
Multiplier for Troms : 1.28276 (1.26419/1.30134)
Multiplier for Vestfold : 0.894262 (0.885612/0.902912)
Multiplier for Ostfold : 1.0094 (1.001/1.01781)
| Rodt | Sosiali | Arbeide | Senterp | Kristel | Venstre | Hoyre | Fremskr | Miljopa | Kystpar | Pensjon | Total
------------------+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------
Akershus | 0 | 1 | 5 | 0 | 1 | 1 | 4 | 4 | 0 | 0 | 0 | 16/ 16
Aust-Agder | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 4/ 4
Buskerud | 0 | 1 | 3 | 1 | 0 | 0 | 2 | 2 | 0 | 0 | 0 | 9/ 9
Finnmark | 0 | 1 | 2 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 5/ 5
Hedmark | 0 | 1 | 3 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 8/ 8
Hordaland | 1 | 1 | 4 | 1 | 1 | 1 | 3 | 3 | 0 | 0 | 0 | 15/ 15
More og Romsdal | 0 | 0 | 3 | 1 | 1 | 1 | 1 | 2 | 0 | 0 | 0 | 9/ 9
Nordland | 0 | 1 | 4 | 1 | 0 | 0 | 1 | 3 | 0 | 0 | 0 | 10/ 10
Nord-Trondelag | 0 | 0 | 3 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 6/ 6
Oppland | 0 | 0 | 4 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 7/ 7
Oslo | 1 | 2 | 5 | 0 | 1 | 2 | 3 | 3 | 0 | 0 | 0 | 17/ 17
Rogaland | 0 | 1 | 3 | 1 | 2 | 1 | 2 | 3 | 0 | 0 | 0 | 13/ 13
Sogn og Fjordane | 0 | 0 | 2 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 5/ 5
Sor-Trondelag | 0 | 1 | 4 | 1 | 0 | 1 | 1 | 2 | 0 | 0 | 0 | 10/ 10
Telemark | 0 | 0 | 3 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 6/ 6
Troms | 0 | 1 | 3 | 0 | 0 | 0 | 1 | 2 | 0 | 0 | 0 | 7/ 7
Vest-Agder | 0 | 0 | 2 | 0 | 1 | 0 | 1 | 2 | 0 | 0 | 0 | 6/ 6
Vestfold | 0 | 1 | 3 | 0 | 0 | 0 | 1 | 2 | 0 | 0 | 0 | 7/ 7
Ostfold | 0 | 1 | 4 | 0 | 1 | 0 | 1 | 2 | 0 | 0 | 0 | 9/ 9
------------------+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------
Total | 2/ 2 | 13/ 11 | 61/ 60 | 10/ 10 | 10/ 9 | 7/ 7 | 28/ 29 | 37/ 39 | 0/ 1 | 0/ 0 | 1/ 1 | 169/169
After this it went back to adjust parties again, then districts, and so
on. It needed to adjust parties 13 times and districts 13 times before
it found a final result:
Modifying multipliers for districts:
Multiplier for Buskerud : 1.00021 (1.00003/1.00039)
Multiplier for Telemark : 0.999337 (0.998849/0.999826)
| Rodt | Sosiali | Arbeide | Senterp | Kristel | Venstre | Hoyre | Fremskr | Miljopa | Kystpar | Pensjon | Total
------------------+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------
Akershus | 0 | 1 | 5 | 0 | 1 | 1 | 4 | 4 | 0 | 0 | 0 | 16/ 16
Aust-Agder | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 4/ 4
Buskerud | 0 | 0 | 3 | 1 | 0 | 0 | 2 | 3 | 0 | 0 | 0 | 9/ 9
Finnmark | 0 | 1 | 2 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 5/ 5
Hedmark | 0 | 1 | 3 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 8/ 8
Hordaland | 1 | 1 | 4 | 1 | 1 | 1 | 3 | 3 | 0 | 0 | 0 | 15/ 15
More og Romsdal | 0 | 0 | 3 | 1 | 1 | 1 | 1 | 2 | 0 | 0 | 0 | 9/ 9
Nordland | 0 | 1 | 4 | 1 | 0 | 0 | 1 | 3 | 0 | 0 | 0 | 10/ 10
Nord-Trondelag | 0 | 0 | 3 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 6/ 6
Oppland | 0 | 0 | 4 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 7/ 7
Oslo | 1 | 2 | 5 | 0 | 0 | 2 | 3 | 3 | 1 | 0 | 0 | 17/ 17
Rogaland | 0 | 1 | 3 | 1 | 2 | 1 | 2 | 3 | 0 | 0 | 0 | 13/ 13
Sogn og Fjordane | 0 | 0 | 2 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 5/ 5
Sor-Trondelag | 0 | 1 | 4 | 1 | 0 | 1 | 1 | 2 | 0 | 0 | 0 | 10/ 10
Telemark | 0 | 0 | 3 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 6/ 6
Troms | 0 | 1 | 3 | 0 | 0 | 0 | 1 | 2 | 0 | 0 | 0 | 7/ 7
Vest-Agder | 0 | 0 | 2 | 0 | 1 | 0 | 1 | 2 | 0 | 0 | 0 | 6/ 6
Vestfold | 0 | 1 | 2 | 0 | 0 | 0 | 2 | 2 | 0 | 0 | 0 | 7/ 7
Ostfold | 0 | 0 | 4 | 0 | 1 | 0 | 1 | 3 | 0 | 0 | 0 | 9/ 9
------------------+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------+---------
Total | 2/ 2 | 11/ 11 | 60/ 60 | 10/ 10 | 9/ 9 | 7/ 7 | 29/ 29 | 39/ 39 | 1/ 1 | 0/ 0 | 1/ 1 | 169/169
--
Regards,
Vidar Wahlberg
More information about the Election-Methods
mailing list