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

Steve Eppley SEppley at alumni.caltech.edu
Wed Feb 23 12:37:29 PST 2000

```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

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)

```