Beatpath criterion, Tideman, and BCM (was Re: [EM] Tideman and GMC)

[Steve Eppley]

Blake C wrote:
-snip-
> 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.
>
-snip-
> So, my conclusion is that Tideman (winning-votes) was rejected on
> faulty grounds.

I agree with Blake.  The so-called "Tideman bad example" 
(which Mike Ossipoff had posted) showed Tideman defeating an 
alternative which lost only one pairing, and that pairing was 
1 to 0, and that outcome looked dubious.  Schulze would have 
elected that alternative.  

But Tideman elected the alternative which won that 1 to 0 
pairing.  How can we claim that the Schulze winner (Tideman 
loser) is preferable when not even one voter considers it 
preferable?

I've been using a different criterion, which dispenses with 
the "absolute majority" requirement, and so is more general:

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

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

   If Vij > Vji and Vij > Bji then j must not finish ahead of i.

The "ideal" majoritarian criterion, if it were not sometimes 
impossible to satisfy, is:

   If Vij > Vji then j must not finish ahead of i.

The Beatpath Criterion is possible to satisfy, and is not 
as overbroad (what Blake calls "restrictive") as what might be 
called the Schulze criterion (if Markus doesn't object to using 
his name this way):

   If Bij > Bji then j must not finish ahead of i.

Any voting method which complies with the Beatpath Criterion 
also complies with Mike Ossipoff's defensive strategy criteria 
and with this generalization of his SFC:

   General "Strategy-Free" Criterion (GSFC)
   ----------------------------------------
   If no voter ranks any alternative ahead of a more preferred
   or equally preferred alternative, and an absolute majority 
   rank at least one member of the sincere top cycle ahead of 
   an alternative X not in the sincere top cycle, then X must
   not finish first.

Though the wordings of Tideman posted in this maillist have, 
to the best of my knowledge, all been of the form
   "Working from largest majority (or margin) to smallest,
   exclude any which cycles with larger ones" 
there are ways to word it non-iteratively.  Here are some 
non-iterative wordings of the majoritarian method:

   Minimize Thwarted Majorities (MTM)
   ----------------------------------
   If Vij > Vji and the social ordering ranks j ahead of i, 
   then the social ordering "thwarts" the Vij majority who 
   ranked i ahead of j.

   Select as the social ordering the ordering which 
   minimizes thwarted majorities.

By "minimizing" thwarted majorities, I mean that to compare two 
orderings to see which is better, we compare each ordering's 
largest thwarted majority.  If that's a tie then compare their 
second largest, etc.

Here's another non-iterative wording:

   Select the transitive subset of pairings which 
   minimizes excluded majorities.

I've written software to implement and compare many voting 
methods, and have found that when Tideman and Schulze are run 
alongside each other, the Tideman winner beats the Schulze 
winner pairwise far more often than vice versa, when the two 
methods are decisive and disagree.

Here's another criterion, possibly of little significance, which 
MTM/Tideman meets but Schulze fails.  (MTM/Tideman's compliance 
assumes the large election model in which there are no pairties 
nor equal majorities.)  This is probably the weakest meaningful 
variation of Arrow's IIAC:

   Independence from Least Relevant Alternative (ILRAC)
   ----------------------------------------------------
   Let M(A,V(A)) be the social ordering selected by the voting
   method M given a set A of alternatives and a set V(A) of
   voters' rankings of the alternatives in A.  Let S be the
   subset of A which excludes the bottom alternative in
   M(A,V(A)).  M is "independent from the least relevant
   alternative" if and only if the winner of M(S,V(S)) is 
   the same as the winner of M(A,V(A)), for any A and V(A).

ILRAC can be generalized:

   Subsequence Invariance criterion (SIC)
   --------------------------------------
   Let M(A,V(A)) be the social ordering selected by the voting
   method M given a set A of alternatives and a set V(A) of
   voters' rankings of the alternatives in A.   Let S be 
   the subset of A which excludes the top n and bottom m
   alternatives in M(A,V(A)).  M is "subsequence invariant" 
   if and only if the alternatives in S are ordered the same 
   in M(S,V(S)) as they are in M(A,V(A)), for any A, V(A), n,
   and m.

   (ILRAC is SIC with n=0 and m=1.)  

MTM/Tideman complies with SIC, and Schulze fails..

* *

Here's another good method which is not equivalent to Tideman or 
Schulze:

   Beatpath Criterion Method (BCM)
   -------------------------------
   For all pairs i&j,
      if Vij > Vji and Vij > Bji then eliminate j.

By itself, BCM isn't as decisive as we'd like.  But here's a 
variation which is quite decisive:

   Iterated Beatpath Criterion Method (IBCM)
   -----------------------------------------
   Repeat BCM, neglecting preferences regarding eliminated
   alternatives, until decisive or until further repetition
   won't eliminate more alternatives.

The same software which shows that Tideman's winner tends to 
beat the Schulze winner when the two methods disagree also shows 
that the IBCM winner tends to beat the Tideman winner pairwise 
when IBCM and Tideman disagree, and the IBCM winner tends to 
beat the Schulze winner pairwise when IBCM and Schulze disagree.


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