Re: [EM] Uncovered set methods (Re: How close can we get to the IIAC)
Hi again Markus, it's different. The goldfish winner can be really strange. If the defeat strength are A B C D A - 2 3 0 B 0 - 1 4 C 0 0 - 5 D 6 0 0 - then Beatpath and Tideman give B, River gives C, and Goldfish gives D since the table evolves like this: B C D B - 1 0 C 0 - 0 D 2 3 - B D B - 0 D 2 - D D - Yours, Jobst Am 31.10.2010 18:35, schrieb Jobst Heitzig: Hi Markus, on 29.04.2010 20:33 you asked: is Jobst Heitzig's river method identical to Blake Cretney's goldfish method? I'm sorry that I have not read any list posts for months, so this caught my attention just now. I will check the differences! You probably refer to the method from Blake's Aug 12, 1998 post I cite below? Yours, Jobst On Aug 12, 1998, Blake Cretney wrote: Here's my entry for single-winner system of the week. It was motivated by my desire to make a method that would be easy to program. To this end, it does not require cycles or the Smith set to be found. I'll call it Goldfish until someone shows me a previous mention under a different name. The idea of goldfish is that the candidates seem to eat each other, becoming bigger and bigger, until only one is left swimming in the electoral fish bowl. Goldfish definition: Successively find the worst defeat and eliminate the pair-wise loser. Any win achieved by the pair-wise loser is now scored as if it was achieved by the pair-wise winner, provided it is larger than the one already scored by him, or he is currently scored a loss. Start by making a victory table. For each row, enter the votes against each column's candidate, if the row's candidate wins pair-wise. Otherwise enter a 0. The best way to resolve ties is for a chairman, president, or random voter to enter a special ballot. This ballot must not be truncated. Repeat until only one candidate is left: FIND: Find the highest value in the table. Call this cell i,j. If more than one row share this value, choose the row that is higher in the special ballot. MERGE: Here's where the big fish eats the little one. For each cell in the i row, if there is a higher value for that column in the j row, copy it over. For each cell in the i column, if there is a zero for that row in the j column, copy it over. Do not change the empty cells on the diagonal. ELIMINATE: Remove the j candidate and its row and column from consideration. I'm going to use the word beats to mean defeats pair-wise and eats to mean is chosen to defeat and merge with. MIIAC -- Candidates outside the Smith set are always beaten by members of the Smith set. When they eat them, the rows and columns are merged, but this provides nothing of use for beating other Smith members, because candidates outside the Smith set only have losing scores against those inside, and the merge rule does not copy losing scores. This is because only 0 values are copied from column to column. GITC -- If someone outside a clone set eats a clone, all the clones will be eaten on successive rounds, just as if there was only one. If a clone eats someone outside, the merge occurs. Because the outsider loses to the clone, it can provide no help in defeating other clones. It does not matter which clone eats an outsider, because eventually all clones will be eliminated, or one will eat all the others, and merge with them. GMC -- Because candidates are removed in order of votes against, and because removal does not eliminate a majority vote against a candidate, but merely copies it, candidates with a majority against will be removed first. Elimination methods frequently have the problem that it is possible to help elect a candidate by ranking it lower. This happens when you can reduce the amount by which a victory is obtained, so that a candidate is not eliminated, and can carry on to defeat your enemies. The merge step in Goldfish makes this strategy unnecessary. The winner ends up beating the same candidates as the loser, and by as much. Lower losing values are not copied, but having another candidate in the race with lower losing values is not helpful. This seems like a pretty good system and is fairly easy to program. With a couple of tweaks, it can be converted to Tideman. 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] Uncovered set methods (Re: How close can we get to the IIAC)
Hi Markus, on 29.04.2010 20:33 you asked: is Jobst Heitzig's river method identical to Blake Cretney's goldfish method? I'm sorry that I have not read any list posts for months, so this caught my attention just now. I will check the differences! You probably refer to the method from Blake's Aug 12, 1998 post I cite below? Yours, Jobst On Aug 12, 1998, Blake Cretney wrote: Here's my entry for single-winner system of the week. It was motivated by my desire to make a method that would be easy to program. To this end, it does not require cycles or the Smith set to be found. I'll call it Goldfish until someone shows me a previous mention under a different name. The idea of goldfish is that the candidates seem to eat each other, becoming bigger and bigger, until only one is left swimming in the electoral fish bowl. Goldfish definition: Successively find the worst defeat and eliminate the pair-wise loser. Any win achieved by the pair-wise loser is now scored as if it was achieved by the pair-wise winner, provided it is larger than the one already scored by him, or he is currently scored a loss. Start by making a victory table. For each row, enter the votes against each column's candidate, if the row's candidate wins pair-wise. Otherwise enter a 0. The best way to resolve ties is for a chairman, president, or random voter to enter a special ballot. This ballot must not be truncated. Repeat until only one candidate is left: FIND: Find the highest value in the table. Call this cell i,j. If more than one row share this value, choose the row that is higher in the special ballot. MERGE: Here's where the big fish eats the little one. For each cell in the i row, if there is a higher value for that column in the j row, copy it over. For each cell in the i column, if there is a zero for that row in the j column, copy it over. Do not change the empty cells on the diagonal. ELIMINATE: Remove the j candidate and its row and column from consideration. I'm going to use the word beats to mean defeats pair-wise and eats to mean is chosen to defeat and merge with. MIIAC -- Candidates outside the Smith set are always beaten by members of the Smith set. When they eat them, the rows and columns are merged, but this provides nothing of use for beating other Smith members, because candidates outside the Smith set only have losing scores against those inside, and the merge rule does not copy losing scores. This is because only 0 values are copied from column to column. GITC -- If someone outside a clone set eats a clone, all the clones will be eaten on successive rounds, just as if there was only one. If a clone eats someone outside, the merge occurs. Because the outsider loses to the clone, it can provide no help in defeating other clones. It does not matter which clone eats an outsider, because eventually all clones will be eliminated, or one will eat all the others, and merge with them. GMC -- Because candidates are removed in order of votes against, and because removal does not eliminate a majority vote against a candidate, but merely copies it, candidates with a majority against will be removed first. Elimination methods frequently have the problem that it is possible to help elect a candidate by ranking it lower. This happens when you can reduce the amount by which a victory is obtained, so that a candidate is not eliminated, and can carry on to defeat your enemies. The merge step in Goldfish makes this strategy unnecessary. The winner ends up beating the same candidates as the loser, and by as much. Lower losing values are not copied, but having another candidate in the race with lower losing values is not helpful. This seems like a pretty good system and is fairly easy to program. With a couple of tweaks, it can be converted to Tideman. Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Uncovered set methods (Re: How close can we get to the IIAC)
Hallo, is Jobst Heitzig's river method identical to Blake Cretney's goldfish method? Markus Schulze Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Uncovered set methods (Re: How close can we get to the IIAC)
fsimm...@pcc.edu wrote: By the way, (contrary to Marcus' confusion) UncAAO does satisfy Monotonicity, Clone Independence, IDPA, and Independence from Non-Smith Alternatives, as well as the following: 1. It elects the same member of a clone set as the method would when restricted to the clone set. 2. If a candidate that beats the winner is removed, the winner is unchanged. 3. If an added candidate covers the winner, the new candidate becomes the new winner. 4. If the old winner covers an added candidate, the old winner still wins. 5. It always chooses from the uncovered set. 6. It is easy to describe: Initialize L to be an empty list. While there exists some alternative that covers every member of L, add to L the one (from among those) ranked on the greatest number of ballots. Elect the last candidate added to L. What other deterministic method (based on ranked ballots with truncations allowed) satisfies all of these criteria? River is the only (other) method I know of that meets Monotonicity, clone independence, IPDA, and independence from non-Smith alternatives. It's simple (affirm defeats that do not create a cycle or a branching), but as for whether it meets the other criteria, I do not know. River also satisfies something Jobst called independence of strongly dominated alternatives, which is stronger than IPDA. It's defined here: http://lists.electorama.com/pipermail/election-methods-electorama.com/2004-October/014018.html Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Uncovered set methods (Re: How close can we get to the IIAC)
- Original Message - From: Kristofer Munsterhjelm ... That's UncAAO, right? I've considered adding it to my simulator, but I'm unsure of where the simulated voters should put the approval cutoff. Yes. I'm glad someone remembers UncAAO. I suggest using truncation as the approval cutoff, and using the same truncations that you do for Schulze wv. By the way, (contrary to Marcus' confusion) UncAAO does satisfy Monotonicity, Clone Independence, IDPA, and Independence from Non-Smith Alternatives, as well as the following: 1. It elects the same member of a clone set as the method would when restricted to the clone set. 2. If a candidate that beats the winner is removed, the winner is unchanged. 3. If an added candidate covers the winner, the new candidate becomes the new winner. 4. If the old winner covers an added candidate, the old winner still wins. 5. It always chooses from the uncovered set. 6. It is easy to describe: Initialize L to be an empty list. While there exists some alternative that covers every member of L, add to L the one (from among those) ranked on the greatest number of ballots. Elect the last candidate added to L. What other deterministic method (based on ranked ballots with truncations allowed) satisfies all of these criteria? Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Uncovered set methods (Re: How close can we get to the IIAC)
Dear Forest, you wrote (20 April 2010): 1. It elects the same member of a clone set as the method would when restricted to the clone set. Well, how do you define clones? In the approval voting paradigm, the term clones implies that all candidates have the same approval score. So when you apply UncAAO to a clone set, then all candidates of its uncovered set are tied. Markus Schulze Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Uncovered set methods (Re: How close can we get to the IIAC)
Markus wrote ... '..how do you define clones? In the approval voting paradigm, the term clones implies that all candidates have the same approval score. So when you apply UncAAO to a clone set, then all candidates of its uncovered set are tied.' Your suggested interpretation of clones (always being tied in approval) would satisfy my claim, breaking ties with random ballot, for example. But that's not what I had in mind. Here's what I had in mind: Since Approval and Cardinal Ratings are strategically equivalent, if the standard high resolution Cardinal Ratings methods satisfy clone independence, then at a strategic level, so must Approval. Beyond that consideration, in the context of many voters we can assume that each candidate's average approval will be approximately equal to each candidate's average cardinal rating even with non-strategic voting. For similar reasons (except in rare borderline cases) it doesn't matter (to their grade) if I give my students partial credit or not when grading hundreds of problems over a term. (It does matter psychologically to the students.) It may be that X, Y, and Z are always ranked solid on the cardinal ratings ballots of some election, but unless they are usually rated near each other, and frequently approved or disapproved together in strategic voting, we would have to judge the clone relationship to be quite loose. In other words, we could call them pseudo-clones. It takes Cardinal Ratings or Approval to distinguish pseudo-clones from true clones. Visually compare in one dimension original: A*C*B** Tight clone set {X, Y, Z} replaces C: AX**Y**ZB*** Loose clone set: *A*X*YZ***B** Since rankings do not distinguish between pseudo and true clones, MinMax Condorcet based on rankings fails clone dependence. But if we base MinMax on ratings ballots (or ranked ballots with approval information) and use James Green-Armytage's weighted pairwise (whether CWP or AWP) measure of strength of defeat, the method acquires clone independence. And because of its simplicity, together with the other advantages of using weighted pairwise measures of strength (see James' discussion at http://fc.antioch.edu/~james_green-armytage/vm/antistratsum.htm), MinMax(CWP or AWP) is an obvious public proposal. In summary the stronger the clone relationship, the stronger the tendency to approve or disapprove all of the members of the clone family together. The looser the relationship, the greater the number of ballots that split them up in approval/disapproval. So they are more or less split up in the approval totals depending on how strong or weak the clone relationship. Forest Election-Methods mailing list - see http://electorama.com/em for list info
[EM] Uncovered set methods (Re: How close can we get to the IIAC)
fsimm...@pcc.edu wrote: Here's a method I proposed a while back that is monotone, clone free, always elects a candidate from the uncovered set, and is independent from candidates that beat the winner, i.e. if a candidate that pairwise beats the winner is removed, the winner still wins: 1. List the candidates in order of decreasing approval. 2. If the approval winner A is uncovered, then A wins. 3. Otherwise, let C1 be the first candidate is the list that covers A. If C1 is uncovered, then C1 wins. 4. Else let C2 be the first candidate in the list that covers C1. If C2 is uncovered, then C2 wins. etc. There are variations on this method that preserve all of the mentioned properties, including methods that do not require approval information, but I think it is nicer to take into account approval information. If this is done via an approval cutoff on ranked ballots, the approval cutoff, AC, itself can be considered a candidate with 50% approval. No candidate with less than 50% approval can cover the AC, and the AC beats pairwise every candidate with less than 50% approval, so no candidate at all can cover the AC unless it pairwise beats all of the candidates with less than 50% approval. What do we do if AC wins the election? If we want a deterministic answer, I suggest that we elect the candidate C that has the least pairwise opposition from the AC. That's UncAAO, right? I've considered adding it to my simulator, but I'm unsure of where the simulated voters should put the approval cutoff. Should they do so based on frontrunner plus strategy, on an objective internal condition (above mean utility or similar), or on a contingent condition (better than what we have already)? I'm not sure. Perhaps one could use AC as a none-of-the-above. As it is, it seems a bit too strong for that, but if it could be modified to work as NOTA, then the simple answer for AC wins is redo the election with other candidates. It would make sense if people put the cutoff at the value of just proceeding as usual (with no change of the office in question). I've also been wondering if my variant of second order Copeland always elects an uncovered candidate. The method goes: first run a sports type of Copeland, where a win is worth 2 points, a tie 1, and a loss zero. Then each candidate gets two times the sum of points of the candidates he beats, plus the sum of points of the candidates he ties. Greatest score wins. I think this would be the case if the initial points allocation had the property that Smith set members have a greater score than non-Smith members, but the 2/1/0 Copeland set (those who win in Copeland with 2 pts for win and 1 for tie) is a subset of the Smith set, not the entire Smith set, which might complicate matters. Election-Methods mailing list - see http://electorama.com/em for list info