[EM] Another auto districting proposal (Crystal districting?)
Was thinking, what about something like: 1) Select N*M points on the map somehow. N is the number of seats M is a power of 2 (say 256) 2) Each block is assigned to the point that has the lowest d^2 + kn d = distance from block (or person) to point kn = offset for that point 3) Select the kn values so that all points have equal population. This generates a convex region for each point. (Hopefully, there is always a unique solution?). The population difference between the max and min regions would be less than double the size of the max census block (so less than 2 (i.e. one or zero), if each resident was considered individually, and they all lived alone). One issue at this point is that ideally, these blocks should themselves be contiguous. Depending on how the state boundary goes, this might not occur. If they aren't contiguous, then the resulting districts wouldn't be guaranteed to be contiguous. Ofc, this is also true for splitline. 4) Find the 2 regions such that a) they are contiguous b) they haven't been combined already in this round c) If they split the map into 2 parts, all resulting pieces must still have an even number of regions d) they have the best measure of some kind (also if combining 2 regions will fix a non-contiguous region problem, then they must be given priority?) 5) Combine those 2 regions into a combined region 6) Goto 4) unless all regions have been combined in this round 7) If there are more than N regions remaining, then advance to next round and goto 4) Notes on the combination rules: a) they are contiguous This is obvious b) they haven't been combined already in this round Since M is a power of 2, by pairing off all the blocks in each round, after a log2(M) rounds there will be N regions. c) If they split the map into 2 parts, all resulting pieces must still have an even number of regions This is to prevent regions ending up locked out and unpairable. For example, if the regions formed a line ABCDEFGH and BC was combined, then A would be isolated. A--DEFGH Thus it can't be combined. This means that the only valid combinations in the example are AB, CD, EF, GH. Also, it is important that connected refers to connections that occur inside the State boundary. The regions near the edges of the State will extend to infinity, but connections outside the state don't count. d) they have the best measure of some kind This should try to combine regions of dense population. For example, - the perimeter when combined (lower better) - the distance between their centres of population (lower better) - area (low better) - Area/(perimeter^2) (high better) Note on step 1) I think a fast version of splitline should be sufficient here. For example, you could alternate between N-S and E-W lines. Once M*N boxes are created, you could take the centre of population of each box as one of the points. Each step would only require a median search. There would be no requirement to figure out the intercept point between the lines and the State boundary. Also, population balance isn't critical here (though can probably achieved). Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Is there a PR voting method obeying participation criterion?
Abd wrote snip Under Robert's Rules, if a voter writes something on a ballot, the voter has voted, and the vote is counted in the basis for majority, snip This is not necessarily correct. Abd is probably relying on the statements on page 402-3 of RRONR 10th edition, that even illegal votes cast by legal voters are included in the basis and that a ballot that registers any evidence of having some opinion should be included. However, a voter who casts a ballot may partially abstain by marking fewer candidates than allowed (see Right of Abstention page 394). Abstaining (as with a blank ballot) removes the ballot from the basis of a majority calculation (see Majority Vote - the Basic Requirement page 387). Thus in an IRV election it is arguable either way as to whether a ballot that abstains as to any preference between two finalists (registers no opinion on this particular question) should be included in the basis or not. The actual practice of organizations using IRV (preferential voting) on which RRONR is based, indicates rather convincingly that exhausted ballots are not used in the basis for calculating a winning threshold. Abd and I have been around and around on this in the past, and I have no desire to revisit the topic, but I just wanted to indicate that this is not an open and shut case as Abd suggests. Terry Bouricius - Original Message - From: Abd ul-Rahman Lomax a...@lomaxdesign.com To: Warren Smith warren@gmail.com; election-methods election-meth...@electorama.com Sent: Tuesday, November 17, 2009 10:27 PM Subject: Re: [EM] Is there a PR voting method obeying participation criterion? At 01:08 PM 11/17/2009, Warren Smith wrote: This seems to be an open question at present. But it might be pretty easy to prove or disprove. A multiwinner voting method obeys participation if an extra voter, by voting honestly, cannot make the election result worse (in her view) than if she had not voted. Might be a small point, but voted should be defined. Under Robert's Rules, if a voter writes something on a ballot, the voter has voted, and the vote is counted in the basis for majority, and analogous for PR would be that the voter has possibly increased the quota. But we can also look at what happens if the voter votes for an irrelevant candidate. If we are going to be able to properly analyze the systems in a fair way, I think we have to assume that the voter votes for someone who is at least eligible, and that if it's Asset, the candidate actually is available to recast the vote and fairly functions as an effective representative of the voter in further process. No voting method can protect a voter from being dissatisfied with the candidate they voted for! Asset, then, could only change the outcome negatively for the voter by causing some effect due to increasing the quota. How could that happen? From the voter voting, the quota increased by a fraction. For accuracy of vote transfers later on, I recommend that exact quotas be used. In the first round, the fractional vote is irrelevant, but it would be considered when determining excess votes available for transfer. In any case, an increase in quota could cause a failure to immediately elect, or could prevent a later election. But the candidate holding this voters' vote could overcome this, still effectively casting the voter's vote to improve the outcome, should an initial election that would improve the outcome fail by one vote, being a fractional vote short. I think Asset, properly implemented, satisfies a reasonable interpretation of participation. There is no harm caused by the voter's participation that cannot be remedied by a proper recasting of the voter's vote. Ah! The voter's vote can affect more than one election. But if fractional vote transfers can be made (which I recommend) then the voter's proxy can fix the problem by spreading that vote among the affected candidates. If fractional vote transfers can't be made, then, sure, there is a technical failure which is basically roundoff error. That's silly, an example of voting criteria gone mad, separated from practical reality. It is fair if symmetric under permuting the candidates and voters. Conjecture: there does not exist a fair multiwinner proportional representation voting method obeying participation. I don't know how to apply fair. Can you give an example of a system which is not fair by this definition? That would help. 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] Another auto districting proposal (Crystal districting?)
This is a nice approach. Maybe it could be simpler though. What do you think about using N points and the d^2+kn rule, and determining a criterion that tells how good some given division is (taking path lengths, equal distribution of voters etc. as parameters), and then use any generic optimization algorithms that can modify both the kn values and the location of the points to find the best solution based on the agreed criterion? On could either agree one official optimization algorithm and then run it, or one could allow anyone to try to optimize the division and then officially adopt the best found result to be used in the elections. 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.) Juho On Nov 18, 2009, at 4:29 PM, Raph Frank wrote: Was thinking, what about something like: 1) Select N*M points on the map somehow. N is the number of seats M is a power of 2 (say 256) 2) Each block is assigned to the point that has the lowest d^2 + kn d = distance from block (or person) to point kn = offset for that point 3) Select the kn values so that all points have equal population. This generates a convex region for each point. (Hopefully, there is always a unique solution?). The population difference between the max and min regions would be less than double the size of the max census block (so less than 2 (i.e. one or zero), if each resident was considered individually, and they all lived alone). One issue at this point is that ideally, these blocks should themselves be contiguous. Depending on how the state boundary goes, this might not occur. If they aren't contiguous, then the resulting districts wouldn't be guaranteed to be contiguous. Ofc, this is also true for splitline. 4) Find the 2 regions such that a) they are contiguous b) they haven't been combined already in this round c) If they split the map into 2 parts, all resulting pieces must still have an even number of regions d) they have the best measure of some kind (also if combining 2 regions will fix a non-contiguous region problem, then they must be given priority?) 5) Combine those 2 regions into a combined region 6) Goto 4) unless all regions have been combined in this round 7) If there are more than N regions remaining, then advance to next round and goto 4) Notes on the combination rules: a) they are contiguous This is obvious b) they haven't been combined already in this round Since M is a power of 2, by pairing off all the blocks in each round, after a log2(M) rounds there will be N regions. c) If they split the map into 2 parts, all resulting pieces must still have an even number of regions This is to prevent regions ending up locked out and unpairable. For example, if the regions formed a line ABCDEFGH and BC was combined, then A would be isolated. A--DEFGH Thus it can't be combined. This means that the only valid combinations in the example are AB, CD, EF, GH. Also, it is important that connected refers to connections that occur inside the State boundary. The regions near the edges of the State will extend to infinity, but connections outside the state don't count. d) they have the best measure of some kind This should try to combine regions of dense population. For example, - the perimeter when combined (lower better) - the distance between their centres of population (lower better) - area (low better) - Area/(perimeter^2) (high better) Note on step 1) I think a fast version of splitline should be sufficient here. For example, you could alternate between N-S and E-W lines. Once M*N boxes are created, you could take the centre of population of each box as one of the points. Each step would only require a median search. There would be no requirement to figure out the intercept point between the lines and the State boundary. Also, population balance isn't critical here (though can probably achieved). Election-Methods mailing list - see http://electorama.com/em for list info Election-Methods mailing list - see http://electorama.com/em for list info
[EM] Multipile Transferable Votes
In a message about STV that appeared in Election-Methods Digest on 29-Aug-2009, I said the following: 1 vote [per ballot] is a special case. And, unfortunately, mentioning only that special case gives opponents of transferable-vote systems a politically effective counter-argument. Instead, what people favoring transferable-vote elections should say is that (1) every valid ballot will cast the same number of votes, and (2) the same outcome will emerge regardless of how many votes each valid ballot casts, whether that number is (a) 1 (which simplifies calculation), (b) the number of open seats (which might be, say, 3), or even (c) merely a letter, say, v. Two people posted comments. One wrote, This statement is wrong . In STV-PR each voter has one vote and one vote only throughout the entire process. It is extremely important to refer to STV as the SINGLE Transferable Vote, because each voter must have only one vote to ensure PR. PR cannot be obtained (except by chance) if that single vote is not transferable . The other comment was, Ahh I see what you are aiming for. Effectively, each voter gets to submit v ranked ballots. This could make counting pretty hard. Both writers missed the point. On the other hand, our leading election theorist, that is, Nicolaus Tideman, understood. He saw that, as I had asserted, changing the number of votes cast by each ballot in a transferable-vote election might not affect the outcome of the election. And, remarkably, he tested and illustrated my assertion. To do so, Professor Tideman referred to a file he had containing 460 rankings actually submitted in a ranked-voting election with 4 winners and 10 candidates. He selected three different numbers of votes that each ballot might have cast in that election, namely, 1 (the number actually cast per ballot), 2, and 4 (the number of seats being filled). For each of these three possibilities, he determined which candidates would have won the election. Professor Tideman used three different versions of STV. He used the two most-sophisticated versions currently available, namely, Meek's method and Warren's method, and also the Newland-Britton method. The latter is much advanced over early versions of STV (for example, over the primitive version still used in Massachusetts) but, like them, does not transfer a vote from a candidate being eliminated to the voter's next choice if that next choice was elected earlier in the calculations (as a result, that voter's following choice receives a larger transfer directly instead of a smaller transfer indirectly). Professor Tideman recently sent me his results, along with a copy of voters' rankings. Appendix 1, below, reproduces the calculations with Meek's method, and the results with Warren and Newland-Britton are available on request. To understand the calculations, you need to notice which variables changed and which variables did not change when the number of votes cast by each ballot changed. With each of the three versions of STV, three variables changed as the number of votes per ballot changed from 1 to 2 to 4. The variables that changed were the values at each stage of (a) the quota (that is, the number of votes that a candidate currently needs to be elected), (b) the candidates' tallies (that is, the number of votes that, after transfers of votes that occurred at previous stages, each candidate currently has), and (c) the excess (that is, the number of votes that, because some ballots have incomplete rankings, cannot be transferred from elected or eliminated candidates to active candidates). When the number of votes cast by each ballot changed, each of those three variables changed in proportion. Specifically, when each ballot cast 2 votes, the quota, the tallies, and the excess at every stage were 2 times the level they had when each ballot cast 1 vote. Similarly, when each ballot cast 4 votes, the values at every stage were 4 times the level that those variables had when each ballot cast 1 vote. To see the re-scaling, compare three columns in Appendix 1, namely, (a) the third column from the left (that is, the column with the heading 1), which contains the quota, tallies, and excess that emerged at each stage when each ballot cast one vote, (b) the fourth column from the left (that is, the column headed 2), which contains the quota, tallies, and excess that emerged at each stage when each ballot cast 2 votes, and (c) the fifth column from the left (that is, the column headed 4), which contains the quota, tallies, and excess that emerged at each stage when each ballot cast 4 votes. Equally important is what did NOT change as the number of votes cast by each ballot changed from 1 to 2 to 4. There was no change at any stage in the retention proportion of any candidate. (If a candidate's current tally exceeds the current quota, a
Re: [EM] Dectecting Clone Sets
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. 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. 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
Re: [EM] strategy-free Condorcet method after all!
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 On Nov 17, 2009, at 8:53 PM, fsimm...@pcc.edu wrote: Here's a way to incorporate this idea for large groups: Ballots are ordinal with approval cutoffs. After the ballots are counted, list the candidates in order of approval. Use just enough randomly chosen ballots to determine the Lull winner with 90% confidence: let L(0) be the candidate with least approval. Then for i = 0, 1, 2, ... move L(i) up the list until some candidate L(i+1) beats L(i) majority pairwise (in the random sample). If the majority is so close that the required confidence is not attained, then increase the sample size, etc. Then with the entire ballots set, apply Jobst's Reverse Lull method: Start with candidate A at the top of the approval list. If a majority of the ballots rank A above the Lull winner (i.e. the presumed winner if A is not elected) then elect A. Otherwise, go down the list one candidate to candidate B. Let L be the top Lull winner with approval less than B. If a majority of ballots rank B above L, then elect B, else continue down the list in the same way. In each case the comparison is of a candidate C with the L(i) with the most approval less than C's approval. If the decisions are all made in the same direction as in the sample, then the Reverse Lull winner is the same as the Lull winner, but occasionally (about ten percent of the time) there will be a surprise. If a voter knew that her ballot was going to be used in the forward Lull sample, she would be tempted to vote strategically. But in a large election, most voters would not be in the sample, so there would be little point in them voting strategically. If sincerity had any positive utility at all, it would be enough to result in sincere rankings (in a large enough election). Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Proportional Representation from Ratings Ballots
On Nov 5, 2009, at 12:37 PM, Raph Frank wrote: Party A (65 voters): A1: 0.7 A2: 0.7 B: 0 Party B (35 voters) A1: 0 A2: 0 B: 1 Round 1 A1: 45.5 A2: 45.5 B: 35 All 3 have exceeded the quota. A1 or A2 will be elected and that will cause the 2nd unelected member of that party to increase his vote since they exceeded the quota. Thus after round 2, both A1 parties will be elected. 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. Warren Smith pointed out some pathological cases like: what if everyone voted (1,0,0,0,0) or (0,1,1,1,1), but I just can't get worked up over how if everyone voted weirdly they might get a weird answer. I'm working up a set of election space diagrams for STV, IRNRP and an artificial method that maximizes happiness where every voter gets a maximum of 1 unit of happiness (no point in giving any one voter too many of their favorite choices). What I want out of a PR election method: 1. Evaluate the whole ballot at once (not just first place vote like IRV/STV). This tends to find better solutions. 2. No wasted vote. Choices that don't win (disqualified in intermediate rounds) don't detract from a voter's ability to elect the best choice they can. Voting for a very popular choice leaves you some vote left for less preferred choices. (STV with Meek redistribution does this OK) 3. Poportionality. Colloquially: An N% constituency should get about N % of the seats. 4. Utility. Maximize the sum happiness of the population. 5. Fairness. No one or no group should be unnecessarily shut out. 6. Strategy resistance. For any voter or bloc of voters, honest voting maximizes expected utility. Brian Olson http://bolson.org/ Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] strategy-free Condorcet method after all!
On Nov 18, 2009, at 6:25 PM, Dave Ketchum wrote: BUT, in our newer studying, we know that there is sometimes a cycle, and NO CW. there certainly *can* be a cycle. since Condorcet is not yet used in governmental elections there is no track record there to say sometimes. have there been cases in organization elections (like Wikipedia and those listed in http://en.wikipedia.org/wiki/ Schulze_method#Use_of_the_Schulze_method ) that evidently use a Condorcet method. are there historical cases where there were cycles with any of those organizations? or is it only the hypothesizing of election method scholars and commentators? sure, we can create pathological cases where there is a cycle, but does it really happen? i'm not saying it can't be expected to; when i voted for IRV for Burlington VT in 2005, i thought to myself that it would not likely ever elect a non-CW when a CW exists because we know that if the CW would have to be eliminated before the final IRV round. that didn't happen in 2006, but that is exactly what happened in Burlington in 2009. so pathologies can happen even if we might guess they happen rarely. but are there actual elections in some organizations where there was 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. the outcome of resolving a Condorcet paradox should never depend on the chronological order that pairs are considered. if the method does involving starting with a particular pair and proceeding to another pair (like Tideman would), it should come up with the same result, no matter which pair you happen to consider first. and if a CW exists, the method should always pick the CW. -- r b-j r...@audioimagination.com Imagination is more important than knowledge. On Nov 17, 2009, at 8:53 PM, fsimm...@pcc.edu wrote: Here's a way to incorporate this idea for large groups: Ballots are ordinal with approval cutoffs. After the ballots are counted, list the candidates in order of approval. Use just enough randomly chosen ballots to determine the Lull winner with 90% confidence: let L(0) be the candidate with least approval. Then for i = 0, 1, 2, ... move L(i) up the list until some candidate L(i+1) beats L (i) majority pairwise (in the random sample). If the majority is so close that the required confidence is not attained, then increase the sample size, etc. Then with the entire ballots set, apply Jobst's Reverse Lull method: Start with candidate A at the top of the approval list. If a majority of the ballots rank A above the Lull winner (i.e. the presumed winner if A is not elected) then elect A. Otherwise, go down the list one candidate to candidate B. Let L be the top Lull winner with approval less than B. If a majority of ballots rank B above L, then elect B, else continue down the list in the same way. In each case the comparison is of a candidate C with the L(i) with the most approval less than C's approval. If the decisions are all made in the same direction as in the sample, then the Reverse Lull winner is the same as the Lull winner, but occasionally (about ten percent of the time) there will be a surprise. If a voter knew that her ballot was going to be used in the forward Lull sample, she would be tempted to vote strategically. But in a large election, most voters would not be in the sample, so there would be little point in them voting strategically. If sincerity had any positive utility at all, it would be enough to result in sincere rankings (in a large enough election). Election-Methods mailing list - see http://electorama.com/em for list info
