[EM] Fw: IBCM, Tideman, Schulze

[MIKE OSSIPOFF]

Dear Markus--

You wrote:


>It seems to me that you consider iterative methods to be more
>intuitive than non-iterative methods.

Well, the most intuitive BC complying methods are iterative
methods. And that seems true of Condorcet versions in general,
because, for instance, PC is more obvious & natural when
defined iteratively.

>
>Actually the Schulze method can also be explained as an iterative
>method:
>
>Step 1: If there are still pairwise comparisons that haven't
>   yet been dropped between candidates that haven't yet been
>   eliminated then drop the weakest pairwise comparison between
>   candidates that haven't yet been eliminated. If there is more
>   than one weakest comparison then all the weakest comparisons
>   are eliminated simultaneously. Eliminate all those candidates A
>   for which there is a candidate B such that there is a path of
>   non-dropped pairwise comparisons from candidate B to candidate A
>   but no path of non-dropped pairwise comparisons from candidate B
>   to candidate A.
>
>Step 2: Repeat Step 1 until there are no pairwise comparisons
>   that haven't yet been dropped between candidates that haven't
>   yet been eliminated.

That isn't simple. This is simple:

1. An unbeaten set is a set of candidates none of whom are beaten
   by anyone outside that set.
2. An innermost unbeaten set is an unbeaten set that doesn't
   contain a smaller unbeaten set.
3. Drop the weakest defeat that is among an innermost unbeaten set.
   Repeat till there's an unbeaten candidate.

(To this, and to your wording, needs to be added that A's defeat
of B has a magnitude equal to the number of people who voted
A over B)

When I showed someone an unbeaten set, and an innermost unbeaten
set, via a diagram, and said that we drop the weakest defeat
that's among an innermost unbeaten set, it was clear &
intuitive & natural to her. So much so that she liked it better
than SD. I doubt that she'd have accepted it if I'd defined it
in terms of beatpaths.

I'm not saying that beatpaths aren't intuitive at all, but
their importance isn't obvious like that of unbeaten sets.
A person will wonder if a beatpath method is better than some
other equally arbitrary-sounding rule. It's _obvious_ that
the members of an innermost unbeaten set are uniquely
deserving of winning.

***

That SSD definition has a natural & obvious motivation &
justification that Schulze doesn't have. Both your definitions
use beatpaths.

>
>The difference between Schulze and SSD is: SSD cnsiders only
>those pairwise comparisons that are pairwise wins while Schulze
>considers all pairwise comparisons.

But they both pick the same winner when there are no pair-ties
or equal defeats.

Could your method be reworded without eliminating candidates, and
in terms of innermost unbeaten sets rather than beatpaths?
Could it be worded as simple as the above SSD definition? If so,
then we would have a Schulze definition that's as intuitive
as SSD. That would bring the great advantage that the method
could be recommended for small committees as one of the 2 best
methods, as well as being proposed for public elections, as can
now be said for Tideman(wv).

>
>Example:
>
>   A:B=50:50
>   B:C=43:48
>   C:A=35:44
>
>   SSD chooses candidate A decisively because candidate A is
>   the unique Schwartz winner.

Correct.

>
>   The Schulze method drops the "35" in the pairwise matrix.
>   Then it drops the "43" in the pairwise matrix. Then it
>   drops the "44" in the pairwise matrix. Then it chooses
>   candidate C because there is a path of non-dropped pairwise
>   comparisons from candidate C to candidate A but no path
>   of non-dropped pairwise comparisons from candidate A to
>   candidate C and because there is a path of non-dropped
>   pairwise comparisons from candidate C to candidate B but no
>   path of non-dropped pairwise comparisons from candidate B
>   to candidate C.

Wait a minute. I thought I understood beatpath Schulze. A has
a beatpath to B, and to C, but neither has a beatpath to A.
How could A not be the Schulze winner? If the iterative procedure
you described above produces the same winner as beatpath Schulze,
then I've misunderstood the definition of beatpath Schulze
(the original non-iterative Schulze definition based entirely
on beatpaths).

