[EM] Tideman and GMC

[Markus Schulze]

Dear Blake,

you wrote (24 Jan 2000):
> Back at one time, on this list, one popular criterion was GMC.  This
> said,
>
> If any candidate has a pairwise absolute majority against it, that
> candidate should not win, unless all candidates have pairwise absolute
> majorities against them.
>
> By pairwise absolute majority, I mean that a majority of the voters
> have ranked one candidate over another.  Note that I am speaking of a
> majority of ALL the voters, not just those with a preference between
> the two candidates.
>
> I will also define an absolute Condorcet winner to be a candidate
> with an absolute pairwise majority against each other candidate, and a
> sincere absolute Condorcet winner (SACW) to be the absolute Condorcet
> winner among voters actual, as opposed to expressed preferences.
>
> Now, the idea was that a method that met GMC would not allow a group
> of voters to defeat the SACW in favour of a candidate they like
> better, if they use only truncation.  Truncation is insincerely
> leaving candidates unranked.
>
> If there is a SACW, this means that the candidate has an absolute
> pairwise majority against each other candidate.  Truncation cannot
> create an absolute majority against the SACW, as it does not actually
> add votes.  As well, since the truncator already has the preferred
> candidate ranked over the SACW, truncation will not reduce its loss
> against the SACW.  So, even after truncation, the truncator's
> candidate still is excluded by GMC, and the SACW isn't.  Therefore,
> the truncator's candidate cannot win.

Ossipoff's GMC presumes that there usually is a SACW. There is -to my
opinion- no justification for this presumption. That's why I defined the
"Set of Sincere Absolute Smith Winners" (Set of SASWs) to be the smallest
non-empty set of candidates such that every candidate in this set wins
against every candidate outside this set with an absolute pairwise
majority. Obviously there is always at least one SASW because in worst
case every candidate is a SASW. Beat path GMC says that plain truncation
should not be able to make a non-SASW win the elections.

The exact mathematical formulation of beat path GMC looks as follows:

   "X >> Y" means that an absolute majority of the voters
   strictly prefers candidate X to candidate Y.
   "There is a majority beat path from X to Y" means that
   (1) X >> Y or 
   (2) there is a set of candidates C[1],...,C[n] with
       X >> C[1] >> ... >> C[n] >> Y.

   If there is a majority beat path from candidate A to
   candidate B and no majority beat path from candidate B
   to candidate A, then candidate B must not be elected.

I agree with you that the mathematical formulation of beat path GMC is
not very intuitive. Beat path GMC says that -in the formulation above-
it is possible that candidate A is a SASW and candidate B is no SASW
but it is not possible that candidate A is no SASW and candidate B is a
SASW. Therefore -if either candidate A or candidate B has to be elected-
rather candidate A than candidate B should be elected.

You wrote (24 Jan 2000):
> However, GMC was found to be in conflict with the Smith criterion
> (and GITC depending on how you define it).  Certainly the methods that
> passed GMC failed both these criteria.  As a result, GMC fell out of
> favour, and was superseded by a new criterion, beat path GMC.
>
> This new GMC relied on the idea of a path of absolute pairwise
> majorities from one candidate to another.  So, if X has an absolute
> majority over Y, and Y has an absolute majority over Z, there is a
> path of these majorities from X to Z.
>
> The new GMC said,
>
> For any candidates X and Z, if X has a path of absolute majorities to
> Y, then Y must not win, unless Y has a path of absolute majorities to
> X.
>
> Markus Schulze showed that this new criterion was consistent with
> GITC and Smith, by proposing a method that satisfied all 3.  Another
> method, Tideman, was shown to fail beat path GMC, and largely for this
> reason was considered defective.  
>
> I should point out that I never agreed with GMC, or with the argument
> about truncation.  However, the purpose of this posting is to suggest
> that Tideman was unfairly criticized, even assuming the argument about
> truncation.  I am going to suggest that beat path GMC is much more
> restrictive than necessary to be a successor of the original GMC. 
> Also, although I think that majority strengths should be measured in
> margins, I will be considering the version of Tideman which only uses
> the number of votes on the winning side.
>
> Beat path GMC seemed a natural revision of GMC, but it was not the
> only one possible.  Consider instead the following definition, GMC2
>
> For any candidates X and Y, if X has an absolute majority over Y,
> then Y must not win, unless Y has a path of absolute majorities to X.
>
> Now, it is clear that the winning-votes version of Tideman has this
> property.  The only way for the X vs. Y victory to not get locked, is
> if there is already a path of locked victories from Y to X.  This can
> only happen if they are considered greater victories by the method.
>
> GMC2 implies the same kind of truncation resistance as did GMC.  The
> truncator's candidate has an absolute majority against it from the
> SACW.  Because no absolute majority exists against the SACW, it
> follows that there is no path from truncators candidate to SACW, and
> the truncators candidate is excluded by GMC2.
>
> So, my conclusion is that Tideman (winning-votes) was rejected on
> faulty grounds.

