[EM] New Condorcet versions, & a classification for them

[MIKE OSSIPOFF]

Hi--

A few days ago, before I rejoined this list, I asked someone to
forward a letter from me to the list. Of course since I wasn't
on the list, I wouldn't have received any comments or questions
about that posting, or about my other forwarded posting (about
votes-against vs margins).

And so I'd like, first to answer a few comments that could be
made about my letter in which I defined 2 Condorcet versions,
SD & DCD.

First of all, SD could be written even more briefly than I wrote
it. All I had to say was:

"Drop the weakest defeat that is in a cycle. Repeat till there's
an unbeaten candidate."

***

Someone could say that SD & DCD drop unnecessarily, and that
SD, and especially DCD, isn't as elegant as Schwartz. True, but
those methods are more simple & obvious in their motivation.
And, as I said, and as I'll show, both of those methods meet
all the defensive strategy criteria.

Sure SD can be improved. It's improved by SSD--Schwartz Sequential
Dropping:

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.

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 I said that it's less elegant than
Schulze. 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.

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.

***

Condorcet wrote 2 proposals for solving circular ties. Those
proposals didn't specify as many details as we might like, and
so Condorcet's method should be taken as referring to a _class_
of methods. They have something in common: They drop the weakest
defeat from some set of defeats. 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.

(SSD, SD, Plain Condorcet, Smith//Condorcet, & 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. Though
Plain Condorcet, as defined on this list, is non-iterative, it's
based on an interative wording by Condorcet, and can be written
iteratively).

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. With Plain Condorcet that's
all the defeats. With Smith//Condorcet that's the initial Smith set).

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).

***

It can be shown that if a defeat is among the current Schwartz
set, then that defeat is in a cycle. So since (as I'll show later)
any method that only drops a defeat if it's the weakest defeat
in a cycle meets every one of the defensive strategy criteria,
then SSD is automatically among those methods that accomplish that.

***

Mike Ossipoff
______________________________________________________
Get Your Private, Free Email at http://www.hotmail.com