Re: [EM] Biproportional representation (was Re: Preferential voting system where a candidate may win multiple seats)
On 07/29/2013 07:22 PM, Vidar Wahlberg wrote: On Mon, Jul 29, 2013 at 01:36:49PM +0200, Kristofer Munsterhjelm wrote: On 07/28/2013 04:37 PM, Vidar Wahlberg wrote: 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. Apportionment according to divisor methods can be done in two ways: either explicitly (like Sainte-Laguë) or by a round-and-adjust method (like Webster). If I understand you correctly, your biproportional program uses the Webster method, i.e. you pick x so that SUM k=1...n round(support[k] * x) equals the desired number of seats. I don't know how to turn a given explicit divisor method into a given rounding method, so how would you implement modified Sainte-Laguë this way? I may misunderstand you here, but in the upper apportionment I used unmodified Sainte-Laguë. That is, exactly how it's done in counties today (excluding leveling seat), just on the national vote count and with 169 seats. As of modifying Sainte-Laguë that would only mean modifying the first divisor, which would have very little impact when 169 seats are to be apportioned. Although, I did try this and that resulted in Miljøpartiet de Grønne not winning a seat. Oh, I see. I thought you meant that the iteration procedure itself used unmodified Sainte-Laguë but could be altered to use modified Sainte-Laguë if so desired. If you're talking about the upper apportionment (i.e. the setting of the targets), then I understand you. Any method could be used to set the targets. For that matter, one could set the target to something not produced by a divisor method at all, although then it's not certain that the iterative process will find a solution. I'm not sure what you mean by exactly how it's done in counties today, though. If you mean that the apportionment of seats to counties (i.e. how many seats each district gets in the district target) is done by unmodified Sainte-Laguë, that's right. But the apportionment of seats to parties within each county (e.g. how many seats AP should get in Oslo according to the current system) is done by modified Sainte-Laguë. Since my last mail I've implemented preferential election (redo upper apportionment until all parties have at least n seats, each rerun excluding the party with least votes, transfering them to the next preference). I chose to use n seats instead of x percent as I only entered data for the 10 largest parties and thus would have to hard code the total amount of votes to get a correct vote percentage, but I digress. I note that this would also support what I call CPO-SL because it, too, returns as output which parties are to be excluded. So one would just run CPO-SL on the national ballots, find out which parties to exclude, do that, and then count support by first preference votes of the uneliminated parties. It would not be the same thing as running CPO-SL on each county to find more balanced councils there, though. Making a biproportional version of CPO-SL would be an interesting puzzle: I think that one would use something like minimax to balance the district concerns and the national concerns, but that is in any case a digression. - District seats are determined externally and thus not apportioned in this implementation. A similar trick could be used to implement a threshold if desired. It would be complicated, though, something like: 1. Do a county-by-county count. 2. Parties below the threshold have their number of seats fixed to the number of seats they got directly. 3. Fixing these parties' number of seats, determine the number of seats for the other parties by national Sainte-Laguë: each party gets a seat as in Sainte-Laguë, but when a party below the threshold have got all their seats according to 2., remove that party from the count. 4. Use the result as the target for the number of party seats. I'd still rather use an absolute but lower threshold, though; or none at all, like you're doing. Regretably I'm not quite following you here. To try to explain the method in short: In upper apportionment you decide how many seats each party gets, this is the final result and will not be changed (but where they receive the seats is yet to be decided). Seats in districts/counties are determined externally. Here is the only place we use Sainte-Laguë. If we want some sort of threshold or preferential election, it must be done here. Yes, that's what I'm saying. If the upper apportionment can be given outside the system itself, you can set it however you want. Say you want a threshold where all parties that get less than 4% national support only get as many seats as they would have got on a county-by-county basis (as is the case today). Then you would use another method, not national Sainte-Laguë, to determine how many seats each
Re: [EM] Biproportional representation (was Re: Preferential voting system where a candidate may win multiple seats)
On Mon, Sep 02, 2013 at 09:55:57AM +0200, Kristofer Munsterhjelm wrote: I'm not sure what you mean by exactly how it's done in counties today, though. If you mean that the apportionment of seats to counties (i.e. how many seats each district gets in the district target) is done by unmodified Sainte-Laguë, that's right. But the apportionment of seats to parties within each county (e.g. how many seats AP should get in Oslo according to the current system) is done by modified Sainte-Laguë. Correct, I explained poorly. I meant that the Sainte-Laguë method is used in the upper apportionment, just like it's used in counties, but the difference is that I use unmodified Sainte-Laguë (because it makes much less impact, even though it actually did result in one party not winning a seat in one recent election). One does not need to use Sainte-Laguë in the upper apportionment, one might as well use Webster's method. This really is just a detail, though. The particular example I gave there would seek to emulate the county only threshold by finding out the number of seats per party per county. For any party that gets less than 4% nationwide support, the number of seats they would get would be fixed to this number. For instance, Venstre would be fixed to get only 2 seats since its support of 3.88% fell short of the 4%. Then, after those parties' seat numbers have been fixed, the other parties would get seats as by ordinary (or modified) Sainte-Laguë. However, I did actually calculate the upper party apportionment with a threshold like the above, and the party target I ended up with was almost identical to the actual 2009 outcome. The only difference was that Arbeiderpartiet got one seat less and Høyre got one more; so that shows that, given the 4% threshold, the current leveling seat system is already pretty good at meeting the target. At least it is so for the 2009 outcome, though one may argue that outcome is not representative because it included unusually few parties. As to be expected, because todays system do strive to reach a fairly proportional representation on a national level, but when limited to 19 leveling seats, there are many scenarios where you'll still end up with disproportionality. One example is that large parties are probably to receive too many (as if it were one district) seats, which in turn will decrease the amount of seats to the other parties. Another example is that several parties may be just above the election threshold, which will give them about 6-7 seats, but they may only win 1-2 seats directly. Once there are 4 such parties (which happens to be the case in Norway at the moment, possibly 5 if MDG wins more support, and support for FrP is declining which eventually could make it 6), there won't be nearly enough leveling seats. Denmark solved this by increasing the amount of leveling seats, but even when that is done, the current algorithm for distributing leveling seats to the district can cause some really peculiar results (such as Venstre winning a seat in Finnmark in 2005, with nearly no support in the county). That said, and this going a bit on the sociological issues, an election threshold of 4% I believe is quite detrimental to our election system, especially when you can't rank your next preference. It will make it very difficult for new parties to challenge the the existing parties, and parties that drops below the election threshold may eventually disappear completely as people won't gamble their vote on a party that may not be (well) represented. Over time this may lead to a two-party system, which I do not believe would represent the people very well, at least not in Norway. We generally vote for a set of ideas (which parties represent), having to choose between only two sets will unlikely reflect the preferences of the population. But that is just Webster's method! And Webster's method is equivalent to Sainte-Laguë. So internally, the lower apportionment consists of alternating a Webster apportionment across (for the districts) and down (for the parties), adjusting the factors until convergence. That's what I mean by that the method uses Sainte-Laguë internally. Interesting. Maybe I've overlooked it, but I don't recall reading about this connection in the works that describe biproportional apportionment. This is good to know, though. As the amount of seats each party receives is already decided before the lower apportionment then I would assume that it will make little difference whether you floor, round or even ceil the quotients, I've not given it much thought or actually tried it, though. I did a cursory search and it doesn't seem like rational number support is planned for D. I suppose you could use a mathematical language (e.g. MATLAB or Mathematica's); or on the other end of things, use C or C++ with GNU MP's rational number functions or classes. But since the algorithm already works the way you have implemented it, that would
Re: [EM] Biproportional representation (was Re: Preferential voting system where a candidate may win multiple seats)
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.7 | total seats: 4 1.5/0.3 = 5.0 | 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.50 - 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
Re: [EM] Biproportional representation (was Re: Preferential voting system where a candidate may win multiple seats)
On Mon, Jul 22, 2013 at 10:49:52PM +0200, Kristofer Munsterhjelm wrote: To make the biproportional voting method work, the numbers should be set so that the rows give the correct allocation per party and the columns give the correct allocation per district (or vice versa, depending on what you assign to the rows and columns). So I think the simplest way to do so would be to apply the weighting to the vote numbers themselves to get effective votes. A significant drawback with weighting votes is that it will likely lead to an outcry of protests (why is my vote here in Oslo only worth half of a vote in Finnmark?). Arguably this is already the case, but it's disguised so people are most likely not aware of it. Something like this may be required though, as there's a theoretical possibility that a party can win a seat that can't be assigned to the party in any district: In Oslo there are 17 seats. Since Oslo is a small region with high population, votes there are weighted less than votes in for example Finnmark. If 18 parties enters the election with a party list only in Oslo, and these 18 parties win all the votes, evenly distributed among themselves, then deciding party seat amount based purely on votes with equal weighting is likely to give all these 18 parties one or more seats. There are not enough seats in Oslo for these parties, and the parties have no candidates who can fill the seat in any other region. Perhaps this scenario is as unlikely as two larger parties getting the exact same amount of votes (which I'm not sure how is dealt with in Norway), but it should nevertheless be adressed. Partly the idea behind all of this was to make every vote weighted equally when it comes to party proportionality, while keeping the possibility of giving certain regions a larger or smaller amount of the seats than their vote percentage dictates. I must admit, the more I look into this algorithm, the less enthusiastic I feel about it. Let me try to explain: It appears to be quite complex, even more so when regional seats are predetermined and not based on votes (unlike it is in the example at Wikipedia[1]). I find the explanation of the method difficult to understand, and I don't think it'll be any easier to explain how it roughly works to the general public. As we've discussed earlier, a method is more likely to be accepted if people understand it. 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. The end result does not seem to be greatly different compared to distributing seats using algorithms discussed earlier, such as using a quota to determine seats won for certain and distribute remaining seats to largest remainder which Juho suggested, or just distributing all seats to largest remainder in the reversed order the seats were won as I suggested earlier. If these ideas are flawed and/or can produce peculiar results I'd appreciate feedback. [1]: http://en.wikipedia.org/wiki/Biproportional_apportionment [2]: http://www.uusikaupunki.fi/~olsalmi/vaalit/Biproportional_Elections.html -- Regards, Vidar Wahlberg Election-Methods mailing list - see http://electorama.com/em for list info