[EM] Tideman and GMC

[Steve Eppley]

Blake C. wrote:
> Markus S. wrote:
> > 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.

Markus neglected to define "top set."  Nor did he identify the 
participants in this maillist who believe that Schulze meets an 
important criterion not met by Tideman.  If Markus was counting 
me among them, he shouldn't.  And based on private email 
correspondence with Mike Ossipoff over the last few months, it's 
clear to me that Mike also does not believe Schulze is better 
than Tideman in any important way, and Mike no longer considers 
GMC or Beatpath GMC to be important.

Tideman will never elect an alternative which is not in the 
"voted" top cycle, and as far as I can tell it is as good as 
Schulze at avoiding electing a candidate not in the sincere top 
cycle.  Any method which complies with the Beatpath Criterion 
(Schulze, Majoritarian Tideman, Beatpath Criterion Method, etc.) 
appears equally good at this.

I'll repeat the Beatpath Criterion here since it's brief:

   Beatpath Criterion (BC)
   -----------------------
   Let Vij denote the number of voters who ranked i ahead of j, 
   for any pair of alternatives i & j.

   For any pair of alternatives i & j, if Vji > Vij
   then there exists a beatpath from j to i having strength Vji.

   For any three alternatives i & j & k, if there is a beatpath
   from j to k having strength S1 and a beatpath from k to i
   having strength S2 then there exists a beatpath from j to i
   having strength min(S1,S2).

   Let Bji denote the strength of the strongest beatpath 
   from j to i, for any pair of alternatives i & j.

   For any pair of alternatives i & j, if Vij > Vji and Vij > Bji
   then j must not finish ahead of i.

Since Vij>Vji and Vij>Bji together imply Bij>Bji, Schulze 
complies with BC.  I'll post a proof that MTM (a.k.a. Tideman) 
complies with BC if requested.  And BCM obviously complies.  
I'll repeat the definition of BCM since it's even briefer:

   Beatpath Criterion Method (BCM)
   -------------------------------
   For any pair of alternatives i & j, 
   if Vij > Vji and Vij > Bji then eliminate j.

In all of Mike Ossipoff's defensive strategy criteria (which are 
about defeating alternatives not in the sincere top cycle), the 
conditions imply that Vij>Vji and Vij>Bji.  So BC is at the 
heart of the defensive strategy criteria.

If by top set Markus means the Schwartz set, it's true that 
Tideman can elect an alternative outside the Schwartz set.  
Here's a 4-alternative example:

   Majorities:  AC56, AD55, BC54, CD53, DB52
   Pairtie:     A=B

   Alternative A is unbeaten pairwise, is the only alternative
   in the Schwartz set, has a majority beatpath to every other
   alternative, and no alternative has a beatpath to A.
   Schulze selects A.

   But given a choice between A and B, there's no compelling 
   reason that I can discern why B must be defeated.  Tideman
   selects both A & B:  Tideman neglects ("skips") DB52 since 
   DB52 cycles with the larger BC54 & CD53, which leaves both 
   A & B undefeated pairwise.

   MTM is equivalent to Tideman: The ABCD order and the BACD
   order are equally good at minimizing thwarted majorities
   since both of these orders thwart only the DB52 majority. 
   Every other order thwarts a larger majority.

   (Request to Demorep: Please don't ask which alternatives
   are "majority YES approved."  Assume they all are, if you
   feel an irresistible need to consider that irrelevant issue.)

But I don't consider the Schwartz criterion to be of value, and 
neither does Mike Ossipoff.

As I recall, Markus has written that a criterion which is harder 
to meet is necessarily better.  I don't think that's true, 
however.  Here's a fanciful example to illustrate:

   Criterion #1:  
   Defeat all candidates not named Hitler or Clinton.

   Criterion #2:
   Defeat all candidates not named Hitler.

Any voting method which complies with #2 also complies with #1, 
but not vice versa.  So #2 is harder to meet.  But it's obvious 
that #2 is an even worse criterion than #1.  (I hope nobody 
misinterprets the point of this example.  I'm not suggesting 
that Clinton is like Hitler, nor am I suggesting that it would 
be good to elect Hitler.)

A criterion which is harder to meet might just be overbroad.

> I think it is important to realize that we are really talking about
> four methods here:  Schulze (margins), Schulze (winning-votes),
> Tideman (margins), and Tideman (winning-votes).
-snip-

Five methods, since IBCM (Iterated BCM) is as good as MTM & 
Majoritarian Tideman and Schulze on BC, and better on the "head 
to head" stat.  And maybe six methods: I haven't looked at the 
"margins" variation of BCM or IBCM, but it's probably as good as 
Blake's Path Voting and Margins Tideman.

Also, IBCM and MTM are more decisive than Schulze or Path Voting.
But this probably doesn't matter in large public elections, 
where all of these methods (except plain BCM) are reasonably 
decisive.


---Steve     (Steve Eppley    seppley at alumni.caltech.edu)