Re: [EM] What does "proportional representation" MEAN? And list of known PR methods (know any more?)
Warren Smith wrote: Kristofer Munsterhjelm asked me what "proportional representation" (PR) means. At this time it is probably unwise to make a too-precise definition since every PR voting method seems to obey a different proportionality theorem. I say you should just assess each theorem on a case by case basis to see if you like it. But a somewhat imprecise definition is: ... HERE'S MY LIST OF KNOWN PR VOTING METHODS: ... That's my list. Is anybody aware of any other PR methods? Yes, the CIVS voting system implements a Condorcet PR method that I came up with. It seems to work well in practice, having been used for dozens if not hundreds of elections/polls. In the k=1 case it devolves to regular Condorcet. There is a description of it on the CIVS web site: http://www.cs.cornell.edu/w8/~andru/civs/proportional.html -- Andrew Election-Methods mailing list - see http://electorama.com/em for list info
[EM] VoteFair ranking as a PR method
Please include VoteFair ranking in your/Warren's list of PR methods. (See thread "What does "proportional representation" MEAN? And list of known PR methods (know any more?)", or message copied below.) VoteFair ranking is described in my book titled "Ending The Hidden Unfairness In U.S. Elections". Portions of the book can be viewed on Google books, and there is a (large, 19MB) downloadable PDF file of key chapters, with the link being on this page: http://www.votefair.org/province.html The most significant PR-related part of VoteFair ranking is VoteFair representation ranking. (It is described in chapter 15 of my book.) It fills a second equivalent seat -- such as in a legislature or board of directors -- with a candidate who best represents the people who are not well-represented by the winner of the first seat. It eliminates strategic voting techniques such as burying a key competitor and/or highly ranking an unpopular candidate. Also there is a component of VoteFair ranking called VoteFair partial-proportional ranking. It does the more familiar task of filling extra seats based on party preferences. However, it does so in a way that also involves VoteFair party ranking (and VoteFair popularity ranking to fill the first equivalent seat). (This method is described in Chapter 20.) The result of using all the components of VoteFair ranking is a legislature that best represents all the voters, including large minorities. There is yet another level of PR beyond filling legislative seats in a representative way. For this level I've developed an algorithm at www.NegotiationTool.com . As an example of what it does, it allows a parliament to choose cabinet members who are from multiple political parties, based on each parliament member ranking all the nominations. It does so without relying on any limits/quotas/etc. being imposed. As an example of why it's needed, consider the Iraqi Parliament where the Shiite majority outvotes the Sunnis and Kurds (and currently only elects non-Shiite cabinet members because of limits/requirements established from the outside). Without this legislative level of fair voting, 51 percent of a population can tell the other 49 percent what they can and cannot do. In my opinion, a big mistake made by many PR methods is that they make unfair compromises such as using closed party lists, using open party lists, using quotas, and/or using other unfair voting practices. Simply yielding party-category numbers that match the general population's party category numbers does not yield truly representative results if the method sacrifices fairness in terms of which candidates win the seats. VoteFair ranking keeps the voting simple (rank all the district's candidates in a single race, and also rank the parties), and protects against gerrymandering and strategic voting simply by being well-designed. I hope to have time to write further explanations of VoteFair ranking in this forum. In the meantime, feel free to ask questions. Richard Fobes VoteFair.org Kristofer Munsterhjelm asked me what "proportional representation" (PR) means. At this time it is probably unwise to make a too-precise definition since every PR voting method seems to obey a different proportionality theorem. I say you should just assess each theorem on a case by case basis to see if you like it. But a somewhat imprecise definition is: I would say that any voting method which elects W winers from N candidates (arbitrary 0http://rangevoting.org/Apportion.html http://www.RangeVoting.org/NewAppo.html http://www.RangeVoting.org/BishopSim.html M.L. Balinski & H. Peyton Young: Fair Representation: Meeting the Ideal of One Person, One Vote (2nd edition), Brookings Institution Press 2001 Asset voting also obeys a PR theorem. http://rangevoting.org/Asset.html paper #77 at http://www.math.temple.edu/~wds/homepage/works.html RRV also (RRV is kind of based on "stealing" the divisor-method idea, inside). paper #78 at http://www.math.temple.edu/~wds/homepage/works.html http://rangevoting.org/RRV.html Hare/Droop STV also. Nicolaus Tideman: The Single transferable Vote, J. Economic Perspectives 9,1 (1995) 27-38. And LPV(kappa) ("logarithmic penalty voting") also. Invented by F.Simmons. Described in paper #91 at http://www.math.temple.edu/~wds/homepage/works.html A
Re: [EM] strategy-free Condorcet method after all!
Dave, Jobst, the inventor of River, is well aware of the cycle problem, and Jobst would never advocate public use of a Condorcet method that failed clone loser, for example, but as near as I know his simple reverse Llull method is the first Condorcet method that gives zero incentive for insincere rankings, even if complete rankings are required (at least generically). As a corollary, it satisfies the Strong FBC. No other extant Condorcet method does even that. In other words it is a benchmark method. It gives us something to shoot for; a clone free version of the same, for example. The complicated method you referred to was my crude attempt at that. Forest Dave Ketchum Wrote ... >Took me a while, but hope what I say is useful. >Jobst had good words, except he oversimplified. >Centuries ago Llull had an idea which Condorcet improved a bit - compare each pair of candidates, and go with whoever wins in each pair. Works fine when there is a CW for, once the CW is found, it will win every following comparison. >BUT, in our newer studying, we know that there is sometimes a cycle, and NO CW. Perhaps useful to take the N*N array from an election and use its values as a test of Jobst's rules: There may be some comparisons before the CW wins one. Then the found CW will win all following comparisons. BUT, if no CW, you soon find a cycle member and cycle members win all following comparisons, just as the CW did above. >Summary: We are into Condorcet with ranking and no approval cutoffs. Testing the N*N array for CW is easy enough, once you decide what to do with ties. Deciding on rules for resolving cycles is a headache, but I question involving anything for this other than the N*N array - such as the complications Jobst and fsimmons offer. >Dave Ketchum Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] A Proportionally Fair Consensus Lottery for which Sincere Range Ballots are Optimal
Thanks for the encouragement, Jobst, and for supplying the proof. It was your strategy free Condorcet method that led me in this direction: I simply adapted it to your Proportionally Fair Consensus Lottery ideas using range ballots instead of taking a second head count after the choice was put to the voters. Most of the credit should be yours; in fact, the proof and all of the ingredients are yours. I hurried to post the message this morning, because I was sure that you were going to beat me to it! I would certainly believe you if you said that you had already thought of the same thing but didn't have time to post the message before I did. Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] A Proportionally Fair Consensus Lottery for which Sincere Range Ballots are Optimal
Dear Raph, you wrote: > Likewise, you might as well pick your favourite as favourite. This is, unfortunately, not true: The labelled favourite influences the expected ratings against which possible consensus options are compared on each ballot, so you can have the incentive to exaggerate by labelling a more extreme candidate than your true favourite in order to lower those ratings and make your preferred consensus more likely! But this, I guess, will not decrease but rather increase the method's efficiency in realistic examples. > The consensus candidate is different. It is inherently strategic. > > There is the possibility for group "chicken" effects. For example, a > party could say that all of their supporters are going to rate > candidate X at minimum, so there is no point in nominating that > candidate. This could cause the other partys' supporters to disregard > that candidate as a potential consensus candidate. > > Also, I wonder if it might be worth having a rule that allows > additional consensus attempts. > > For example, if 10% refuse, then the other 90% would be given the > option of choosing the consensus candidate. The 2 choices in that > case would be > > Option 1) > Full random ballot > > Option 2) > 90% chance of consensus candidate > 10% chance of random ballot (only the ballots outside the 90% are considered) > > This would probably break the strategic "purity" of the single stage method. I guess so, too, but I think we can overcome the unanimity requirement in a different way. Let me think about it... Yours, Jobst Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] A Proportionally Fair Consensus Lottery for which Sincere Range Ballots are Optimal
Dear folks, although Forest's posting comes along so matter-of-factly, let's make it absolutely clear that it is an ENORMOUS MILESTONE! Why so? He describes a very SIMPLE, EFFICIENT, and FAIR method which REVEALS THE TRUE UTILITY VALUES of all voters who are rational in the sense of von Neumann and Morgenstern. The only other known methods which have this revelation property are not only more artificial and complex but are much less efficient or require monetary taxes to be paid and destroyed (like the Clarke tax). Very simple proof that sincere ratings are optimal: My ratings are only relevant in a specific situation. In this situation a fall-back lottery has already been determined from all the labels (thus not dependent on my ratings), and a possible consensus option has been nominated from the circle on a drawn ballot (thus also independently from my ratings). If my ratings are relevant, they will decide between this given fall-back lottery and this given nominated consensus option, but I will not know beforehand which lottery and which nominated option they will be (except if I knew all other ballots, which is impossible in a secret poll). So the only way to make sure that my ratings will lead to the fall-back lottery when I prefer it over the nominated consensus option, and that they will lead to the nominated consensus option when I prefer it to the fall-back lottery, is to give ratings that reflect my true preferences, in other words, to specify a set of sincere utility values. Note that this is not only true in some equilibrium situation but NO MATTER HOW THE OTHERS VOTE! In other words, it is always a dominant strategy. Now, that does not mean, however, that the whole method is strategy-free, since the other part of the ballot, namely the circle and the label, are strategic. I may, for example, have incentives to label a more extreme option as favourite than my true favourite, in order to lower the expected rating of the fall-back lottery and make a consensus more probable. However, every such strategic behaviour would be visible from the ballot since the labelled favourite would not have the highest rating. That is a very interesting property which I have never seen before in any method: you have the incentive to vote strategically, but you cannot hide if you do so! My guess is that we will soon find a similar method in which a single voter cannot prevent the consensus completely but only lower its probability... Forest: EXCEPTIONALLY WELL-DONE! Jobst fsimm...@pcc.edu schrieb: > A proportionally fair lottery is a lottery method in a which any faction of > the > voters can unilaterally guarantee that their common favorite will be elected > with a probability proportional to the size of their faction. > > A consensus candidate is any candidate that would be liked at least as much as > the random favorite by 100 percent of the voters (assuming all voters to be > rational). > > A consensus lottery is a method that elects consensus candidates with > certainty > (again, assuming rational voters). > > I won't attempt to define "sincere range ballot" here, but the meaning will be > apparent from this method: > > Ballots are range style (i.e. cardinal ratings). > > Each voter rates the candidates, circles one of the names as a proposed > consensus candidate, and labels another (or perhaps the same) name as > "favorite" > or "favourite." > > Have I overlooked anything? > > The ballots are collected and the probabilities in the "random favorite" > lottery > are determined. > > These probabilities are used to determine and mark a "random favorite rating > expectation" on each range ballot. > > A ballot is then drawn at random. > > If the circled name on the randomly drawn ballot has a rating above the > "random > favorite rating expectation," on any ballot (including the one in play), then > another ballot is drawn, and the indicated favorite of the second ballot is > elected. > > Otherwise, the proposed consensus candidate whose name was circled on the > first > drawn ballot is elected. > > That's it. > > Note that any voter has the power to turn the election into "random favorite" > by > giving only one candidate (favorite=consensus) a positive non-zero rating. > But > whenever that is optimal rational strategy, sincere range yields the same > expectation, and is therefore optimal, too. > > > > > > > Election-Methods mailing list - see http://electorama.com/em for list info
[EM] Does this method have a name, pt II
As part of coding my simulator, I have implemented a Condorcet method that goes like this: A candidate X's victory score is equal to the sum of all victories of X against other candidates. If the pairwise matrix is d, and d[A,B] is the number of voters preferring A to B, then the victory of X against Y is: If WV, 0 if d[X,Y] <= d[Y,X], otherwise d[X,Y] If margins, max(0, d[X,Y] - d[Y,X]). The candidate with the greatest victory score is the winner. - I've called this method "Offensive L-R", because it's like least-reversal, only instead of awarding the first place to the one with the least defeat sum ("defensive"), it awards it to the one with the greatest victory sum ("offensive"). Does the method have a name already? It's so simple I can't but think it's already been invented. Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] What does "proportional representation" MEAN? And list of known PR methods (know any more?) correction
> > If the clusters are arranged along a line without overlapping, > then the median> voter candidate on that line will get the seat. So the method > picks the> Condorcet winner for one dimensional issue spaces.> > > > Sorry, This last statement is wrong! Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] What does "proportional representation" MEAN? And list of known PR methods (know any more?)
Here's another idea for PR: First use MCA ballots (Majority Choice Approval, where favorites and also approved are indicated) to get a distance between pairs of candidates. The distance between two candidates is the number of ballots on which just one of the two is neither favorite nor also approved. Next do a cluster analysis of the candidates by one of the standard methods that yields a binary tree as output. Initialize a system for labeling each node of the tree by labeling each branch with both the number of candidates that it (the branch) leads to and the total number of "favorites" garnered by all of those candidates. One by one send each "seat" down the tree until it reaches a candidate. At each node a decision must be made. Which of the two branches will get the seat? Send the seat down the branch with the greatest "favorite" label. Then make the following label adjustments: We decrement (i.e. subtract one from) the number of candidates label, and then reduce the number of favorites label by the number of voters a seat is supposed to represent. If this last number is still positive when the candidate number reaches zero, then the remainder is transferred proportionately to the "favorite" totals of the branches of the sub-tree beginning at the other branch. If there is only one seat, then at each node it goes according to the majority in the sub-tree for which that node is the root. If any candidate is majority favorite, then that candidate will win the one seat. If the clusters are arranged along a line without overlapping, then the median voter candidate on that line will get the seat. So the method picks the Condorcet winner for one dimensional issue spaces. Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] A Proportionally Fair Consensus Lottery for which Sincere Range Ballots are Optimal
On Thu, Nov 19, 2009 at 8:08 PM, wrote: > If the circled name on the randomly drawn ballot has a rating above the > "random > favorite rating expectation," on any ballot (including the one in play), then > another ballot is drawn, and the indicated favorite of the second ballot is > elected. > > Otherwise, the proposed consensus candidate whose name was circled on the > first > drawn ballot is elected. Effectively, a random voter proposes a consensus candidate. The random ballot probabilities are determined and each voter is given the option to vote Yes/No to the consensus candidate. Unless all prefer the consensus candidate to the expected utility of the random ballot, the random ballot method is used. It is clear that honest range is the best plan as it doesn't affect anything else. Likewise, you might as well pick your favourite as favourite. The consensus candidate is different. It is inherently strategic. There is the possibility for group "chicken" effects. For example, a party could say that all of their supporters are going to rate candidate X at minimum, so there is no point in nominating that candidate. This could cause the other partys' supporters to disregard that candidate as a potential consensus candidate. Also, I wonder if it might be worth having a rule that allows additional consensus attempts. For example, if 10% refuse, then the other 90% would be given the option of choosing the consensus candidate. The 2 choices in that case would be Option 1) Full random ballot Option 2) 90% chance of consensus candidate 10% chance of random ballot (only the ballots outside the 90% are considered) This would probably break the strategic "purity" of the single stage method. Election-Methods mailing list - see http://electorama.com/em for list info
[EM] A Proportionally Fair Consensus Lottery for which Sincere Range Ballots are Optimal
A proportionally fair lottery is a lottery method in a which any faction of the voters can unilaterally guarantee that their common favorite will be elected with a probability proportional to the size of their faction. A consensus candidate is any candidate that would be liked at least as much as the random favorite by 100 percent of the voters (assuming all voters to be rational). A consensus lottery is a method that elects consensus candidates with certainty (again, assuming rational voters). I won't attempt to define "sincere range ballot" here, but the meaning will be apparent from this method: Ballots are range style (i.e. cardinal ratings). Each voter rates the candidates, circles one of the names as a proposed consensus candidate, and labels another (or perhaps the same) name as "favorite" or "favourite." Have I overlooked anything? The ballots are collected and the probabilities in the "random favorite" lottery are determined. These probabilities are used to determine and mark a "random favorite rating expectation" on each range ballot. A ballot is then drawn at random. If the circled name on the randomly drawn ballot has a rating above the "random favorite rating expectation," on any ballot (including the one in play), then another ballot is drawn, and the indicated favorite of the second ballot is elected. Otherwise, the proposed consensus candidate whose name was circled on the first drawn ballot is elected. That's it. Note that any voter has the power to turn the election into "random favorite" by giving only one candidate (favorite=consensus) a positive non-zero rating. But whenever that is optimal rational strategy, sincere range yields the same expectation, and is therefore optimal, too. Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Proportional Representation from Ratings Ballots
(Ahem), actually it's: Stage 1, (Election stage) select k1 so that k1*[ w(a)*r(a) + w(b)*r(b) + . ] = 1 Each candidate gets k1*w(x)*r(x) Stage 2, (Elimination stage) select k2 so that (k2)^2 * ([w(c)*r(c)]^2 + [w(d)*r(d)]^2 + ... ) = 1 - k1*[w(a)*r(a) + w(b)*r(b)] Each candidate gets k2*[w(x)*r(x)] Eliminate the remaining candidate who scores the lowest. Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Another auto districting proposal (Crystal districting?)
On Nov 19, 2009, at 6:55 PM, Raph Frank wrote: On Thu, Nov 19, 2009 at 4:00 PM, Juho wrote: My thinking is that it might be easier to agree about the targets rather than the whole procedure. The targets can be simpler to define. Following Raph Franks model it would be thus enough to say that any N points and the kn values and then derive the border lines and the jointly agreed value of the solution from this data. That would not leave much space for strategies and gerrymandering. The proposed solutions would be evaluated and the one with best value would be declared the winner. Well, ideally the method should be a well defined process rather than an optimisation method. This is true from the point of view that it would be good to have a known algorithm that can automatically (and in reasonable time) find the best result. On the other hand the optimization approach is a superset of the procedural approach. The optimization approach works also in the case where finding the best answer (or proving that some answer is the best) is not computationally feasible (but when optimization can find good enough answers). It may also be easier to define and agree just the targets / criterion. I also like the idea of defining the ideal outcome instead of defining a procedure (that might or might not yield a good result) (the agreed criterion is closer to defining the actual targets). It would take as its input a set of points and output a map. Splitline also requires a description of the State boundary. I think the optimization approach that I proposed would as well require very similar data, except that the points could be picked at random and not given as input. However, it would be perfectly valid to give a measure and then allow anyone submit a map districting. Yes, for splitlines one could e.g. just set a requirement that the borders should be straight lines and there should be n-1 lines (to get n districts) (+ the border length and even population distribution requirements). I think that if the block boundaries are decided before the census and the number of blocks is large enough (say 100-300 people per block on average), then it would be hard to gerrymander using block boundaries. Yes, some suitably small size should be set to reduce gerrymandering. The process could be something like - based on the old census, define the blocks for the new census -- A group of contiguous old blocks with population < 500 may be combined into a new block -- Old blocks may be split into pieces (if > 1000*N, it must be split into N+1 parts) -- otherwise, the blocks shall remain the same as previously Yes. In the case that they are already small enough there would not even be any interest to find "politically appropriate" blocks. - Geographic data is released - Hold census - Population data is released - Format for maps is published - Anyone can submit a map - best map after 6 months wins. Yes. With computers (and if working sw is already available to all and all the rules are already well known) also shorter period should be enough. Ofc, that requires that the SC is able to determine which map wins based on the description of the measure in the legislation. Yes, the comparison method should be well defined and feasible to compute. The optimization algorithms should be able call this subroutine thousands of times. Juho Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Another auto districting proposal (Crystal districting?)
On Thu, Nov 19, 2009 at 3:35 PM, Kristofer Munsterhjelm wrote: > If you're dealing with redistricting, the competition solution that you > mentioned could work, but it might well be that, for redistricting, > capturing the exact tradeoff between looking like "communities of interest" > and being completely neutral is a task best left to an independent > commission. Another option is to automatically generate a map, and then allow a commission to tweak that map. For example, you could have a rule that at least 85% of the people in each district must be placed in the district that they were automatically assigned to. Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Another auto districting proposal (Crystal districting?)
On Thu, Nov 19, 2009 at 4:00 PM, Juho wrote: > My thinking is that it might be easier to agree about the targets rather > than the whole procedure. The targets can be simpler to define. Following > Raph Franks model it would be thus enough to say that any N points and the > kn values and then derive the border lines and the jointly agreed value of > the solution from this data. That would not leave much space for strategies > and gerrymandering. The proposed solutions would be evaluated and the one > with best value would be declared the winner. Well, ideally the method should be a well defined process rather than an optimisation method. It would take as its input a set of points and output a map. Splitline also requires a description of the State boundary. However, it would be perfectly valid to give a measure and then allow anyone submit a map districting. I think that if the block boundaries are decided before the census and the number of blocks is large enough (say 100-300 people per block on average), then it would be hard to gerrymander using block boundaries. The process could be something like - based on the old census, define the blocks for the new census -- A group of contiguous old blocks with population < 500 may be combined into a new block -- Old blocks may be split into pieces (if > 1000*N, it must be split into N+1 parts) -- otherwise, the blocks shall remain the same as previously - Geographic data is released - Hold census - Population data is released - Format for maps is published - Anyone can submit a map - best map after 6 months wins. Ofc, that requires that the SC is able to determine which map wins based on the description of the measure in the legislation. Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Another auto districting proposal (Crystal districting?)
Juho wrote: Well, this approach is also complex in the sense that the general optimization algorithms may be as complex as you want, but the optimization algorithms are totally independent of the politics and the basic rules that determine what the final outcome should be (the criterion) can be quite simple and intuitive. (Additional criteria like favouring border lines that follow the borders of states or rivers etc. can be easily included in the agreed criterion. Maybe even higher cost of splitting cities etc.) Splitline works because it's recursive. Any sort of divison algorithm where you can smoothly control the relative sizes of the two districts will work, also. Just subdivide into two, then freeze one and subdivide the other. After you're done, unfreeze the first (and so on). It may not produce the best result if the borders can move on the unfrozen areas, but should work. As for general optimization, if you're dealing with an election method, then the optimization's approximation to the optimum (you can't ensure it'll reach the true optimum if there are multiple local optima and no additional structure) becomes a different rule itself. For instance, Borda is a 5-approximation to the optimal Kemeny ordering, but Borda is a completely different method from Kemeny. If you're dealing with redistricting, the competition solution that you mentioned could work, but it might well be that, for redistricting, capturing the exact tradeoff between looking like "communities of interest" and being completely neutral is a task best left to an independent commission. Of course, one can also dissolve the problem rather than solve it, and employ some PR method which would greatly diminish the incentive to do any gerrymandering in the first place. Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Another auto districting proposal (Crystal districting?)
On Nov 19, 2009, at 5:35 PM, Kristofer Munsterhjelm wrote: Juho wrote: Well, this approach is also complex in the sense that the general optimization algorithms may be as complex as you want, but the optimization algorithms are totally independent of the politics and the basic rules that determine what the final outcome should be (the criterion) can be quite simple and intuitive. (Additional criteria like favouring border lines that follow the borders of states or rivers etc. can be easily included in the agreed criterion. Maybe even higher cost of splitting cities etc.) Splitline works because it's recursive. Any sort of divison algorithm where you can smoothly control the relative sizes of the two districts will work, also. Just subdivide into two, then freeze one and subdivide the other. After you're done, unfreeze the first (and so on). It may not produce the best result if the borders can move on the unfrozen areas, but should work. As for general optimization, if you're dealing with an election method, then the optimization's approximation to the optimum (you can't ensure it'll reach the true optimum if there are multiple local optima and no additional structure) becomes a different rule itself. For instance, Borda is a 5-approximation to the optimal Kemeny ordering, but Borda is a completely different method from Kemeny. If you're dealing with redistricting, the competition solution that you mentioned could work, but it might well be that, for redistricting, capturing the exact tradeoff between looking like "communities of interest" and being completely neutral is a task best left to an independent commission. Of course, one can also dissolve the problem rather than solve it, and employ some PR method which would greatly diminish the incentive to do any gerrymandering in the first place. My thinking is that it might be easier to agree about the targets rather than the whole procedure. The targets can be simpler to define. Following Raph Franks model it would be thus enough to say that any N points and the kn values and then derive the border lines and the jointly agreed value of the solution from this data. That would not leave much space for strategies and gerrymandering. The proposed solutions would be evaluated and the one with best value would be declared the winner. The optimization procedures may not find the global optimum (but only one of the local optima), but if there is an algorithm that can find the global optimum then that solution will also be found. It is possible that some party (that runs some optimization procedures) would not publish the best solution it found (since the second best is better to this party) but the field would be free for anyone else to find that even better result. At some point one must freeze the solution and ignore any better solution that someone might find later. In most cases I guess it is quite improbable that better solutions would be found later. And if they are found then they might not be much better (probably true for most sensible criteria). No rules are needed for the optimization algorithm (= just let the scientists and politicians and private citizens do their best + maybe arrange some official calculations too to make sure that at least someone makes a serious attempt to find the best solution). Juho Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Dectecting Clone Sets
On Nov 18, 2009, at 11:33 PM, fsimm...@pcc.edu wrote: How's this for making Kemeny clone free? Ballots are ordinal with equal rankings and truncation allowed. The distance between two candidates is the number of ballots on which they are distinguished, i.e. one ranked and one not, or both ranked but not equal. In normal Kemeny the distance between two ballots is the minimum number of transpositions to convert one ballot into the other. My suggestion is to modify this count by giving each transposition a weight proportional to the distance between the two candidates involved. The Kemeny order is the permutation of the candidates whose average Kemeny distance to the ballots is minimum. I claim that if the suggested modified Kemeny distance is used, then the method is clone free. How about this example. 1: A>B 1: B>A => a tie 1: A1>A2>B 1: B>A1>A2 It seems that the method elects now A1. Introduction of a clone would thus change the balance. Did I get the definition right? (= for each vote if some pair is not ordered right in the result then add as many points as the distance between the candidates is in this vote) Kemeny is NP hard because there are so many permutations to check, not because the distances are hard to calculate. So I suggest that various standard permutations always be checked along with each ballot order, as well as as many other orders as anybody wants to nominate. Yes, it'd be easy to allow anyone to run some generic optimization procedures themselves and propose solutions (also and maybe especially after the votes are already known). The "official calculation procedure" could also use some monte carlo optimization and thus include also whatever random permutations. It would be enough to define the criterion that can be used to identify the best result and accept any methods to be used to find it (also to make sure that the best result will not fall outside of the "accepted calculation rules"). Juho The ballot orders that have truncations or equal rankings should be completed in various ways (for this purpose only, not for use in the distance or average distance computations) if a complete ordering of the candidates is desired. Election-Methods mailing list - see http://electorama.com/em for list info Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Proportional Representation from Ratings Ballots
On Thu, Nov 19, 2009 at 12:49 PM, Raph Frank wrote: > If no candidate is elected, a different rule is used, each ballot is > scaled so that > > [w(a)*r(a)]^2 + [w(b)*r(b)]^2 + ... = 1 > > The running candidate the the lowest score is then eliminated. Stage 1, (Election stage) select k1 so that k1*[ w(a)*r(a) + w(b)*r(b) + . ] = 1 Each candidate gets k1*w(x)*r(x) Stage 2, (Elimination stage) select k2 so that k2*(w(c)*r(c)^2 + w(d)*r(d)^2 + ... ) = 1 - k1*[w(a)*r(a) + w(b)*r(b)] Each candidate gets k2*w(x)*r(x)^2 Eliminate the remaining candidate who scores the lowest. Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Proportional Representation from Ratings Ballots
Stealing the Meek's method proof :). This is the existance proof: A weighting vector is defined as "feasible" if all elected candidates have a score >= the quota (Q) A candidate receives from each ballot (B) a score (S) equal to S(B) = r(c)*w(c)/(sum_over_x(r(x)*w(x)) r(x) is the rating for the candidate on that ballot w(x) is the global weighting of that candidate The candidate's total T(c) is the sum of the vote received from each ballot Theorom: Replacing an elected candidate's weight by w(c)*k will not convert a feasible vector into an non-feasible one, if k>=Q/T(c) Proof: The candidate will receive from each ballot S_new(B) = r(c)*w_new(c)/(sum_over_x(r(x)*w_new(x)) Only 1 term has changed in the sum Since w_old(x) >= w_new(c) and r(c) >= 0, then the sum cannot increase, i.e. sum_over_x(r(x)*w_new(x)) <= sum_over_x(r(x)*w_old(x)) Thus, S_new(B) >= r(c)*w_new(c)/(sum_over_x(r(x)*w_old(x)) replacing w_new(c) with w_old(c)*k as required, gives S_new(B) >= r(c)*w_old(c)*k/(sum_over_x(r(x)*w_old(x)) Re-arranging: S_new(B) >= k*[r(c)*w_old(c)/(sum_over_x(r(x)*w_old(x)) S_new(B) >= k*S_old(B) Thus, the candidate will receive form each ballot a score that is at least k times as large as before the change. Thus, T_new(c) >= T_old(c)*k Assuming, k>=Q/T_old(c) T_new(c) >= T_old(c)*[Q/T_old(c)] T_new(c) >= Q Thus, the candidate in question who had his weighting decreased will still have at least a quota. All other candidates will at worst have their vote totals remain static, and will likely increase. (The same proof, except their weight doesn't actually decrease). This means that if the vector was feasible initially, then it will still be feasible after updating the weight of candidate c. This means that the process can be applied over and over. In each step, the weighting of one of the elected candidates will be decreased, but never increase. This means that the total vote held by the elected candidates will decrease. This also gives an algorithm. You can apply that rule to each elected candidate in turn. In fact, you can update them all in 1 go (set a weights w(c) = Q/T(c) for elected candidates). If you update them in order, then all the other candidate's who haven't being reduced yet will have totals that will have increased slightly (or stayed the same). Thus, k = Q/T(c) for all the other candidates will drop (or stay the same). If you use the k from before the update, it will still be greater or equal to the k that would have been used if they were done in order, which is all that is required. Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Proportional Representation from Ratings Ballots
On Thu, Nov 19, 2009 at 4:51 AM, Brian Olson wrote: > Oh, that is a problem. It gets the right answer if I use L1 norm instead of > L2. I think L2 norm is going to work better for single-seat IRNR but L1 norm > better for multi-seat. L2 inflates the amount of vote that winds up getting > applied to multiple choices. The L1 norm mean that each voter always gets to cast exactly 1 vote (ratings add to 1). Thus the total number of votes cast is always constant. This means that a quota can be easily determined. You could use a different rule for eliminating than you use for electing (and I think that is a good idea anyway). For example, for electing, each ballot is scaled so that w(a)*r(a) + w(b)*r(b) + . = 1 All eliminated candidates have a w(x) = 0 and all non-elected candidates have a weighting of 1. Elected candidates have weighting so that they have exactly a quota of the votes. If any candidate meets the Droop quota, that candidate is declared elected and the next round is started. If no candidate is elected, a different rule is used, each ballot is scaled so that [w(a)*r(a)]^2 + [w(b)*r(b)]^2 + ... = 1 The running candidate the the lowest score is then eliminated. (The weights are based on the L1 calculation) This process has the nice feature that a group of voters equal to a Droop quota will decide their candidate using the L2 single seat (L2) version of the process. (This assumes that they rate all non-party candidates at zero and all voters outside the group rate their candidates at zero). Also, there is also a question if the weights assigned in step 1 will always yield a unique set of weights. Hopefully there is a Meek's method like proof. Election-Methods mailing list - see http://electorama.com/em for list info