[EM] Tideman and GMC

[Markus Schulze]

Dear Blake,

Steve Eppley wrote (9 Jun 1999):
> When calculating the size of a pairwin, Cretney uses the pairwise
> margin of victory. (Schulze uses the number of voters who ranked
> the pairwinner ahead of the pairloser.) Blake made a philosophical
> argument for preferring pairwise margins of victory, but I don't
> find it more compelling than the philosophical argument for
> preferring pairwise support (or call it opposition, depending on
> which side you're on). More important than philosophical criteria,
> in my opinion, are other criteria we usually use for comparing
> voting methods.

I have to agree with Steve Eppley. It seems to me that you put too
much emphasis on heuristics. It is true that on the one hand it is
advantageous for campaign purposes to have a simple heuristic for
a given election method. But on the other hand in the end only the
properties of this election method are important. And if we look at
the properties then the Schulze Method is superior to the Tideman
Method in so far as there is no desirable criterion that is met by
Tideman and that is not met by Schulze and there is at least one
criterion that is met by Schulze and that is not met by Tideman and
that is important to at least a few participants of this mailing
list: Schulze guarantees that never unnecessarily a candidate is
elected who is not in the sincere top set.

The problem of heuristics is that they usually contain many
implicite presumptions. The most severe implicite presumption of
Tideman's heuristic is the presumption that the task of an election
method is to find the most probably best _ranking_ and not the most
probably best _candidate_. To my opinion, Tideman's implicite
presumption is not justifiable. To my opinion, the parties and the
voters are interested only in which candidate wins and they are not
interested in which candidate gets which position in the ranking.

******

You wrote (31 Jan 2000):
> What about
>
> 25 A D B C
> 35 B A D C -> B
> 30 D C A B
> 4  A D C B
> 6  C A D B
>             winning-votes
> A->D 35-30   35
> A->B 65-35   65
> C->A 36-29   36
> B->C 60-40   60
> D->B 65-35   65
> D->C 59-6    59
>
> Here, A is in the SASW; D is not.  A wins in Tideman (winning-votes),
> but D wins in Schulze.

I don't understand your example. What do you want to demonstrate with
your example? Do you want to criticize the mathematical formulation of
beat path GMC? Or do you want to criticize the Schulze Method?

First: The intention of beat path GMC is that a voter should rather be
punished than rewarded for truncating his votes. In your example, beat
path GMC does exactly what it was designed to do. Those 35 voters whose
sincere opinion is B > A > D > C truncate their votes and change the
winner from candidate A to candidate D. Thus the truncators are
punished. In so far as beat path GMC does exactly what is was designed to
do, your example cannot be interpreted as a criticism of beat path GMC.

Second: In your example (25 voters vote A > D > B > C; 35 voters vote B;
30 voters vote D > C > A > B; 4 voters vote A > D > C > B; 6 voters vote
C > A > D > B.), not enough information is available to calculate the
SASWs. In your example, Tideman accidently elects a SASW while Schulze
accidently elects a non-SASW because you presumed that the sincere
opinion of the 35 voters who vote for B only is B > A > D > C. But in so
far as we usually don't have any information about the sincere preferences
but only about the reported preferences, it is also possible that the
sincere opinion of the 35 voters who vote for B only is B > D > A > C so
that Tideman accidently elects a non-SASW while Schulze accidently elects
a SASW in your example. The difference between Tideman and Schulze is that
Schulze can elect a non-SASW only if not enough information is available
to calculate the SASWs while Tideman can unnecessarily elect a non-SASW.

******

You wrote (31 Jan 2000):
> Markus Schulze wrote (29 Jan 2000):
> > Blake Cretney wrote (24 Jan 2000):
> > > I have made some attempts to show that Schulze (path voting) is
> > > in some way intuitive.  That is, it seems to rely on "arguments"
> > > composed of majority views, where the strength of the argument
> > > is equal to its weakest link.
> > >
> > > So, if we have
> > >
> > > A>B 30
> > > B>C 20
> > > C>D 15
> > >
> > > If we view pairwise decisions as more probably correct than
> > > incorrect, we have to view this as evidence that A is better
> > > than D.  But what if we also knew that
> > >
> > > C>E 30
> > > E>B 25
> > >
> > > Clearly, this gives evidence contrary to one of the links in our chain
> > > of argument (B>C).  It suggest that it is more likely that C is better
> > > than B, than the contrary.  The whole chain of argument falls apart.
> > > In fact, it is Tideman that makes use of this additional information.
> >
> > It is not correct to say that "Tideman makes use of additional
> > information." For every pair of election methods it is possible to
> > create a situation such that both election methods lead to the same
> > result and such that -if this situation is slightly modified- election
> > method 1 still leads to the same result as before and method 2 leads
> > to a different result. But it is not correct to conclude that election
> > method 2 uses more information. All election methods use the same
> > information; they only interpret this information differently.
>
> My point was not that Tideman makes use of more information, in
> general.  My point was only that additional information is used in a
> particular situation, and that in that situation the additional
> information seems relevant.  Of course, this assumes an attempt to
> base the method on probability, evidence, or some similar grounds.
>
> That is, if we justify Schulze on the basis that a path of victories
>
> A>B, B>C, C>D
>
> should be granted as evidence that A>D, as an obvious result of
> believing that each pairwise victory is evidence of the superiority of
> the winner over the loser, then we must also acknowledge that a path
> contradicting one of these pairwise victories (a side-path) must
> contradict the entire chain of argument.  Tideman ensures that if a
> path is to be "locked", each victory must not contradict a higher
> "locked" path.  So, it is using the information provided by these
> side-paths.

The Tideman winner usually depends on more elements of the matrix of
pairwise defeats than the Schulze Method. The reason: The Schulze
Method tries to find the most probably best _candidate_ and not the
most probably best _ranking_. Therefore very often it is possible to
"guess" the Schulze winner and then -by calculating the beat paths
from this guessed winner to every other candidate and from every
other candidate to this guessed winner- to verify whether this guess
is correct. On the other hand the Tideman Method tries to find the
most probably best _ranking_ and not the most probably best _candidate_.
Therefore if you want to calculate the Tideman winner you always have
to calculate the complete Tideman ranking.

Example:

   26 voters vote C > A > B > D.
   20 voters vote B > D > A > C.
   18 voters vote A > D > C > B.
   14 voters vote C > B > A > D.
   08 voters vote B > D > C > A.
   07 voters vote D > A > C > B.
   07 voters vote B > D > A = C.

Then the matrix of pairwise defeats looks as follows:

   A:B=51:49
   A:C=45:48
   A:D=58:42
   B:C=35:65
   B:D=75:25
   C:D=40:60

Tideman:

   Tideman would
   1) lock B > D,
   2) lock C > B,
   3) skip D > C because it would create a directed cycle
      with the other already locked pairwise defeats,
   4) lock A > D,
   5) lock A > B,
   6) lock C > A.

   Thus the Tideman ranking is C > A > B > D and the Tideman
   winner is candidate C.

