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 ---- Election-Methods mailing list - see http://electorama.com/em for list info