>
>Remarks:
>
>(1) To my opinion, Schulze is more similar to Condorcet's bottom-up
>proposal than SD. Condorcet wrote that _the weakest pairwise
>comparisons_ should be dropped successively. He didn't write that
>_the weakest pairwise comparisons that are in a directed cycle_
>should be dropped successively.

Yes, and based on that, and on the translations that you quoted
below, PC is the literal interpretation of Condorcet's words.
SD, as you point out isn't the literal meaning, and neither is
SSD.

But the 2nd quote, could be interpreted in a more refined way:

We could say: "Since we're only dropping defeats because they
can't all exist together, then isn't it true that we need only
drop from the (or a) set of defeats that can't exist together?

If we use the word "the", instead of "a", the defeats among
the current Schwartz set are the ones that can't exist together.
They're the ones in conflict about the winner. The defeats of
Schwartz set members against non-members aren't contradicted.

But if we use "a", we can say that any cycle contains defeats
that cannot all exist together, and so defeats in cycles are
all that qualify for dropping.

The first assumption gives us SSD, and the second assumption
gives us SD. There's a strong case for saying that Condorcet
would have carried out SD or SSD rather than PC. Regrettably
I guess he didn't leave examples.

>
>On page 126 of his "Essai sur l'application de l'analyse a la
>probabilite des decisions rendues a la pluralite des voix"
>(Imprimerie Royale, Paris, 1785), Condorcet wrote:
> > Create an opinion of those n*(n-1)/2 propositions, which win
> > most of the votes. If this opinion is one of the n*(n-1)*...*2
> > possible, then consider as elected that subject, with which this
> > opinion agrees with its preference. If this opinion is one of the
> > (2^(n*(n-1)/2))-n*(n-1)*...*2 impossible opinions, then eliminate
> > of this impossible opinion successively those propositions, that
> > have a smaller plurality, & accept the resulting opinion of the
> > remaining propositions.
>
>In "Sur les Elections," Condorcet wrote due to McLean's
>translation (Iain McLean, Fiona Hewitt, "Condorcet," Edward
>Elgar Publishing, 1994):
> > A table of majority judgements between the candidates
> > taken two by two would then be formed and the result - the
> > order of merit in which they are placed by the majority -
> > extracted from it. If these judgements could not all exist
> > together, then those with the smallest majority would be
> > rejected.
>
>(2) To my opinion, Schulze is more intuitive than Tideman
>because why should I proceed overruling voters until there
>is a complete ranking when I am only interested in the
>winner?

Yes, that occurred to me also, comparing the intuitiveness of
SSD & SD to that of Tideman. Since we don't have a winner because
everyone is beaten, then it's natural to only drop the defeats
it takes to make someone unbeaten. The smallest defeat that will
do the job, repeated if necessary.

But of course that's mostly true if someone in the same crowd is
saying "But why not do it this way [SD or SSD]?" If Tideman is
the only proposal being offerred, I don't know if it will occur
to people to wonder why we have to get rid of all the cycles.

If someone asks, we can answer that we do it because quitting
when we undefeat someone, and leaving cycles unsolved, can
ignore important relationships among the defeats. That's true,
isn't it? And I wonder if, when Tideman & SSD differ, the total
number of overruled voters isn't lower with Tideman.

Maybe Tideman's ability to examine the overall defeats situation
more thoroughly than SSD does can explain, and be justified by,
the fact that the Tideman winner usually beats the SSD winner
pairwise.

I'd thought previously that an advantage of SSD is, by dropping
smallest defeats, it overrules fewer people. But I don't know
if that's still true if we consider _all_ the people it overrules
when it drops 2 defeats. I haven't thoroughly checked this out
yet: Does Tideman or SSD, when compared to the other, consistently
elect someone who has fewer votes against him?

Mike Ossipoff



________________________________________________________________________
Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com