[EM] Tideman and GMC

[Markus Schulze]

Dear Steve,

you wrote (23 Feb 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.

So you disagree with Mike Ossipoff's Tideman bad example.
But do you agree with my Tideman bad example (3 Feb 2000)?

You wrote (23 Feb 2000):
> 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.

T.M. Zavist and T.N. Tideman wrote ("Complete Independence
of Clones in the Ranked Pairs Rule," Social Choice and
Welfare, vol. 6, p. 167-173, 1989):
>      The ranked pairs rule can be defined algorithmically
> as follows: Define M(x,y) as the difference between the
> number of voters who rank x ahead of y and the number who
> rank y ahead of x. Given voters' rankings of an agenda, A,
> consider the set of unordered pairs of distinct candidates
> in A. Define a ranking, T, of that set of pairs, by the
> rule that {x,y}T{u,v} if and only if |M(x,y)|>|M(u,v)|.
>      If |M(x,y)|=|M(u,v)| then {x,y} is tied with {u,v}
> according to T. For x,y elements of A with M(x,y)>0, and
> P a complete ranking of the candidates in A, define P to
> "describe" the pair {x,y} if and only if xPy.
> To implement the algorithm for the ranked pairs rule,
> consider all possible complete rankings of A. Eliminate
> the complete rankings that do not describe the first and
> second pairs in T. When one reaches the third and
> subsequent pairs, it is possible that none of the
> remaining complete rankings describe that pair. In that
> case, ignore that pair and proceed to the next. Continue
> until just one complete ranking of the candidates remains.
> The winner under the ranked pairs rule is the candidate
> at the top of that ranking.
>      If there are one or more ties in T then, whenever
> q of the pairs are tied with the same majority and none
> of the remaining complete rankings describe all of the
> tied pairs, consider each of the q! ways of breaking the
> tie. For each way of breaking that and any subsequent
> ties, there will be a final complete ranking of the
> candidates. The election is a tie among all candidates
> that are at the top of a complete ranking that the
> algorithm generates for some way of breaking the ties
> among pairs. If the majority for any pair is 0 and the
> algorithm proceeds to the point where majorities of
> 0 would be considered, then all remaining complete
> rankings, and all candidates that head them are winning
> candidates.

You wrote (23 Feb 2000):
> 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).

That's the so-called "Increasing Sequential Independence" which can
be found e.g. in "Social Choice and Multicriterion Decision-Making"
by Kenneth Joseph Arrow and Herve Raynaud (MIT Press, 1986).

"Decreasing Sequential Independence" means that if the winner is
excluded then the ranking of the remaining candidates isn't
changed.

You wrote (23 Feb 2000):
> 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.

In so far as the task of an election method is to find the
best guess for best _candidate_ and not the best guess
for best _ranking_, your argument is quite meaningless.

You wrote (23 Feb 2000):
> 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.

You wrote (26 Feb 2000):
> 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."

Please read my mails more carefully. I wrote (29 Jan 2000):
> 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.

If you think that my terminology is misleading, then I want you to
remember that it is Blake Cretney who introduced the term "Sincere
Absolute Condorcet Winner" (24 Jan 2000).

You wrote (26 Feb 2000):
> 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.

I didn't count on you. I know that you hate me because I have
criticized your just in time withdrawal option.

You wrote (26 Feb 2000):
> 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.

I don't think that Mike Ossipoff needs you to speak for him.

You wrote (26 Feb 2000):
> 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.

And neither do I.

By the way: I don't think that Mike Ossipoff needs you to speak
for him.

You wrote (26 Feb 2000):
> 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.

Please read my mails more carefully. I wrote (29 Jan 2000):
"Why should I relax a given criterion if this given criterion
is compatible to all other desired criteria?" In other words:
A given criterion should be relaxed only if this criterion is
not compatible with another desired criterion.

Do you think that your criteria #1 and #2 are desirable?

You wrote (26 Feb 2000):
> Blake C. wrote:
> > 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.

It is always very amusing when somebody criticizes a given election
method so vehemently and simultaneously proposes another election
method that is almost identical and that is based on the same idea
(here: beat paths).

In so far as until recently your favourite election methods were
JITW//plurality, JITW//IRO and JITW//MinMax, I have convinced you
of almost everything I wanted to convince you. Remember that it is
me who introduced the Tideman method, beat paths, reversal
symmetry and clones to this mailing list. If I didn't do that, then you
would still discuss with Mike Ossipoff ad infinitum whether the
MinMax method or the Copeland method is the best method.
Therefore your accusations are rather unintelligible.

Markus Schulze