[EM] information content, game theory, cooperation
Hi! I am sorry for igniting such a flamewar. 1. information content I propose that this topic should be discussed only after understanding Shannon's information theory. A good introductory material is on Wikipedia: http://en.wikipedia.org/wiki/Information_entropy If we consider all variations of votes equally possible, we end up that for n candidates - approval voting have 2^n possibilities (hence log2(2^n)=n bits) - preferential voting have n! possibilities (hence log2(n!) bits) (not counting the cases wherre not all candidates are ranked) I have made a mistake stating that it is clear that prefeerential voting have more information. It is true only for n=4. Fortunately I am too young, didn't vote in communist times, so I have only encountered situations where n=4. So now I consider that while my statement wasn't correct mathematically, it is true in real life situations. Now you can discuss how information content is different in real life because all votes not being equally possible, but please do not challenge well established theoretical facts. 2. game theory The discussion about how Nash equilibrium is reached with different voting methods had been very enlightening to me. It shown how to tackle my country's current situation from a mathematical standpoint. Maybe assumption about full information, no cooperation or logical voters should be changed, and changes of opinion of voters between election should be accounted for to have a better model. But there is the brief explanation of how I could understand the situation: We have a voting system which is converging fast, and the convergence point (I do not use notion of Nash equilibrium here) is far from the least unacceptable situation considering voters' preferences. 3. cooperation Since I have asked, I have found the answer to my question: what is the distinctive feature of Schulze? (The page has been on rangevoting.org, but I cannot find it now.) Shulze prefers the candidate which beatpath is weak (as far I can remember Schulze's description). Which means something like it is the least unacceptable candidate. I have the feeling that this is connected with cooperativeness of the candidate. Formal description or refusal of this effect is welcome. Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] information content, game theory, cooperation
Hi, --- En date de : Dim 7.6.09, Árpád Magosányi mag...@rabic.org a écrit : Shulze prefers the candidate which beatpath is weak (as far I can remember Schulze's description). Which means something like it is the least unacceptable candidate. I have the feeling that this is connected with cooperativeness of the candidate. Formal description or refusal of this effect is welcome. Schulze is a Condorcet method, so that it wants to elect the candidate who could defeat any other candidate head-to-head. When such a candidate doesn't exist, then Schulze wants to find the candidate whose worst loss is the least. (The idea is to reduce the number of voters who have good reason to object to the outcome.) But simply doing this would violate clone independence. So beatpaths are used to ensure that a candidate doesn't lose simply due to being a clone. That's not very formal but it's how I would explain it. Kevin Venzke Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] information content, game theory, cooperation
Dear Árpád Magosányi, here are the proposed statutory rules for the Schulze method: http://m-schulze.webhop.net/propstat.pdf If I understand you correctly, then you want to define the Schulze method in an axiomatic manner in your proposal. I don't think that this is a good idea. Markus Schulze Election-Methods mailing list - see http://electorama.com/em for list info
[EM] Schulze definition (was: information content, game theory, cooperation)
Hi! Sorry for top posting, But I believe I have found something nearing a suitable simple-word definition for Schulze. As this is what I desperately need, I offer it for scrutiny here: - The electors rank the candidates according to their preferences. - If there is a group of candidates all preferred over all candidates outside the group, then ignoring the candidates outside the group should not change the outcome of the election. - The winner should be choosen from the above group in a way that guarantees that if a candidate similar to an already running candidate is introduced, the outcome of the election is not changed, and the less controversial candidates are preferred. Reasoning below. Please point out possible mistakes and ways to better phrase it between the boundary conditions given (simple words, no expert terms like Schulze or beatpath, and should be matchable to correct mathematical definitions. 2009/6/7 Markus Schulze markus.schu...@alumni.tu-berlin.de Dear Árpád Magosányi, here are the proposed statutory rules for the Schulze method: http://m-schulze.webhop.net/propstat.pdf If I understand you correctly, then you want to define the Schulze method in an axiomatic manner in your proposal. I don't think that this is a good idea. I'm afraid you haven't yet understood the Hungarian situation ([?]). There is no hope to push real changes through the Parliament. The only way to achieve any democratic change is referendum. The rules for the questions eligible for referendum are very strict. Nothing remotely as complex as your statutory proposal would go through. Of course when time comes for changing the text of law, we will push this text. What I need is a small set of simply worded criteria, and to be able to show that these criteria are not just wishes with a broad meaning, but can be matched with exact mathematical definitions. BTW it would be nice if the wikipedia page would actually contain something describing Schulze method, not just the heuristics. The best I have found so far is: http://rangevoting.org/SchulzeExplan.html Therefore, my aim was to find a method that satisfies Condorcet, monotonicity, clone-immunity, majority for solid coalitions, and reversal symmetry, *and* that tends to produce winners with weak worst pairwise defeats (compared to the worst pairwise defeat of the winner of Tideman's Ranked Pairs method). Sorry for thinking loudly, this boils down to: -Condorcet and majority for solid coalitions can be described with ISDA whenever you can partition the candidates into group *A* and group *B* such that each candidate in group *A* is preferred over each candidate in group * B*, you can eliminate all candidates of group *B* without changing the outcome of the election. -Monotonicity *A candidate* x *should not be harmed* [i.e., change from being a winner to a loser] *if* x *is raised on some ballots without changing the orders of the other candidates. -*Clone immunity the addition of a candidate identical to one already present in an election will not cause the winner of the election to change. - reversal symmetry If a candidate A is the unique winner, and the individual preferences of each voter are inverted, then candidate A must not be elected. - tends to produce winners with weak worst pairwise defeats prefers candidates who are cooperative Now there are 3 methods I know of ( http://en.wikipedia.org/wiki/Schulze_method#Comparison_with_other_preferential_single-winner_election_methods) complying with ISDA. Of them only Schulze tends to produce winners with weak worst pairwise defeats. But this does not imply clone independency, and it is overly important, so we should add this as well. So my definition is the above. 4F4.gif Election-Methods mailing list - see http://electorama.com/em for list info
[EM] information content of ballots (and intelligent people)
I understand quite well Warren's point that for 2 and 3-candidate races, and with full ranking required, and equal ranking not allowed, then Approval (with the silly votes excluded) and ranked ballots can be encoded in the same number of bits. And yes, there is certainly an algorithm for turning a binary number like 100 back into a ranking. Or for turning an 8-bit number into 3 Approval or 3 ranked ballots. In his most recent post to EM, Paul wrote: If ranked ballots provide more information than approval ballots is a MYTH, then Mr. Smith should be able to decide from {B C} {A} which of {C B} is preferred by the approval voter over the other. In other words, Paul is saying that the ranked ballot BCA contains some information (namely BC) that is not contained in the Approval ballot {B,C} are approved. I think the answer to this seeming paradox is that the ranked and Approval ballots contain the same amount but _different kinds_ of information. In fact the Approval ballot contains information that can not be determined from the ranked ballot: in the above example, can you tell from the ranked ballot whether C would be approved by the voter? (Approved meaning the voter considers C to be better than the outcome expected if A and B were the only candidates.) To state it more simply: does the voter like C a lot or not much at all, compared to the likely winners? You can't tell from the ranked ballot. The Approval ballot at least gives you a hint. Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Schulze definition (was: information content, game theory, cooperation)
On Sun, Jun 7, 2009 at 7:35 PM, Árpád Magosányi mag...@rabic.org wrote: - The electors rank the candidates according to their preferences. - If there is a group of candidates all preferred over all candidates outside the group, then ignoring the candidates outside the group should not change the outcome of the election. - The winner should be choosen from the above group in a way that guarantees that if a candidate similar to an already running candidate is introduced, the outcome of the election is not changed, and the less controversial candidates are preferred. Reasoning below. Please point out possible mistakes and ways to better phrase it between the boundary conditions given (simple words, no expert terms like Schulze or beatpath, and should be matchable to correct mathematical definitions. Ok, so you are basically saying (in simple terms) A) the method is a ranked method B) All candidates outside the Smith set can be ignored without changing the result C) The method should be clone independent. That is a pretty good idea. You are in effect defining the characteristics that Schulze meets and the others don't. Wikipedia has a table at: http://en.wikipedia.org/wiki/Schulze_method Schulze and ranked pairs are the only methods that meet clone independence and the condorcet rule. Does ranked pairs fail the Smith criterion? I would change B to If there is a group of candidates all preferred over all candidates outside the group, then only those candidates may win and the candidates outside the group may have no effect on the result. If you don't restrict the winner to the Smith set (which your rules don't necessarily), then you could end up with a non-condorcet method. Also, just because the popular/proposed condorcet methods are excluded by your definition doesn't mean that some other weird method can't be found that also meets the rule. It might be better to just include the reasons that you like Sculze and use those rules rather than trying to select Sculze by a process of elimination. BTW it would be nice if the wikipedia page would actually contain something describing Schulze method, not just the heuristics. The best I have found so far is: http://rangevoting.org/SchulzeExplan.html Therefore, my aim was to find a method that satisfies Condorcet, monotonicity, clone-immunity, majority for solid coalitions, and reversal symmetry, *and* that tends to produce winners with weak worst pairwise defeats (compared to the worst pairwise defeat of the winner of Tideman's Ranked Pairs method). Yeah. Though, ofc, Schulze isn't allow to edit the article. Could someone on this list give a brief outline or the formal rule (actually his statutory rules are probably it)? Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Schulze definition (was: information content, game theory, cooperation)
To me all this sounds still a bit too complex for the referendum. I'd drop out all the criteria, Smith set etc. since the voters will not understand. There is also the risk that experts and opponents of the reform will sabotage the referendum by digging into the details (and thereby proving to the voters that the method is too complex). The question in the referendum can not in any case define the complete method. It may be enough to make it clear in the question that the method is a ranked method (the voters may understand even have interest in this point) and that it is a Condorcet method (if you want to rule out e.g. IRV). If the question clearly points out the group of Condorcet methods and it will be approved, then it may be natural to pick the Schulze method since it is anyway the most used Condorcet method. It could be thus enough to say: - The electors rank the candidates according to their preferences. - If some candidate is preferred over all other candidates then that candidate shall be elected. Juho --- On Sun, 7/6/09, Raph Frank raph...@gmail.com wrote: On Sun, Jun 7, 2009 at 7:35 PM, Árpád Magosányi mag...@rabic.org wrote: - The electors rank the candidates according to their preferences. - If there is a group of candidates all preferred over all candidates outside the group, then ignoring the candidates outside the group should not change the outcome of the election. - The winner should be choosen from the above group in a way that guarantees that if a candidate similar to an already running candidate is introduced, the outcome of the election is not changed, and the less controversial candidates are preferred. Reasoning below. Please point out possible mistakes and ways to better phrase it between the boundary conditions given (simple words, no expert terms like Schulze or beatpath, and should be matchable to correct mathematical definitions. Ok, so you are basically saying (in simple terms) A) the method is a ranked method B) All candidates outside the Smith set can be ignored without changing the result C) The method should be clone independent. That is a pretty good idea. You are in effect defining the characteristics that Schulze meets and the others don't. Wikipedia has a table at: http://en.wikipedia.org/wiki/Schulze_method Schulze and ranked pairs are the only methods that meet clone independence and the condorcet rule. Does ranked pairs fail the Smith criterion? I would change B to If there is a group of candidates all preferred over all candidates outside the group, then only those candidates may win and the candidates outside the group may have no effect on the result. If you don't restrict the winner to the Smith set (which your rules don't necessarily), then you could end up with a non-condorcet method. Also, just because the popular/proposed condorcet methods are excluded by your definition doesn't mean that some other weird method can't be found that also meets the rule. It might be better to just include the reasons that you like Sculze and use those rules rather than trying to select Sculze by a process of elimination. BTW it would be nice if the wikipedia page would actually contain something describing Schulze method, not just the heuristics. The best I have found so far is: http://rangevoting.org/SchulzeExplan.html Therefore, my aim was to find a method that satisfies Condorcet, monotonicity, clone-immunity, majority for solid coalitions, and reversal symmetry, and that tends to produce winners with weak worst pairwise defeats (compared to the worst pairwise defeat of the winner of Tideman's Ranked Pairs method). Yeah. Though, ofc, Schulze isn't allow to edit the article. Could someone on this list give a brief outline or the formal rule (actually his statutory rules are probably it)? -Inline Attachment Follows- 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] information content of ballots (and intelligent people)
It matters what is said, not whether speaking in different languages affects whether different information can be contained in the same size statement. Paul is stating, correctly, that reading a ballot that only approves {B C} provides no information as to the voter's desires being BC, B=C, or BC - only preferring them over A. On Jun 7, 2009, at 2:57 PM, Jan Kok wrote: I understand quite well Warren's point that for 2 and 3-candidate races, and with full ranking required, and equal ranking not allowed, then Approval (with the silly votes excluded) and ranked ballots can be encoded in the same number of bits. And yes, there is certainly an algorithm for turning a binary number like 100 back into a ranking. Or for turning an 8-bit number into 3 Approval or 3 ranked ballots. In his most recent post to EM, Paul wrote: If ranked ballots provide more information than approval ballots is a MYTH, then Mr. Smith should be able to decide from {B C} {A} which of {C B} is preferred by the approval voter over the other. In other words, Paul is saying that the ranked ballot BCA contains some information (namely BC) that is not contained in the Approval ballot {B,C} are approved. I think the answer to this seeming paradox is that the ranked and Approval ballots contain the same amount but _different kinds_ of information. In fact the Approval ballot contains information that can not be determined from the ranked ballot: in the above example, can you tell from the ranked ballot whether C would be approved by the voter? (Approved meaning the voter considers C to be better than the outcome expected if A and B were the only candidates.) Paradox? (ignoring Jan's naming error), Paul's approval ballot is approving {B C} as if equally liked, and unable to imitate rank's ability to include relative liking of the two. The approval voter had to omit voting for A to indicate lesser liking for A, while the rank voter could indicate lesser liking for A in the ranking. To state it more simply: does the voter like C a lot or not much at all, compared to the likely winners? You can't tell from the ranked ballot. The Approval ballot at least gives you a hint. Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Schulze definition (was: information content, game theory, cooperation)
On Sun, Jun 7, 2009 at 10:20 PM, Juho Laatujuho4...@yahoo.co.uk wrote: It could be thus enough to say: - The electors rank the candidates according to their preferences. - If some candidate is preferred over all other candidates then that candidate shall be elected. I think that Smith compliance should be required. Condorcet compliance on its own isn't that great. Frankly, even if 1 condorcet method is better than others, going from plurality to any Condorcet/Smith method is a massive improvement. Also, the benefit to the politicians is pretty small from picking a horrible condorcet method, so hopefully they won't bother (though maybe that is overly trusting). If an added criteria is needed, then maybe add clone independence. However, then you are adding more complexity. Do you want the voting method to be one where The voters rank the candidates, and, unranked candidates are considered equal worst, and, a candidate is considered preferred to another if he is preferred by a majority of the voters who express a preference, and, If a candidate is ranked first on a majority of the ballots, then that candidate wins, and, if a candidate is preferred to all other candidates, then that candidate wins, and, If every candidate in a group of candidates is preferred to all candidates outside the group, then one of them wins ? This has some redundant clauses, but adding them actually makes it clearer (I think). In, theory you only need the last one as the other 2 rules automatically follow. Maybe you could submit one that only requires condorcet compliance as the 3 clause is complex. Btw, does Schulze allow equal rankings? Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Schulze definition (was: information con tent, game theory, cooperation)
Dear Raph, Schulze and ranked pairs are the only methods that meet clone independence and the condorcet rule. Nope. River, too, of course, meets all three criteria... Does ranked pairs fail the Smith criterion? I would change B to If there is a group of candidates all preferred over all candidates outside the group, then only those candidates may win and the candidates outside the group may have no effect on the result. If you don't restrict the winner to the Smith set (which your rules don't necessarily), then you could end up with a non-condorcet method. Also, just because the popular/proposed condorcet methods are excluded by your definition doesn't mean that some other weird method can't be found that also meets the rule. It might be better to just include the reasons that you like Sculze and use those rules rather than trying to select Sculze by a process of elimination. BTW it would be nice if the wikipedia page would actually contain something describing Schulze method, not just the heuristics. The best I have found so far is: http://rangevoting.org/SchulzeExplan.html Therefore, my aim was to find a method that satisfies Condorcet, monotonicity, clone-immunity, majority for solid coalitions, and reversal symmetry, and that tends to produce winners with weak worst pairwise defeats (compared to the worst pairwise defeat of the winner of Tideman's Ranked Pairs method). Yeah. Though, ofc, Schulze isn't allow to edit the article. Could someone on this list give a brief outline or the formal rule ( actually his statutory rules are probably it)? 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] Schulze definition (was: information content, game theory, cooperation)
Hallo, here is another short, but complete definition of the Schulze method: http://en.wikipedia.org/wiki/User:MarkusSchulze/Schulze_method_(simple_version) * - tends to produce winners with weak worst pairwise defeats I usually define this desideratum using MinMax scores for sets of candidates: Suppose the MinMax score of a set X of candidates is the strength of the strongest pairwise win of a candidate A outside set X against a candidate B inside set X. Then the winner should always be a candidate of the set with minimum MinMax score. See also section 9 of my paper: http://m-schulze.webhop.net/schulze1.pdf Markus Schulze Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Idiots and information
This is going crazy, but I cannot now resist. On Jun 7, 2009, at 1:45 AM, Paul Kislanko wrote: Let's go back to the original post. Mr Smith called me an idiot for pointing out that his claim that approval ballots contain as much information as ranked ballots or range ballots do. This much should have ended it, but this idiocy goes on and ON! I point out that given a range ballot I can create a ranked ballot, and given a ranked ballot (truncation allowed, equivalent to assigning a zero for a range) I can create the approval equivalent. Slipping a bit. If approval was truly equivalent to ranking one would be able to reconstruct any ranked ballot from an approval ballot that contained all the ranking information - but approval cannot include ranking information other than which candidates were approved. Now, in a 3 alternative ballot with alternatives A, B, and C, I approove B and C. Knowing only that, Mr Smith asserts their is as much information as there would be if I'd ranked the candidates. I ask him publicly to derive from my approval of B and C which one of them I'd prefer, using only the knowledge that I approve both of them. Weak in that Paul has not (and could not have) indicated via approving B and C, which of them he preferred - but Paul is pointing out that, with ranking, he could have indicated a preference. He can't do that, but he calls me an idiot. That ranked ballots provide more informations than approval ballots is not a myth, it is a fact. Mr. Smith can evidently tell from my {B C} {A} what my preference between B and C is. If he can't provide an algorithm for that, his assertion that my explicitly telling him provides no new information is certainly not correct. Does not matter whether information in an approval ballot requires the same length of statement as in a ranking ballot - what matters is that all that can be said via approval can be said via ranking, but ranking can say more. If ranked ballots provide more information than approval ballots is a MYTH, then Mr. Smith should be able to decide from {B C} {A} which of {C B} is preferred by the approval voter over the other. Saying it another way, by approving one or more candidates approval divides them into two groups, but is unable to say anything more about either group. Ranking, of course, approves BC , and can indicate which is most preferred. Dave Ketchum Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Schulze definition (was: information content, game theory, cooperation)
Hallo, here is another paper that confirms the observation, that the Schulze winner is almost always identical to the MinMax winner: http://dukespace.lib.duke.edu/dspace/bitstream/10161/1278/1/Wright_Barry.pdf See pages 67-70. In the 4-candidate case, the Schulze winner and the MinMax winner are identical with a probability of 99.7%. In the 5-candidate case, the Schulze winner and the MinMax winner are identical with a probability of 99.2%. In the 6-candidate case, the Schulze winner and the MinMax winner are identical with a probability of 99.1%. In the 7-candidate case, the Schulze winner and the MinMax winner are identical with a probability of 98.9%. Markus Schulze Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Schulze definition (was: information content, game theory, cooperation)
On Sun, Jun 7, 2009 at 11:52 PM, Juho Laatujuho4...@yahoo.co.uk wrote: My thinking was that if the question on the referendum excludes IRV, then the final outcome is anyway likely to be Schulze (and the unlikely event of choosing some other one of the good Condorcet methods would not be a big problem). But they could pick the bottom 2 runoff version of IRV, if all you want is Condorcet compliance. Some possibilities elect the condorcet winner if 1 exists, or the candidate with the most first choices otherwise. elect the condorcet winner if 1 exists or the candidate chosen by the outgoing PM otherwise. It depends on how evil the legislators are. Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] information content of ballots (and intelligent people)
Dave, --- En date de : Dim 7.6.09, Dave Ketchum da...@clarityconnect.com a écrit : It matters what is said, not whether speaking in different languages affects whether different information can be contained in the same size statement. Paul is stating, correctly, that reading a ballot that only approves {B C} provides no information as to the voter's desires being BC, B=C, or BC - only preferring them over A. That isn't what the argument is about. Nobody disagrees with this part. Kevin Venzke Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Schulze
The Schulze-beatpaths page Arpad was probably thinking of was http://rangevoting.org/SchulzeExplan.html The information thing now is summarized here http://rangevoting.org/PuzzInfo1.html which will be a future puzzle... -- Warren D. Smith http://RangeVoting.org -- add your endorsement (by clicking endorse as 1st step) and math.temple.edu/~wds/homepage/works.html Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Schulze definition (was: information content, game theory, cooperation)
2009/6/7 Raph Frank raph...@gmail.com On Sun, Jun 7, 2009 at 7:35 PM, Árpád Magosányi mag...@rabic.org wrote: - The electors rank the candidates according to their preferences. - If there is a group of candidates all preferred over all candidates outside the group, then ignoring the candidates outside the group should not change the outcome of the election. - The winner should be choosen from the above group in a way that guarantees that if a candidate similar to an already running candidate is introduced, the outcome of the election is not changed, and the less controversial candidates are preferred. Ok, so you are basically saying (in simple terms) A) the method is a ranked method B) All candidates outside the Smith set can be ignored without changing the result C) The method should be clone independent. Not exactly. C/1) The method should be clone independent C/2) The method should prefer weak defeats Actually C/2 is the one where I yet to became confident that there is a one-to-one match between the wording and the exact mathematical definition. [...] Schulze and ranked pairs are the only methods that meet clone independence and the condorcet rule. Does ranked pairs fail the Smith criterion? No. It fails the prefer-weak-defeats criterion only from the above. I would change B to If there is a group of candidates all preferred over all candidates outside the group, then only those candidates may win and the candidates outside the group may have no effect on the result. If you don't restrict the winner to the Smith set (which your rules don't necessarily), then you could end up with a non-condorcet method. B does restrict the winner to the Smith set. If someone outside the Smith set wins, ignoring him would change the election result. Also, just because the popular/proposed condorcet methods are excluded by your definition doesn't mean that some other weird method can't be found that also meets the rule. This is why I have put clone independence back. It might be better to just include the reasons that you like Sculze and use those rules rather than trying to select Sculze by a process of elimination. Actually I end up doing so. I did not include monotonicity because I don't view it as very important, but include cloneproofness because I do. (I am hoping that a nonmonotonic method matching all other criteria should not be very bad in most cases.) Election-Methods mailing list - see http://electorama.com/em for list info