Re: [EM] Paper By Ron Rivest (fsimm...@pcc.edu)
fsimm...@pcc.edu wrote: As I mentioned in my last message, Designated Strategy Voting (DSV) methods almost always fail monotonicity, even when the base method is monotone. I promised that I would give a general technique for resolving this technique. Before I try to keep that promise, let’s think about why DSV is such an attractive idea. I think that there are two main reasons. (1) The DSV “machine” is supposed to implement near optimal strategy for the voter based on the information it receives. (2) The information the machine receives is directly from the voters on election day, so it should be more accurate than any politically manipulated polling (dis)information available to the voters as a basis for forming their own strategies, should they be so inclined. Myself, I think the reasons that make DSV appealing is: 1. The machine can strategize better than the manual strategists, and it does so indiscriminately, so there's a leveling effect. 2. The machine can strategize better than the manual strategists but GIGO still applies, so there's an incentive to provide honest inputs. They may be similar to your points, but I don't think they're exactly the same. With those points in mind, here is my general remedy: each voter may submit two ballots, the first of which is understood to be a substitute for the polling information that would be used for strategizing in the base method if there were no DSV. Then near optimal strategy (assuming the approximate validity of this substitute polling information) for the base method is applied to the second set of ballots to produce the output ballots, which are then counted as in the base method. This externalizes strategy and criterion failures to the second set of ballots, though, and so feels a bit like cheating. To show it more clearly, consider a method like this: 1. Voters submit two ballots each. 2. There's an IRV election based on the first set of ballots. 3. The pairwise winner, with respect to the second set, of the two candidates who IRV eliminated last, wins. The method is monotone when you consider the second set of ballots, but not with respect to the second or to both. It also seems a bit odd that a DSV method, which is supposed to strategize so that the voter doesn't have to, should ask the voter for both a sincere ballot and a strategic one. Election-Methods mailing list - see http://electorama.com/em for list info
[EM] Paper By Ron Rivest (fsimm...@pcc.edu)
As I mentioned in my last message, Designated Strategy Voting (DSV) methods almost always fail monotonicity, even when the base method is monotone. I promised that I would give a general technique for resolving this technique. Before I try to keep that promise, let’s think about why DSV is such an attractive idea. I think that there are two main reasons. (1) The DSV “machine” is supposed to implement near optimal strategy for the voter based on the information it receives. (2) The information the machine receives is directly from the voters on election day, so it should be more accurate than any politically manipulated polling (dis)information available to the voters as a basis for forming their own strategies, should they be so inclined. With those points in mind, here is my general remedy: each voter may submit two ballots, the first of which is understood to be a substitute for the polling information that would be used for strategizing in the base method if there were no DSV. Then near optimal strategy (assuming the approximate validity of this substitute polling information) for the base method is applied to the second set of ballots to produce the output ballots, which are then counted as in the base method. That’s the idea. Let’s see how it might work for a DSV version of Approval, which is an ideal candidate for DSV because all of the near optimal strategies assume fairly accurate polling information, and voters averse to strategizing miss out on the full potential benefit of their vote: Suppose that the designated strategy for all voters is to approve all alternatives with a score greater than the expected winning score on their score ballot. The voters submit two score ballots, one to substitute for polling information, and therefore not necessarily sincere, and the other for conversion into an approval ballot by the designated strategy. Then … (I) The winning probabilities are calculated from the first set of ballots by some machine that implements game theoretic and/or statistical ideas. (II)Once these approximate winning probabilities have been determined, the approval cutoffs are calculated for each ballot in the second set. The alternative with the greatest approval is elected. Note that since the base method (Approval) is monotone, step (II) is monotone. In other words, if some voters raise the score of the approval winner on the second set of ballots (leaving the first set of ballots unchanged), the winner will not change. Of course it is possible that by raising the score of the winning alternative on the first (polling) ballot, the winner could change. But this possibility already exists (in hidden form) for ordinary Approval; in that setting the voters can manipulate the polls just as much without destroying the reputation of Approval as a monotonic method. Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Paper by Ron Rivest
fsimm...@pcc.edu wrote: The Rivest lottery is non-monotone, but here is a monotone, clone independent lottery that always selects from the uncovered set: 1. Let C1 be a candidate chosen by random ballot. If C1 is uncovered, then C1 wins. 2. Else use random ballot to find a candidte C2 that covers C1. If C2 is uncovered, then C2 wins. 3. Else use random ballot to find a candidte C3 that covers C2. If C3 is uncovered, then C3 wins. 4. Else use random ballot to find a candidte C4 that covers C3. If C4 is uncovered, then C4 wins. etc. Note that the clone independence has the nice character of the Condorcet Lottery and the Rivest method: the conditional probability that a member C of the clone set S is chosen given that the winner is in the clone set is equal to the probability that C would be chosen from S if the method were applied soley to S. I suppose this method can be used to enhance any base method so it elects from the uncovered set. Just let C1 be the winner of the base method. Whether or not that introduces more criteria failures is another question. One could also run the above lottery a billion times and elect the candidate that wins most often. Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Paper by Ron Rivest
fsimm...@pcc.edu wrote: The Rivest lottery is non-monotone, but here is a monotone, clone independent lottery that always selects from the uncovered set: 1. Let C1 be a candidate chosen by random ballot. If C1 is uncovered, then C1 wins. 2. Else use random ballot to find a candidte C2 that covers C1. If C2 is uncovered, then C2 wins. 3. Else use random ballot to find a candidte C3 that covers C2. If C3 is uncovered, then C3 wins. 4. Else use random ballot to find a candidte C4 that covers C3. If C4 is uncovered, then C4 wins. etc. Note that the clone independence has the nice character of the Condorcet Lottery and the Rivest method: the conditional probability that a member C of the clone set S is chosen given that the winner is in the clone set is equal to the probability that C would be chosen from S if the method were applied solely to S. I suppose this method can be used to enhance any base method so it elects from the uncovered set. Just let C1 be the winner of the base method. This enhancement will preserve individually each of the following possible compliances of the base method: clone independence, monotonicity, Independence from Pareto Dominated Alternatives, and Independence from non-Smith alternatives. So Random Ballot Smith would be a great base method for somebody that likes all of these compliances DMC would be a great base method for the same reason.. Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Paper by Ron Rivest
The Rivest lottery is non-monotone, but here is a monotone, clone independent lottery that always selects from the uncovered set: 1. Let C1 be a candidate chosen by random ballot. If C1 is uncovered, then C1 wins. 2. Else use random ballot to find a candidte C2 that covers C1. If C2 is uncovered, then C2 wins. 3. Else use random ballot to find a candidte C3 that covers C2. If C3 is uncovered, then C3 wins. 4. Else use random ballot to find a candidte C4 that covers C3. If C4 is uncovered, then C4 wins. etc. Note that the clone independence has the nice character of the Condorcet Lottery and the Rivest method: the conditional probability that a member C of the clone set S is chosen given that the winner is in the clone set is equal to the probability that C would be chosen from S if the method were applied soley to S. FWS Election-Methods mailing list - see http://electorama.com/em for list info
[EM] Paper by Ron Rivest
This GT method is non-monotonic, which is why we didn't pursue it a few years ago when Jobst reported on the Condorcet Lottery that was based on the pairwise win matrix (i.e. Copeland matrix) in the same way that GT is based on the margins matrix. Election-Methods mailing list - see http://electorama.com/em for list info
[EM] Paper by Ron Rivest
here is an interesting paper by Ron Rivest: http://people.csail.mit.edu/rivest/RivestShen-AnOptimalSingleWinnerPreferentialVotingSystemBasedOnGameTheory.pdf Very interesting paper. It contains a very good rationale for using a random election method (when there is a Condorcet cycle). The GT method in the paper is intriguing. It meets the Condorcet criterion, but if there is a Condorcet cycle then it does not necessarily meet the Pareto criterion! As the paper says, one of the defeats in the Condorcet cycle could be unanimous but the GT method would probably assign all candidates in the cycle a positive probability of winning. (Though the paper claims this can be done with a 3-cycle, it seems to me that you would need at least a 4-cycle.) Is anyone willing to reconsider the Pareto criterion in the case of a Condorcet cycle? I don't know if I am, but it's worth thinking about. Andy Jennings Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Paper by Ron Rivest
Markus Schulze wrote: Hallo, here is an interesting paper by Ron Rivest: http://people.csail.mit.edu/rivest/RivestShen-AnOptimalSingleWinnerPreferentialVotingSystemBasedOnGameTheory.pdf He gets to the conclusion that the Schulze method is nearly perfect (page 12). I'm curious now as to how often, say, Ranked Pairs would disagree with GT/GTD/GTS. Do you consider the GT agreement a worthwhile metric, i.e. that (absent criteria problems) methods closer to GT are better? Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Paper by Ron Rivest
Hallo, Kristofer Munsterhjelm wrote (16 April 2010): I'm curious now as to how often, say, Ranked Pairs would disagree with GT/GTD/GTS. Do you consider the GT agreement a worthwhile metric, i.e. that (absent criteria problems) methods closer to GT are better? I don't like probabilistic models, because I don't think that voters are random variables. However, I am impressed how often authors get to the conclusion that the Schulze method is the best method in random simulations. Markus Schulze Election-Methods mailing list - see http://electorama.com/em for list info
[EM] Paper by Ron Rivest
Hallo, here is an interesting paper by Ron Rivest: http://people.csail.mit.edu/rivest/RivestShen-AnOptimalSingleWinnerPreferentialVotingSystemBasedOnGameTheory.pdf He gets to the conclusion that the Schulze method is nearly perfect (page 12). Markus Schulze Election-Methods mailing list - see http://electorama.com/em for list info
