Fwd: New Condorcet versions, & a classification for them
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
Reply to: