Re: [EM] strategy-free Condorcet method after all!
robert bristow-johnson wrote: robert bristow-johnson wrote: ... i dunno how to, other than take the raw ballot data of some existing IRV elections, but i would like to see how many of these municipal IRV elections, that if the ballots were tabulated according to Condorcet rules, that a cycle would occur. Kristofer Munsterhjelm wrote: ... I haven't run the data through my simulator yet, but it seems cycles are rare. i have to confess that i am less worked up about what pathologies would result from a Condorcet cycle than i am about what pathologies result from FPTP or IRV (or Borda or whoever) failing to elect the Condorcet winner whether such exists. we know the latter actually happens in governmental elections. i still have my doubts to any significant prevalence of the former. That's what the data might provide information about. If it is representative and cycles are rare, then there's little to worry about, except how opponents might exaggerate the faults. If cycles are common, then one should be careful to pick the right cycle-breaker. on the rare occasion a cycle ever happens, probably Tideman Ranked-Pairs would be the best compromise between a fairer Schulze beatpath and some method that has sufficient "lucidity" that voters can understand it and have confidence that no "funny business" is going on. Yes. I think so, too, but Schulze has momentum (within technical organizations, mostly), so the question is which is greater an advantage. but whether it's beatpath or ranked-pairs or IRV rules as the method that resolves a cycle, at least in this very rare occasion, it's picking a non-Condorcet winner meaningfully, even if there are conceptual ways to turn tactical with it. but then, how profitable is it to vote tactically when there is little probability to the conditions that would serve such tactical voting? There would be two kinds, I think: attempted "vote management" by parties and what we might call "ignorant strategy" that the voters do by themselves, and which only distorts the outcome if lots of people do it. The latter is not much of a threat, I think, and the method only has to weather the former for a few elections before the parties see it isn't going to work. In small committees, the two would converge: poison pill type tricks are possible with Condorcet methods, as well, but that's not the application we're speaking of at the moment. if it were one of those Condorcet methods and if there is little likelihood of a cycle happening and if a savvy voter knows that, how does it benefit his/her political interests to do anything other than vote for their fav as their first choice and cover their ass with a tolerable 2nd choice? how are they ever (assuming no cycle) hurting their favorite or helping any unranked candidates (tied for last place, in this voter's esteem) beat the 2nd choice? i really find it hard to see the tactical interests as differing from the sincere political interests. Ignorant strategy could take the form of "I really really hate [major party X], so I'll put him last", where there are also worse candidates in the running, but the voter is used to two-party systems. Burial by accident, as it were. Warren claims that will destroy most Condorcet methods, because DH3 applies to that instance as well, but I'm not so sure. It *does* destroy Borda, but so does agenda manipulating (fielding loads of clones). Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] strategy-free Condorcet method after all!
FPTP: For most elections this can handle the decision needed - though get near a tie and suspicion pushes toward doing a runoff. IRV: Does let voters do ranked voting, but we find plenty of reasons to complain about how it counts the votes. Condorcet: Lets voters do ranked voting for more than one, indicating which they like best. Matters often to let them express their desires more completely when they wish - though they can often adequately express their desires via bullet voting. Matters MUCH, though rarely, to sort out more complex decisions. It is for this ability that we need such as Condorcet. It is for the last topic, where there may be a cycle and no CW, that analyzing votes is more of a challenge. The Llull method will find the CW if it exists. Else it will find a cycle member. Deciding which takes a bit more looking at the N*N array. We debate how to choose a winner, which I claim should only consider cycle members (any cycle member would become CW if other members were rejected). Tactical voting? PROVIDED you know how all others will vote, you may be able to influence results by responding based on what you know. That results can be affected via such makes sense. That you can both have the needed information and modify your vote as you plan is a suspect dream - perhaps someone can do useful analysis as to frequency of attainable useful results for such. Dave Ketchum On Nov 23, 2009, at 5:00 PM, robert bristow-johnson wrote: robert bristow-johnson wrote: ... i dunno how to, other than take the raw ballot data of some existing IRV elections, but i would like to see how many of these municipal IRV elections, that if the ballots were tabulated according to Condorcet rules, that a cycle would occur. Kristofer Munsterhjelm wrote: ... I haven't run the data through my simulator yet, but it seems cycles are rare. i have to confess that i am less worked up about what pathologies would result from a Condorcet cycle than i am about what pathologies result from FPTP or IRV (or Borda or whoever) failing to elect the Condorcet winner whether such exists. we know the latter actually happens in governmental elections. i still have my doubts to any significant prevalence of the former. on the rare occasion a cycle ever happens, probably Tideman Ranked- Pairs would be the best compromise between a fairer Schulze beatpath and some method that has sufficient "lucidity" that voters can understand it and have confidence that no "funny business" is going on. but whether it's beatpath or ranked-pairs or IRV rules as the method that resolves a cycle, at least in this very rare occasion, it's picking a non-Condorcet winner meaningfully, even if there are conceptual ways to turn tactical with it. but then, how profitable is it to vote tactically when there is little probability to the conditions that would serve such tactical voting? if it were one of those Condorcet methods and if there is little likelihood of a cycle happening and if a savvy voter knows that, how does it benefit his/her political interests to do anything other than vote for their fav as their first choice and cover their ass with a tolerable 2nd choice? how are they ever (assuming no cycle) hurting their favorite or helping any unranked candidates (tied for last place, in this voter's esteem) beat the 2nd choice? i really find it hard to see the tactical interests as differing from the sincere political interests. r b-j Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] strategy-free Condorcet method after all!
> robert bristow-johnson wrote: ... >> i dunno how to, other than take the raw ballot data of some existing IRV >> elections, but i would like to see how many of these municipal IRV >> elections, that if the ballots were tabulated according to Condorcet >> rules, that a cycle would occur. Kristofer Munsterhjelm wrote: ... > I haven't run the data through my simulator yet, but it seems cycles are > rare. i have to confess that i am less worked up about what pathologies would result from a Condorcet cycle than i am about what pathologies result from FPTP or IRV (or Borda or whoever) failing to elect the Condorcet winner whether such exists. we know the latter actually happens in governmental elections. i still have my doubts to any significant prevalence of the former. on the rare occasion a cycle ever happens, probably Tideman Ranked-Pairs would be the best compromise between a fairer Schulze beatpath and some method that has sufficient "lucidity" that voters can understand it and have confidence that no "funny business" is going on. but whether it's beatpath or ranked-pairs or IRV rules as the method that resolves a cycle, at least in this very rare occasion, it's picking a non-Condorcet winner meaningfully, even if there are conceptual ways to turn tactical with it. but then, how profitable is it to vote tactically when there is little probability to the conditions that would serve such tactical voting? if it were one of those Condorcet methods and if there is little likelihood of a cycle happening and if a savvy voter knows that, how does it benefit his/her political interests to do anything other than vote for their fav as their first choice and cover their ass with a tolerable 2nd choice? how are they ever (assuming no cycle) hurting their favorite or helping any unranked candidates (tied for last place, in this voter's esteem) beat the 2nd choice? i really find it hard to see the tactical interests as differing from the sincere political interests. r b-j Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] strategy-free Condorcet method after all!
Andrew Myers wrote: I have ballot data from about 1500 elections run using CIVS. But I haven't had the time to write software to package it up nicely. Could you use CIVS itself to quickly determine how many of them had proper Condorcet winners (i.e. Smith set of cardinality one)? That might be an interesting result and wouldn't take as long time as packaging up the data. Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] strategy-free Condorcet method after all!
Kristofer Munsterhjelm wrote: Warren Smith has a copy of Tideman's election archive, as well as some other data, here: http://rangevoting.org/TidemanData.html I haven't run the data through my simulator yet, but it seems cycles are rare. There's also a database of STV elections at http://www.openstv.org/stvdb . While they could be processed by my program (if I write the correct converters), they are multiwinner elections and so the frequency of cycles might not be relevant to what would be the case for when voters are told the election is single-winner. Does anybody know of any data sources apart from the above? I have ballot data from about 1500 elections run using CIVS. But I haven't had the time to write software to package it up nicely. -- Andrew Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] strategy-free Condorcet method after all!
robert bristow-johnson wrote: On Nov 23, 2009, at 1:43 AM, Dave Ketchum wrote: Seems to me that cycles can occur even with sincerity - they relate to conflict among three or more voter views. sure, they "can". but i still question the prevalence of such happening. and with the other methods, particularly the two used in governmental elections: FPTP and IRV, the prevalence of tactical voting (particularly compromising) is clear. why is there so much worry about a pathology that just doesn't seem to occur often enough to be worth it when there seems to be plenty reason to worry about pathologies involved with the non-Condorcet methods? i dunno how to, other than take the raw ballot data of some existing IRV elections, but i would like to see how many of these municipal IRV elections, that if the ballots were tabulated according to Condorcet rules, that a cycle would occur. i know the answer for Burlington 2006 and 2009 (no cycle in either case, the first case the IRV, Condorcet, and FPTP winner was the same person, the second case they were 3 different persons, a clear pathology worth worrying about). what about Cambridge MA or SF, anyone know? Warren Smith has a copy of Tideman's election archive, as well as some other data, here: http://rangevoting.org/TidemanData.html I haven't run the data through my simulator yet, but it seems cycles are rare. There's also a database of STV elections at http://www.openstv.org/stvdb . While they could be processed by my program (if I write the correct converters), they are multiwinner elections and so the frequency of cycles might not be relevant to what would be the case for when voters are told the election is single-winner. Does anybody know of any data sources apart from the above? Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] strategy-free Condorcet method after all!
On Nov 23, 2009, at 1:43 AM, Dave Ketchum wrote: Seems to me that cycles can occur even with sincerity - they relate to conflict among three or more voter views. sure, they "can". but i still question the prevalence of such happening. and with the other methods, particularly the two used in governmental elections: FPTP and IRV, the prevalence of tactical voting (particularly compromising) is clear. why is there so much worry about a pathology that just doesn't seem to occur often enough to be worth it when there seems to be plenty reason to worry about pathologies involved with the non-Condorcet methods? i dunno how to, other than take the raw ballot data of some existing IRV elections, but i would like to see how many of these municipal IRV elections, that if the ballots were tabulated according to Condorcet rules, that a cycle would occur. i know the answer for Burlington 2006 and 2009 (no cycle in either case, the first case the IRV, Condorcet, and FPTP winner was the same person, the second case they were 3 different persons, a clear pathology worth worrying about). what about Cambridge MA or SF, anyone know? -- r b-j r...@audioimagination.com "Imagination is more important than knowledge." Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] strategy-free Condorcet method after all!
Trying to sort this out: Llull never heard of cycles, and did not have enough data to think of others doing more complex methods centuries later. River has the data, and Jobst explains, while describing River, that having defeat data, sorting defeats, and discarding defeats related to cycles, can result in a system competitive with the best other Condorcet methods. When Jobst wrote of "reverse Llull" his big topic was strategy. I do not see the protection that River included mentioned as attended to. Seems to me that cycles can occur even with sincerity - they relate to conflict among three or more voter views. Dave Ketchum On Nov 19, 2009, at 7:55 PM, fsimm...@pcc.edu wrote: 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] 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] 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
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] strategy-free Condorcet method after all!
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] strategy-free Condorcet method after all!
Here's a small group method for making decisions based on Jobst's "Reverse Lull." Randomly decide an ordering of the members of the group. Vote approval style on each of the members in the given order. If no member receives more than fifty percent approval, then the last member in the order makes the decision. Otherwise, the first member to receive more than fifty percent approval makes the decision. If I am not mistaken, this method is clone independent; either cloning the winning alternative nor cloning any losing alternative should make a difference in the choice. Of course the random order can make a difference, but the randomness doesn't detract from the fairness. . Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] strategy-free Condorcet method after all!
One can thwart strategic voting in general by hiding the algorithm that makes the decision who wins. Instead of collecting perfect poll information (that voters are supposed to use accurately when they decide how to vote) one could upgrade the poll answers to actual ranked votes. The randomness / uncertainty could be introduced by determining the rules (in the case of a top level cycle) only after the votes have been collected (e.g. in using the randomization mechanism of the reverse Llull method). If the method is Condorcet compliant voters may try to create a top level cycle if they don't like the expected Condorcet winner (that they guess based on some earlier polls etc.). Artificial cycles however typically include also candidates that are worse than the current winner and the candidate that one tries to promote. If one can not guess which one of the cycle members (or other candidates if that is allowed) will win then the benefits of strategic voting may easily be close to zero. Polls are usually more sincere than actual votes. But actual votes may be one step more sincere if voting is heavily based on the polls but one's actual vote is independent of what one said in the polls. The basic procedure was thus to collect ranked votes first and only after that decide the randomish procedure / algorithm input that is then used to decide which one of the "almost tied leading candidates" wins. Juho On Nov 14, 2009, at 2:32 PM, Jobst Heitzig wrote: Dear folks, it seems there is a stragegy-free Condorcet method after all -- say good-bye to burying, strategic truncation and their relatives! More precisely, I believe that at least in case of complete information (all voters knowing some details about the true preferences of all other voters) and when all voters will follow dominating strategies, then the following astonishingly simple method will always make unanimous sincere voting the unique dominating strategy, and it will always elect a true beats-all winner (=Condorcet winner): Method: Reverse Llull = 1. Sort the options into some arbitrary ordering X1,...,Xn (e.g. alphabetically or randomly), publish this ordering, and put i=n. 2. If already i=1, then X1 is the winner. Otherwise, ask all voters whether they prefer Xi or the option they expect to be the winner of applying this method to the remaining options X1,...,X(i-1). 3. If more voters prefer Xi, Xi is the winner. Otherwise, decrease i by 1 and repeat steps 2 and 3. Why should this be strategy-free? If n=2, the question in step 2 is whether X1 or X2 is preferred and the method is traditional majority choice in which sincere voting is known to be the dominant strategy in case of 2 options. For n>2, we prove strategy-freeness inductively, assuming it has been proved for n-1 options already: Since we assume that each voter follows dominant strategies and knows enough about the other voter's preferences, and since each voters knows that sincere voting is the unique dominant strategy for all cases of at most n-1 options, she will know in step 2 which option Xj would win if the method was applied to X1,...,X(i-1), and she will also know that her vote at this step does not influence which option Xj is but only whether Xi or Xj will win. That is, in step 2 all voters face a simple majority choice between two known options Xi and Xj, so again voting sincerely in this step is the unique dominant strategy. By induction, the whole method is strategy- free. The method is in some sense the reverse of Llull's famous earliest known "Condorcet' method from the 13th century (cited recently on this list): In the classical Llull method, voters would first make a majority decision between X1 and X2, then a majority choice between the winner of the first choice and X3, and so on working thru the whole list of options, always keeping the last winner and comparing it with the next option in the list. The overall winner is the winner of the last comparison. So, the only difference between classical Llull and Reverse Llull is the order in which these pairwise comparisons are done. If we assume all voters vote sincerely in classical Llull, both method would be equivalent. But with strategic voters, the difference is important: In classical Llull, a voter's voting behaviour in one step can influence the results of the later steps (because it can influence which candidate "stays in the ring"), whereas in Reverse Llull it cannot. In practice, the method can be sped-up by using approval-style ballots on which each voter marks after step 1 every option Xi which she prefers to the expected winner of the subset X1,...,X(i-1). As for additional properties, Reverse Llull is Pareto-efficient, Smith-efficient (i.e. elects a member of the Smith set), and monotonic, but not clone-proof. I wonder if we can also find a clone-proof version of this... Any ide
Re: [EM] strategy-free Condorcet method after all!
Think some more re Jobst Heitzig's "Reverse Llull" method, I think "strategy-free" is not the right phrase to describe it. Why? Heitzig's recommended way to vote is totally strategic (!), i.e. heavily dependent on that voter's info about what all the other voters are doing. By that reasoning, any strategic vote in ANY voting method is "honest" provided the voter, when deciding on her strategic vote, is asked (e.g. by her PC) a number of questions about both her preferences and about her perceptions of the other voters, and she answers them all honestly in order to generate the strategic vote! Well, no. But what Heitzig really does accomplish, is: he has a voting method where voters, BY ACTING STRATEGICALLY, will elect the honest-voter Condorcet winner (when one exists). Now with ordinary approval and range voting, it is an already known theorem, see http://rangevoting.org/AppCW.html that voters, BY VOTING STRATEGICALLY, will always elect the honest-voter Condorcet winner (when one exists). It is assumed that they choose their strategic vote in a certain (realistic) manner, and they have enough information about the other voters to do so... in particular, they do not need to have perfect info about the other votes, they merely need to know enough to know who the Condorcet winner C, and who the approval-voting winner would be if it were not C, are. -- 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
[EM] strategy-free Condorcet method after all!
Jobst Heitzig's "Reverse Llull" method was intended to
(1) elect Condorcet winners (under the assumption one exists)
(2) cause strategic and honest voting to be the same thing (at least,
under perfect info assumptions)
It would be better to replace his goal #1 by this better goal
(1') elect the max-summed-utility winner
but unfortunately I cannot see any way to accomplish that.
-
To make it crystal clear that (as I said before, but with less
clarity) the Reverse Llull winner can depend on the candidate
pre-ordering, consider an A>B>C>A Condorcet cycle.
Assume the Heitzig ordering is A,B,C. Clearly with no C, the winner would be A.
So voters will "approve" C (since C>A says a majority) and it will win.
Arguing symmetrically, any one of the three will win, depending on
the Heitzig pre-ordering.
So it appears that with random pre-ordering, every member of a
top-cycle will be equally likely to be the winner with Reverse Llull.
---
I believe it is shown in one of the puzzles on the CRV puzzle page,
that with random votes in the limit of a large number of candidates
and voters, the probability-->1
that EVERY candidate is a member of a top cycle ("pan-cyclicity")
so that with probability-->1 for a "random election" Reverse Llull just becomes
"random winner." This, of course, is very poor in terms of Bayesian Regret
compared with (say) approval voting.
So all in all, despite Reverse Llull's beauty, a case could be made that
plain approval voting is better...
--
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] strategy-free Condorcet method after all!
(Same post as before, but with annoying typos corrected.)
> Jobst Heitzig (with slight editing by me):
>Method: Reverse Llull
>=
>1. Sort the options into some arbitrary ordering X1,...,Xn (e.g.
>alphabetically or randomly), publish this ordering, and put i=n.
WDS: will different orderings yield different results? ("Agenda
manipulation"?)
>2. If already i=1, then X1 is the winner. Otherwise, ask all voters
>whether they prefer Xi or the option they expect to be the winner of
>applying this method to the remaining options X1,...,X(i-1).
WDS: a slight altering in wording would be "or the expected utility of
the winner when applying this method to the remaining options X1,...,X(i-1)."
This change makes no difference under the perfect info assumption that the
voter can predict the winer 100% accurately, but does make a difference if
imperfect info.
>3. If more voters prefer Xi, Xi is the winner. Otherwise, decrease i by
>1 and repeat steps 2 and 3.
>Why should this be strategy-free?
>If n=2, the question in step 2 is whether X1 or X2 is preferred and the
>method is traditional majority choice in which sincere voting is known
>to be the dominant strategy in case of 2 options.
>For n>2, we prove strategy-freeness inductively, assuming it has been
>proved for n-1 options already: Since we assume that each voter follows
>dominant strategies and knows enough about the other voter's
>preferences, and since each voters knows that sincere voting is the
>unique dominant strategy for all cases of at most n-1 options, she will
>know in step 2 which option Xj would win if the method was applied to
>X1,...,X(i-1), and she will also know that her vote at this step does
>not influence which option Xj is but only whether Xi or Xj will win.
>That is, in step 2 all voters face a simple majority choice between two
>known options Xi and Xj, so again voting sincerely in this step is the
>unique dominant strategy. By induction, the whole method is strategy-free.
>The method is in some sense the reverse of Llull's famous earliest known
>"Condorcet' method from the 13th century ...
---
Fascinating. Now I suppose one could argue in the same manner
that the voter can provide all (n-1) of her votes ahead of time, as n-1
binary "bits." Which would actually be n bits if an extra (unused)
vote-bit also
were provided for X1. Note this then is an approval-voting-style ballot.
Now suppose the candidate ordering happens to be
the ordering in decreasing likelihood of victory.
The "moving mean" strategy for approval voting (actually applicable to
a wide class of kinds of voting, which I defined many years ago...)
is precisely the following.
1. order the candidates in decreasing likelihood of victory.
2. approve exactly one of the first two candidates (whichever you prefer).
3. go thru the remaining candidates in order, approving/disapproving
each, if you prefer/not him versus the average utility among
the preceding candidates.
One really should use weighted average weighted by conditional
probability of victory -- though I had in mind unweighted average at
that time, based on the theory that under certain circumstances they
were going to be effectively the same thing. When deciding on the
approval of X[k+1] the probabilities for X1,X2,...,Xk need to be
conditioned on the assumption that X[k+1] is going to have a decent
chance to win, i.e. is near-tied with the leader among X1,X2,...Xk,
while X[k+2],...,Xn are regarded as having negligible winning chances.
If this ordering happens to coincide with the one used by Jobst Heitzig,
then the moving-mean-strategy approval ballot, will coincide with
honest=strategic reverse-Llull voting.
Now the following alternative vote-tallying algorithm will elect Jobst
Heitzig's same winner:
1. go thru the candidates in reverse order (n, n-1, n-2,..., 2, 1)
2. As soon as you find a candidate with more than 50% approval, elect him.
3. If no such candidate exists, elect X1 (but in fact, with Heitzian
"honest" voting, i.e. Smithian moving-mean-strategic voting, one will
always exist, so X1's election would have been automatic without need
for rule 3).
This way of rewording the algorithm seems to make it pretty clear that
the winner CAN depend on the ordering. (Answering my own question
above.) Therefore, this method (if deterministic) disobeys
"neutrality."
A method which, however, is similar and happens to obey "neutrality"
is plain old
APPROVAL VOTING.
Observe that if a Condorcet winner exists, then it automatically is
unique and automatically is elected, both by Reverse Llull, and (with
the same votes) by ordinary approval voting.
They only can differ in circumstances where no Condorcet winner exists.
--
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
[EM] strategy-free Condorcet method after all!
> Jobst Heitzig (with slight editing by me):
>Method: Reverse Llull
>=
>1. Sort the options into some arbitrary ordering X1,...,Xn (e.g.
>alphabetically or randomly), publish this ordering, and put i=n.
WDS: will different orderings yield different results? ("Agenda manipulation"?)
>2. If already i=1, then X1 is the winner. Otherwise, ask all voters
>whether they prefer Xi or the option they expect to be the winner of
>applying this method to the remaining options X1,...,X(i-1).
WDS: a slight altering in wording would be "or the expected utility of
the option they expect to be the winner of
applying this method to the remaining options X1,...,X(i-1)."
This change makes no difference under the perfect info assumption that the
voter can predict the winer 100% accurately, but does make a difference if
imperfect info.
>3. If more voters prefer Xi, Xi is the winner. Otherwise, decrease i by
>1 and repeat steps 2 and 3.
>Why should this be strategy-free?
>If n=2, the question in step 2 is whether X1 or X2 is preferred and the
>method is traditional majority choice in which sincere voting is known
>to be the dominant strategy in case of 2 options.
>For n>2, we prove strategy-freeness inductively, assuming it has been
>proved for n-1 options already: Since we assume that each voter follows
>dominant strategies and knows enough about the other voter's
>preferences, and since each voters knows that sincere voting is the
>unique dominant strategy for all cases of at most n-1 options, she will
>know in step 2 which option Xj would win if the method was applied to
>X1,...,X(i-1), and she will also know that her vote at this step does
>not influence which option Xj is but only whether Xi or Xj will win.
>That is, in step 2 all voters face a simple majority choice between two
>known options Xi and Xj, so again voting sincerely in this step is the
>unique dominant strategy. By induction, the whole method is strategy-free.
>The method is in some sense the reverse of Llull's famous earliest known
>"Condorcet' method from the 13th century ...
---
Fascinating. Now I suppose one could argue in the same manner
that the voter can provide all (n-1) of her votes ahead of time, as n-1 binary
"bits." Which would actually be n bits if an extra (unused) vote-bit also
were provided for X1. Note this then is an approval-voting-style ballot.
Now suppose the candidate ordering happens to be
the ordering in decreasing likelihood of victory.
The "moving mean" strategy for approval voting (actually applicable to
a wide class of kinds of voting, which I defined many years ago...)
is precisely the following.
1. order the candidates in decreasing likelihood of victory.
2. approve exactly one of the first two candidates (whichever you prefer).
3. go thru the remaining candidates in order, approving/disapproving
each, if you prefer/not him versus the average utility among
the preceding candidates.
One really should use weighted average weighted by conditional
probability of victory -- though I had in mind unweighted average at
that time, based on the theory that under certain circumstances they
were going to be effectively the same thing. Wehn deciding on the
approval or X[k+1] the probabilities for X1,X2,...,Xk need to be
conditioned on the assumption that X[k+1] is going to have a decent
chance to win, i.e. is near-tied with the leader among X1,X2,...Xk,
while X[k+2],...,Xn are regarded as having negligible winning chances.
If this ordering happens to coincide with the one used by Jobst Heitzig, then
the moving-mean-strategy approval ballot, will coincide with honest=strategic
reverse-Llull voting.
Now the following alternative vote-tallying algorithm will elect Jobst
Heitzig's same winner:
1. go thru the candidates in reverse order (n, n-1, n-2,..., 2, 1)
2. As soon as you find a candidate with more than 50% approval, elect him.
3. If no such candidate exists, elect X1 (but in fact, with Heitzian
"honest" voting,
i.e. Smithian moving-mean-strategic voting, one will always exist, so
X1's election would have been automatic without need for rule 3).
This way of rewording the algorithm seems to make it pretty clear that
the winner CAN depend on the ordering. (Answering my own question
above.) Therefore, this method (if deterministic) disobeys
"neutrality."
A method which, however, is similar and happens to obey "neutrality"
is plain old
APPROVAL VOTING.
Observe that if a Condorcet winner exists, then it automatically is
unique and automatically
is elected, both by Reverse Llull, and (with the same votes) by
ordinary approval voting.
They only can differ in circumstances where no Condorcet winner exists.
--
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] strategy-free Condorcet method after all!
Very nice construction. The first strategic thought in my mind is to give false poll information since the method relies on that information to be available. Let's see what happens with a simple loop of three. 1: A>B>C 1: B>C>A 1: C>A>B The A supporter is strategic, so the poll results could be as follows. 1: B>A>C or B>C>A 1: B>C>A 1: C>A>B => the falsified strategic preferences indicate B>C>A Depending on the ordering any one of the candidates could be the one that will be checked first. The A supporter will not know which one when giving the poll answer IF the ordering will be decided only just before (the first round of) the election. - A will be checked first => A will be elected (since the C supporter is afraid that B would win A) - B will be checked first => B will be elected (the A supporter votes for B since A would lose to C if B would not be elected) - C will be checked first => C will not be elected (since the B supporter thinks that B will win A) => A will win since A is preferred over B In this example the A supporter was able to improve the results. There could thus be some false information in the polls (or in the discussions between these three voters). Juho P.S. The A supporter could also try C>B>A in the poll. On Nov 14, 2009, at 2:32 PM, Jobst Heitzig wrote: Dear folks, it seems there is a stragegy-free Condorcet method after all -- say good-bye to burying, strategic truncation and their relatives! More precisely, I believe that at least in case of complete information (all voters knowing some details about the true preferences of all other voters) and when all voters will follow dominating strategies, then the following astonishingly simple method will always make unanimous sincere voting the unique dominating strategy, and it will always elect a true beats-all winner (=Condorcet winner): Method: Reverse Llull = 1. Sort the options into some arbitrary ordering X1,...,Xn (e.g. alphabetically or randomly), publish this ordering, and put i=n. 2. If already i=1, then X1 is the winner. Otherwise, ask all voters whether they prefer Xi or the option they expect to be the winner of applying this method to the remaining options X1,...,X(i-1). 3. If more voters prefer Xi, Xi is the winner. Otherwise, decrease i by 1 and repeat steps 2 and 3. Why should this be strategy-free? If n=2, the question in step 2 is whether X1 or X2 is preferred and the method is traditional majority choice in which sincere voting is known to be the dominant strategy in case of 2 options. For n>2, we prove strategy-freeness inductively, assuming it has been proved for n-1 options already: Since we assume that each voter follows dominant strategies and knows enough about the other voter's preferences, and since each voters knows that sincere voting is the unique dominant strategy for all cases of at most n-1 options, she will know in step 2 which option Xj would win if the method was applied to X1,...,X(i-1), and she will also know that her vote at this step does not influence which option Xj is but only whether Xi or Xj will win. That is, in step 2 all voters face a simple majority choice between two known options Xi and Xj, so again voting sincerely in this step is the unique dominant strategy. By induction, the whole method is strategy- free. The method is in some sense the reverse of Llull's famous earliest known "Condorcet' method from the 13th century (cited recently on this list): In the classical Llull method, voters would first make a majority decision between X1 and X2, then a majority choice between the winner of the first choice and X3, and so on working thru the whole list of options, always keeping the last winner and comparing it with the next option in the list. The overall winner is the winner of the last comparison. So, the only difference between classical Llull and Reverse Llull is the order in which these pairwise comparisons are done. If we assume all voters vote sincerely in classical Llull, both method would be equivalent. But with strategic voters, the difference is important: In classical Llull, a voter's voting behaviour in one step can influence the results of the later steps (because it can influence which candidate "stays in the ring"), whereas in Reverse Llull it cannot. In practice, the method can be sped-up by using approval-style ballots on which each voter marks after step 1 every option Xi which she prefers to the expected winner of the subset X1,...,X(i-1). As for additional properties, Reverse Llull is Pareto-efficient, Smith-efficient (i.e. elects a member of the Smith set), and monotonic, but not clone-proof. I wonder if we can also find a clone-proof version of this... Any ideas? Yours, Jobst Election-Methods mailing list - see http://electorama.com/em for list info Election-Methods mailing list - see http://electorama.com/em for list i
Re: [EM] strategy-free Condorcet method after all!
Very ingenious!Perhaps the method could be adapted some way to choose a clone class, then a sub clone class within the winning clone class, etc.- Original Message -From: Jobst Heitzig Date: Saturday, November 14, 2009 4:32 amSubject: strategy-free Condorcet method after all!To: EM Cc: Forest W Simmons > Dear folks,> > it seems there is a stragegy-free Condorcet method after all -- say> good-bye to burying, strategic truncation and their relatives!> > More precisely, I believe that at least in case of complete > information(all voters knowing some details about the true > preferences of all other> voters) and when all voters will follow dominating strategies, > then the> following astonishingly simple method will always make unanimous > sincerevoting the unique dominating strategy, and it will always > elect a true> beats-all winner (=Condorcet winner):> > > Method: Reverse Llull> => > 1. Sort the options into some arbitrary ordering X1,...,Xn (e.g.> alphabetically or randomly), publish this ordering, and put i=n.> > 2. If already i=1, then X1 is the winner. Otherwise, ask all voters> whether they prefer Xi or the option they expect to be the > winner of> applying this method to the remaining options X1,...,X(i-1).> > 3. If more voters prefer Xi, Xi is the winner. Otherwise, > decrease i by> 1 and repeat steps 2 and 3.> > > Why should this be strategy-free?> > If n=2, the question in step 2 is whether X1 or X2 is preferred > and the> method is traditional majority choice in which sincere voting is known> to be the dominant strategy in case of 2 options.> > For n>2, we prove strategy-freeness inductively, assuming it has been> proved for n-1 options already: Since we assume that each voter > followsdominant strategies and knows enough about the other voter's> preferences, and since each voters knows that sincere voting is the> unique dominant strategy for all cases of at most n-1 options, > she will> know in step 2 which option Xj would win if the method was > applied to> X1,...,X(i-1), and she will also know that her vote at this step does> not influence which option Xj is but only whether Xi or Xj will win.> That is, in step 2 all voters face a simple majority choice > between two> known options Xi and Xj, so again voting sincerely in this step > is the> unique dominant strategy. By induction, the whole method is > strategy-free.> > > The method is in some sense the reverse of Llull's famous > earliest known> "Condorcet' method from the 13th century (cited recently on this > list):In the classical Llull method, voters would first make a > majoritydecision between X1 and X2, then a majority choice > between the winner of> the first choice and X3, and so on working thru the whole list of> options, always keeping the last winner and comparing it with > the next> option in the list. The overall winner is the winner of the last > comparison.> So, the only difference between classical Llull and Reverse > Llull is the> order in which these pairwise comparisons are done. If we assume all> voters vote sincerely in classical Llull, both method would be> equivalent. But with strategic voters, the difference is > important: In> classical Llull, a voter's voting behaviour in one step can influence> the results of the later steps (because it can influence which > candidate"stays in the ring"), whereas in Reverse Llull it cannot.> > > In practice, the method can be sped-up by using approval-style ballots> on which each voter marks after step 1 every option Xi which she > prefersto the expected winner of the subset X1,...,X(i-1).> > As for additional properties, Reverse Llull is Pareto-efficient,> Smith-efficient (i.e. elects a member of the Smith set), and > monotonic,but not clone-proof.> > I wonder if we can also find a clone-proof version of this... > Any ideas?> > > Yours, Jobst> Election-Methods mailing list - see http://electorama.com/em for list info
[EM] strategy-free Condorcet method after all!
Dear folks, it seems there is a stragegy-free Condorcet method after all -- say good-bye to burying, strategic truncation and their relatives! More precisely, I believe that at least in case of complete information (all voters knowing some details about the true preferences of all other voters) and when all voters will follow dominating strategies, then the following astonishingly simple method will always make unanimous sincere voting the unique dominating strategy, and it will always elect a true beats-all winner (=Condorcet winner): Method: Reverse Llull = 1. Sort the options into some arbitrary ordering X1,...,Xn (e.g. alphabetically or randomly), publish this ordering, and put i=n. 2. If already i=1, then X1 is the winner. Otherwise, ask all voters whether they prefer Xi or the option they expect to be the winner of applying this method to the remaining options X1,...,X(i-1). 3. If more voters prefer Xi, Xi is the winner. Otherwise, decrease i by 1 and repeat steps 2 and 3. Why should this be strategy-free? If n=2, the question in step 2 is whether X1 or X2 is preferred and the method is traditional majority choice in which sincere voting is known to be the dominant strategy in case of 2 options. For n>2, we prove strategy-freeness inductively, assuming it has been proved for n-1 options already: Since we assume that each voter follows dominant strategies and knows enough about the other voter's preferences, and since each voters knows that sincere voting is the unique dominant strategy for all cases of at most n-1 options, she will know in step 2 which option Xj would win if the method was applied to X1,...,X(i-1), and she will also know that her vote at this step does not influence which option Xj is but only whether Xi or Xj will win. That is, in step 2 all voters face a simple majority choice between two known options Xi and Xj, so again voting sincerely in this step is the unique dominant strategy. By induction, the whole method is strategy-free. The method is in some sense the reverse of Llull's famous earliest known "Condorcet' method from the 13th century (cited recently on this list): In the classical Llull method, voters would first make a majority decision between X1 and X2, then a majority choice between the winner of the first choice and X3, and so on working thru the whole list of options, always keeping the last winner and comparing it with the next option in the list. The overall winner is the winner of the last comparison. So, the only difference between classical Llull and Reverse Llull is the order in which these pairwise comparisons are done. If we assume all voters vote sincerely in classical Llull, both method would be equivalent. But with strategic voters, the difference is important: In classical Llull, a voter's voting behaviour in one step can influence the results of the later steps (because it can influence which candidate "stays in the ring"), whereas in Reverse Llull it cannot. In practice, the method can be sped-up by using approval-style ballots on which each voter marks after step 1 every option Xi which she prefers to the expected winner of the subset X1,...,X(i-1). As for additional properties, Reverse Llull is Pareto-efficient, Smith-efficient (i.e. elects a member of the Smith set), and monotonic, but not clone-proof. I wonder if we can also find a clone-proof version of this... Any ideas? Yours, Jobst Election-Methods mailing list - see http://electorama.com/em for list info