GMC2 is a relaxation of beat path GMC. Why should I relax a given
criterion if this given criterion is compatible to all other desired
criteria?

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.

Tideman would elect candidate C.
But it is possible that candidate A is a SASW and candidate C is no SASW
and it is not possible that candidate A is no SASW and candidate C is a
SASW. Therefore rather candidate A than candidate C should be elected.

Of course, you can disagree with my desire that no non-SASW is elected.
But it is not correct to say that "Tideman was rejected on faulty grounds."

You wrote (24 Jan 2000):
> In my previous posting I suggested that Tideman was originally
> rejected on faulty grounds.  Now, the arguments mentioned did not
> influence me, because I disagreed with some premises behind them. 
> However, I had suggested some other reasons for rejecting Tideman,
> which have over time appeared less convincing.  In particular, my
> justifications for favouring Schulze (using margins) over Tideman seem
> in retrospect rather poor, and I am starting to lean towards Tideman
> as the superior method.  The methods are so similar, that it is hard
> to find useful points of differentiation.
>
> Reverse-consistency
>
> Some time ago, I suggested that Tideman was inferior because its
> handling of ties did not appear to be internally consistent.
>
> A > B 30
> B > C 30
> C > A 30
> A > D 8
> D > B 5
> D > C 6
>
> I reasoned that Tideman in effect made the winners
> { A, D }
> suggesting that A and D are superior to B and C
>
> But, if all ballots were reversed, the winners were
> { A, B, C}
> which suggests that for the un-reversed ballots, D is superior to A,
> B and C.
>
> I note an equivalent situation in Schulze
>
> 5 A B C
> 5 D (A=B=C)
>
> The potential winners are A and D.  The reverse gives C and D.
> What the above ballot suggests is that A is preferred to B, but there
> is no way to know which, or all, of A, B, and C are preferred to D.
> The argument that D=A and A>B, therefore D>B, just does not follow.  A
> tie should not be taken as a statement of equality, but of indecision.
> However, with this view, the complaint against Tideman evaporates.

Your argumentation is problematic because of two reasons.

First: You write: "I suggested that Tideman was inferior because
its handling of ties did not appear to be internally consistent."
You can criticize a given election method for its handling of ties
only if this handling of ties is an elementary part of this election
method.

I have read Tideman's papers [T. Nicolaus Tideman, "Independence of
Clones as a Criterion for Voting Rules," Social Choice and Welfare,
vol. 4, p. 185-206, 1987; T.M. Zavist, T. Nicolaus Tideman, "Complete
Independence of Clones in the Ranked Pairs Rule," Social Choice and
Welfare, vol. 6, p. 167-173, 1989]. His proposals how to handle ties
are unnecessarily complicated and have no interesting properties.
But there is absolutely no reason to use Tideman's handling of ties.
You can simply use that handling of ties that had been proposed by you
or that handling of ties that had been proposed by me without losing
any of Tideman's properties and without violating any of Tideman's
heuristics.

So there is no justification to criticize Tideman because of his
very secondary proposals how to handle ties.

Second: Reversal Symmetry (or "Reverse-consistency" as you call it)
is only defined for situations where every voter ranks all candidates
and there is a unique winner. Otherwise Reversal Symmetry would
presuppose e.g. how equal rankings are interpreted; even whether
Borda meets Reversal Symmetry would depend on how you interpret
equal rankings and on how you dissolve ties.

Therefore your examples don't demonstrate any inconsistencies in
the Tideman Method or the Schulze Method.

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

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