Hi-- I'd like to tell you about some new proposals for versions of Condorcet's method, and about a classification of Condorcet versions. But first, let me correct a typo in my previous letter, where I talked about the problems of solving circular ties by the Alternative Vote method: When commenting on the example that I'd listed, what I meant to say was: With the currently-specified rule for solving circular ties in Debian elections, it's no coincidence that the A voters are in a position to make a circular tie, by truncation, and are also the winners when that tie is solved by the Alternative Vote, after B is eliminated. The reason why the A voters are in a position to make a circular tie is because A beats C pairwise. Otherwise, the truncation would merely give the election to C. And the reason why A wins after B is eliminated is also because A beats B pairwise. So then, the people who are in a position to make a circular tie are set up to win it too, when the circular tie is solved by the Alternative Vote, as the rules currently specify. The A voters can gain by truncation (as they do in the example), and can't worsen their outcome by it. If they're sure that A beats C pairwise, then the strategy of truncating dominates the strategy of voting a complete ranking. So that circular tie solution makes offensive truncation those voters' best strategy. And it creates a defensive strategy problem for that majority who prefer B to A. If it's widely expected that A will beat C pairwise, so that truncation is clearly the best strategy for the A voters, then the C voters need to rank B equal to C, to foil the A voters' attempt to create a circular tie. But if the A voters escalated their offensive strategy to order-reversal, ranking C over B, then the C voters would need to vote B over their favorite in order to prevent the A strategy from working. B is the candidate who'd beat each one of the others pairwise if everyone sincerely ranked all the candidates. Such a candidate is called the "Condorcet winner". In a susequent message, I'll talk about criteria. Now I'd like to mention some better circular tie solutions:' *** Condorcet made 2 proposals for what to do when there's no candidate who beats each one of the others in pairwise comparisons (I call such a candidate a "BeatsAll candidate"). Condorcet wasn't as specific about details as we might like, and so Condorcet's method should be regarded as a _class_ of methods. What they have in common is that they drop the weakest defeat from among some subset of the pairwise defeats in the election. Later in this letter I'll suggest a classification of Condorcet versions. First I define a few of them. Condorcet's idea of dropping weakest defeats is really the obvious & natural thing to do when the defeats conflict with eachother (by forming one or more cycles). Here are a few Condorcet versions: When there's a circular tie, we can't honor each one of the pairwise defeats; every candidate is beaten by another, so we don't have the luxury of being able to elect someone who wins all his pairwise comparisons. So we have to overrule or disregard at least one pairwise defeat. But we don't do that lightly, since when we do that, electing Y, we're overruling those voters who indicated that they'd rather have X than Y. So we should at least overrule as few voters as possible. So if we have to drop a pairwise defeat, we'd rather that it be the defeat that has the fewest people voting for it. So, "the weakest defeat" means the defeat that has the fewest people ranking the defeater over the defeated, the defeat that is voted for by fewest people. Here, then, are some count rules based on that: *** "Drop the weakest defeat in every cycle". I call that "Drop Contradicted Defeats" (DCD). It's surely the most briefly defined way of counting ranked ballots. It's much briefer than the way the Alternative Vote is defined. If, as could happen with DCD, it undefeats more than 1 candidate, then eliminate all candidates other than the undefeated ones, and start over, applying DCD's rule with just those tied candidates as the candidate set, and using the elections original defeats-- in other words, starting over with no defeats dropped. Re-applying the method to its ties is the obvious solution when DCD undefeats more than 1 candidate. But the rule stated next won't undefeat more than 1 candidate, under public election conditions--conditions where there are no pairwise ties or exactly equal defeats. So with the next method, and subsequent ones, there's no need to talk about tiebreaking in elections with many voters. Of course when there are few voters, ties unavoidably become more likely with any method. *** "Drop the weakest defeat that is in a cycle. Repeat till there's an unbeaten candidate". *** I call that "Sequential Dropping", or SD. DCD & SD are the briefest & most obvious & natural Condorcet versions, and are among the best, in terms of results, as I'll show when I write about criteria. Next is a method requiring a slightly wordier definition: *** "Drop the weakest defeat from among the members of the current Schwartz set. Repeat till there's an unbeaten candidate." *** The current Schwartz set is the Schwartz set based only on those defeats which haven't yet been dropped. Informally, the Schwartz set is the innermost set of candidates who are not beaten from outside the set. Here's a more precise definition: 1. An "unbeaten set" is a set of candidates none of whom is beaten by anyone outside the set. 2. A "small unbeaten set" is an unbeaten set that doesn't contain a smaller unbeaten set. 3. The "Schwartz set" is the set of candidates who are in small unbeaten sets. *** SSD is equivalent to Schulze's method if there are no pairwise ties or exactly equal defeats. I'll define Schulze's method later. The defeats in the Schwartz set are the only ones that are really in conflict for choosing a winner. SD could unnecessarily solve a bottom cycle, which is why it's less elegant than SSD. But that won't affect the outcome, when there are no pairwise ties or equal defeats, because everyone in that bottom cycle has a noncyclic defeat from the top cycle, a defeat which won't be dropped. If there are no pairwise ties or equal defeats, then SD is equivalent to SSD, which under those conditions is equivalent to Schulze's method. That's pretty good for something as simple & obvious as SD. Additionally, DCD, like SSD & SD, always chooses from the initial Schwartz set candidates when there are no pairwise ties or equal defeats. Also, as I'll show in a subsequent letter, SD & DCD meet all of the defensive strategy criteria. It turns out that that is accomplished by only dropping a defeat if it's the weakest defeat in a cycle. It can also be shown that any defeat among the Schwartz set members is in a cycle. *** I'd like to suggest a classification of those methods according to 3 variables: 1. Whether the method is iterative from the top down or from the bottom up, or whether its rule treats the dropping as simultaneous. (SSD, SD, & SD are bottom-up. Schulze is equivalent to SSD under large-election conditions. DCD, since it drops the weakest defeat in every cycle, could be written iteratively either way. Tideman is top-down). 2. We only drop a defeat if it's the weakest defeat among what kind of a set of defeats? (With SSD that's the defeats among the current Schwartz set. With SD & DCD & Tideman that's a cycle. As I said, any defeat among the current Schwartz set is in a cycle). 3. Stopping goal. (The methods other than Tideman & DCD stop when they make an undefeated candidate. DCD & Tideman stop when they've solved all cycles--if I understand Tideman correctly). *** A few other methods: I said that, when there are no pairwise ties or equal defeats, SSD is equivalent to Schulze. I'll define Schulze here. I'd like to add first that, when there are pairwise ties or equal defeats, SSD can be more decisive than Schulze. Schulze's method: 1. A has a beatpath to B if either A beats B, or if A beats something that has a beatpath to B. 2. The strength of a beatpath is measured by the strength of its weakest defeat. 3. If A has a stronger beatpath to B than B has to A, then A has a "Schulze win" over B. 4. The winner is the candidate who has a Schulze win over each one of the others. (It's been shown that there's always such a candidate, if there are no pairwise ties or exactly equal defeats. As I said, SSD & Schulze are equivalent under those conditions). Of course "A beats B", and the strength of B's defeat by A are defined the same for Schulze as for the previously described methods. *** Earlier, we on the mailing lists discussed 2 other methods that aren't quite as top-grade as the one's that I've already described here, but which are still better than any non-Condorcet method. In the classification that I described earlier, if we choose a bottom-up method that stops when it makes an unbeaten candidate, and for which the set discussed in paragraph 2 is the whole set of candidates, that's the method that we call Plain Condorcet. So the rule for Plain Condorcet would be: "Drop the weakest defeat. Repeat till there's an unbeaten candidate." *** That's a little simpler than SD, but because it doesn't limit itself to dropping the weakest defeat in a cycle, it doesn't do quite as well as the previously-described methods, in terms of criteria. Plain Condorcet will sometimes drop a noncyclic defeat, electing someone who has a noncyclic defeat. Plain Condorcet strictly passes some defensive strategy criteria, but not others. But it only fails those under relatively rare special conditions. Its main drawback is that it fails some criteria that are important to some academic authors. But it does better by defensive strategy criteria than any non-Condorcet method. *** Smith//Condorcet: "Use Plain Condorcet to choose from among the candidates in the initial Smith set." The Smith set is the smallest set of candidates who each beat everyone outside that set. (Somewhat less exclusive than the Schwartz set). The initial Smith set is the set of candidates who were in the Smith set before any defeats were dropped. *** Of course Plain Condorcet could be reworded to say: "The winner is the candidate whose greatest defeat is the least." *** I recommend SSD, SD, DCD, or Schulze. Schulze doesn't have the obvious natural motivation & justification that the others in that list have, which could make it more difficult to get adopted. *** Plain Condorcet or Smith//Condorcet could be used if computational simplicity were a goal. But implementation software is available for all of the methods mentioned in this letter. Mike Ossipoff ______________________________________________________ Get Your Private, Free Email at http://www.hotmail.com