Schulze:

   A has 58 votes against B via the beat path A > D > C > B.
   A has 58 votes against C via the beat path A > D > C.
   A has 58 votes against D via the beat path A > D.

   B has 48 votes against A via the beat path B > D > C > A.
   B has 60 votes against C via the beat path B > D > C.
   B has 75 votes against D via the beat path B > D.

   C has 48 votes against A via the beat path C > A.
   C has 65 votes against B via the beat path C > B.
   C has 65 votes against D via the beat path C > B > D.

   D has 48 votes against A via the beat path D > C > A.
   D has 60 votes against B via the beat path D > C > B.
   D has 60 votes against C via the beat path D > C.

   Candidate A is the Schulze winner because candidate A defeats
   every other candidate via beat paths.

In the Schulze Method, the strength of the pairwise defeat B:D
has no influence on the final winner; even if we set B:D=100:0
or B:D=0:100, candidate A stays the Schulze winner. On the other
hand, if we set B:D=59:41 then the Tideman winner is changed from
candidate C to candidate A.

You seem to believe that the fact that the Tideman winner usually
depends on more elements of the matrix of pairwise defeats is a
selling point. I view this fact of Tideman to be the fatal flaw in
this method. The reason: If the question whether candidate A or
candidate C is elected unnecessarily depends on how many voters
prefer candidate B to candidate D then it is possible to manipulate
the result of the elections by ranking B respectively to
candidate D insincerely.

In other words: If an election method should be as difficult as
possible to manipulate then it should not only meet monotonicity,
local independence from irrelevant alternatives, complete
independence from clones, and beat path GMC, the result of the
election method should also depend on as few irrelevant information
as possible.

******

You wrote (31 Jan 2000):
> There are three major kinds of strategic voting (as far as I know).
>
> Burying-  Lower a candidate (with respect to sincere placement) in
> the hopes of defeating it.  This is what SPC prevents.
> Compromising- Raise a candidate in the hopes of electing it. This
> is impossible to eradicate in a non-random method, but some methods
> are more affected than others.
> Push-over- Lower a candidate in the hopes of electing it.  This is
> what monotonicity prevents.

Example 1:

Suppose that the sincere opinion of a given voter is A > B > C > D.
Suppose that this given voter votes B > A > C > D to change the
winner from D to C.

Example 2:

Suppose that the sincere opinion of a given voter is A > B > C > D.
Suppose that this given voter votes A > C > B > D to change the
winner from D to A.

Is this Burying, Compromising or Push-over?

******

Markus Schulze
schulze at sol.physik.tu-berlin.de
schulze at math.tu-berlin.de
markusschulze at planet-interkom.de