[EM] Fw: IBCM, Tideman, Schulze

Steve Eppley SEppley at alumni.caltech.edu
Fri Jun 2 18:12:51 PDT 2000


Norm P wrote, in reply to a private question from Markus S:
-snip-
> Here's a 4-candidate example showing different results for
> Tideman and IBCM. Note that there are no tied values anywhere
> within the matrix, so the result does not depend on the
> effects of a tiebreaker
-snip-
> Examples of this type occur fairly frequently in the
> simulations I've run which compare these methods.  However, it
> is an open question whether it is possible to create this or
> other similar examples using actual ballots.

[Sorry about the delay in my response to Norm's message.]

It's not really an open question.  My software generates voters' 
rankings (randomly), and turns up scenarios where IBCM & MTM 
(majoritarian Tideman) are decisive and disagree.  Here's an 
example which closes the question affirmatively:

   32 voters' rankings:    
   3: ABCD
   3: ABDC
   1: ADBC
   2: BADC
   1: BCAD
   2: BCDA
   2: CABD
   2: CBAD
   2: CBDA
   2: CDAB
   1: CDBA
   2: DABC
   2: DACB
   1: DBAC
   3: DBCA
   3: DCAB

   Majorities: AB18,CA18,DA18,BC18,BD17,DC17

   IBCM elects:    B
   MTM elects:     D
   Schulze elects: D

(Usually I configure my software to include a degree of 
indifference in the randomly generated rankings, but you can't 
tell that from this example.  I could just as easily have found 
an example where IBCM and MTM differ and preferences are not all 
strict.)

-snip-
> I have confirmed the result of Steve Eppley's simulation
> comparing the pairwise winners of Schulze, Tideman, and IBCM,
> which he announced to the list on February 23, 2000: 
> 
>>  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.

Furthermore, IBCM and MTM both have what appears to be a 
significant edge over Schulze in the head-to-head comparison, 
much larger than IBCM's edge over MTM.  

In a message being posted separately ("Head-to-head: Schulze vs. 
MTM") I have posted some raw data, calculated by my simulation 
software, which supports the contention that MTM dominates 
Schulze in the head-to-head comparison.

> To test this claim I wrote my own simulation (called
> 'rankPairwiseMethods' in VoteSim) which generates a series of
> 'Smith Matrices' of various sizes, and compares how often
> each method's winner pairwise-beats the winner chosen by every
> other method.  Since I wanted to apply this test to a large
> number of methods, I began by creating a pairwise matrix for
> the methods themselves.  For each trial, I computed each
> method's winner; if a method's winner beat another method's
> winner pairwise, it would get one 'vote' against the competing
> method. 

I'm curious about what Norm's software does when one or more of 
the methods are not decisive.  The stat that I implemented does 
not count scenarios in which either of the two methods being 
compared is indecisive.

In addition to counting numbers of scenarios, my software also 
calculates another stat, the average margin (when the two 
methods being compared are decisive and disagree).  It is 
possible that a method can do well when comparing the number of 
scenarios won to the number of scenarios lost, but do poorly 
when comparing the accumulated margin for its winners over the 
other method's winners.  I wouldn't expect this second stat to 
contradict the first stat when comparing a margins method to a 
margins method, or when comparing a majoritarian method to a 
majoritarian method, but it shouldn't cause a surprise if the 
second stat contradicts the first when comparing a margins 
method to a majoritarian method.  

> Once the simulation was complete, I determined a social
> ranking of all the methods using Tideman's method (somewhat
> arbitrary, but the result would be similar using any other
> approach).  My results for 3-10 candidate Smith sets are as
> follows (just for laughs I included Borda!): 

Since Borda and the PC(..) methods look outside the Smith set, 
perhaps those shouldn't be tested using a "Smith matrix."

> Trials:     20,000
> Voters:     100
> 
> Rank\Cands: 3             4             5             6
>      1      Schulze(m)    IBCM(av)      Copeland      Copeland
>      2      IBCM(m)       IBCM(wv)      IBCM(av)      IBCM(av)
>      3      Schulze(wv)   IBCM(m)       IBCM(wv)      IBCM(m)
>      4      IBCM(wv)      Tideman(wv)   IBCM(m)       IBCM(wv)
>      5      IBCM(av)      Tideman(av)   Tideman(m)    Tideman(m)
>      6      Schulze(av)   Tideman(m)    Tideman(wv)   Tideman(wv)
>      7      PC(m)         Copeland      Tideman(av)   Tideman(av)
>      8      Tideman(m)    Schulze(av)   Schulze(av)   Schulze(m)
>      9      Goldfish(m)   Schulze(wv)   Schulze(wv)   Schulze(wv)
>      10     SD(m)         Schulze(m)    Schulze(m)    Schulze(av)
>      11     SSD(m)        SSD(wv)       SD(wv)        SD(m)
>      12     PC(av)        SSD(av)       SSD(wv)       SSD(m)
>      13     Tideman(wv)   SD(av)        SSD(av)       Goldfish(m)
>      14     PC(wv)        Goldfish(wv)  Goldfish(wv)  SD(wv)
>      15     Goldfish(wv)  Goldfish(av)  SD(av)        SSD(wv)
>      16     SD(wv)        SD(wv)        Goldfish(av)  SSD(av)
>      17     SSD(wv)       SD(m)         SSD(m)        Goldfish(wv)
>      18     SSD(av)       Goldfish(m)   SD(m)         Goldfish(av)
>      19     Tideman(av)   SSD(m)        Goldfish(m)   SD(av)
>      20     Goldfish(av)  PC(av)        PC(m)         PC(m)
>      21     SD(av)        PC(wv)        PC(av)        PC(wv)
>      22     Copeland      PC(m)         PC(wv)        PC(av)
>      23     Borda         Borda         Borda         Borda
> 
> Rank\Cands: 7             8             9             10
-snip- 
> Comparing Schulze(wv), Tideman(wv) and IBCM(wv), we see that
> Steve's conclusion is correct for Smith sets of 4-10
> candidates.  Note though that this result does not hold for
> 3-candidate Smith sets, where Schulze produces better results
> than either IBCM or Tideman.  

I think Norm has erred significantly in the 3-candidate case.  
As Markus noted last year, given 3 candidates, Schulze and 
PC(wv) choose the same.  Yet we can see that Norm's 3-candidate 
column ranks PC(wv), MTM, and IBCM below Schulze.

And it is easy to show that, given 3 candidates, PC(wv) and BCM 
choose the same, and that the IBCM winner never loses to the 
PC(wv) winner, or to the Schulze winner, or to the MTM winner.  
Furthermore, given 3 candidates, PC(wv) and MTM choose the same.

So Norm's implementation must be flawed.  Schulze, MTM, and 
PC(wv) must tie in the 3-candidate stat.  IBCM either ties them 
or leads them in the 3-candidate stat, depending on whether 
indecisive scenarios are counted or neglected.

The way I've implemented the head-to-head comparison test, it 
only counts scenarios where the two methods being compared are 
decisive, needing no tie-breaker.  So in the 3-candidate 
comparison, the stat when comparing any two of {IBCM, MTM, 
Schulze, PC(wv)} is 0-to-0.  If I also counted indecisive 
scenarios (which would be rare in large public elections but not 
in committees) I believe IBCM would show an edge over Schulze in 
the 3-candidate case, due to scenarios where Schulze chooses two 
and IBCM chooses the pairwinner of Schulze's two. (For example, 
the scenario "BC52,CA51,AB51" where Schulze chooses A&B and IBCM 
chooses A.  When the Schulze tie is broken, it may choose B, 
which would count fractionally for IBCM head-to-head.)

So I stand by my conclusions: IBCM & MTM dominate Schulze on the 
head-to-head comparison.  Norm's result is probably based on 
different implementations of the voting methods than I use.  He 
may also count in his stats some differences when methods are 
indecisive, and if he does that then it remains to be seen 
whether he is doing it in a reasonable way.

I hope that if Norm runs his test again (after presumably 
correcting any bugs), he'll post the pairwise table generated by 
his software (or at least the portion for the best methods, 
since the table is large), not just a table of rankings derived 
from it.  That would reveal the magnitude of the head-to-head 
edge, and whether or not the tested methods cycle.

We can infer from Norm's message that he does not agree with 
Markus' objection that simulations based on random voting are 
meaningless.  Markus said that the use of random voting in 
simulations implies that my underlying model of voter behavior 
is that voters behave randomly, but that's not a logical 
conclusion.  People have at various times posted estimates of 
the percentage of scenarios which would have a Condorcet winner, 
using simulations involving randomness, but Markus has not 
criticized those estimates.  I think that the main argument why 
random generation is useful even though voters do not vote 
randomly is that, given a voting method which encourages 
competition (i.e., independence from "similar" alternatives) 
there would presumably be a number of similar viable candidates 
and a number of irrelevant candidates.  Preferences regarding 
similar candidates figure to be more random than votes regarding 
irrelevant candidates.  And there is no need to simulate 
irrelevant candidates.

> Therefore, in order to judge which method produces better
> results by this metric, it is necessary to know the relative
> frequency of Smith sets of various sizes that we might expect
> in an actual election. 

Not so, assuming Norm's 3-candidate column is flawed.

-snip-
> That said, I am not persuaded that this is a particularly
> important consideration -- if we thought this was an important
> factor in selecting a method, we would probably choose
> Smith//Copeland, since its results are even superior to those
> of IBCM.

Smith//Copeland is the same as Copeland.

I haven't tested Copeland, so I can't verify Norm's surprising 
Copeland result.  Maybe I will find time to add the Copeland 
method to my software's collection.

Since Copeland is so indecisive, and presuming that Copeland 
advocates will specify a reasonably deterministic tie-breaker 
(e.g., Copeland//Plurality, advocated by Bruce Anderson), a 
reasonable comparison requires evaluating Copeland with such a 
tie-breaker.  Norm hasn't specified what his software does when 
Copeland, or any other method, is indecisive.

Also, since Copeland neglects the vote counts in each pairing, 
I'd expect it wouldn't do nearly so well in my other head-to-
head stat which accumulates margins.

However, it's important to clear up a major misunderstanding 
apparently shared by Norm, Markus, and Blake due to my terseness 
about the purpose of the head-to-head comparison:  

The head-to-head comparison criterion is one among many 
criteria.  Criteria are not equally important.  I'm sure we 
agree that several criteria are more important than the head-to-
head comparison: feasibility, anonymity, neutrality, simplicity, 
monotonicity, resolvability, top cycle, independence from 
clones, pareto, etc.

Each reader must judge the relative importance of criteria.  The 
head-to-head comparison can serve to distinguish between methods 
which are not distinguished by any of the criteria the reader 
considers more important than the head-to-head comparison.

Some of us, including me, also consider Mike Ossipoff's 
defensive strategy criteria (Minimal Defense, Truncation 
Resistance, etc.) more important than the head-to-head 
comparison, and more important than some of the other criteria 
listed above.

I don't consider Beatpath GMC at all important: 

1. I see no justification for disqualifying a candidate who 
would not be disqualified if a few indifferent abstainers decide 
to express their indifference by voting.

2. I see no reason why we should accord more respect to a 
"majority strength beatpath" abstraction than to the real 
plurality of voters who prefer a candidate rejected by Beatpath 
GMC more than the Schulze winner.  Consider this example:

   Majorities:  BD65,DC64,CB63,AF62,FE61,CF52,EA51,AB49
   (All other pairings are ties.)
   MTM & IBCM elect A.  Schulze elects B.
   
   There is a "majority strength beatpath" from B to A:
   BDCFEA has strength 51.

   But in what sense of "majority" can it be said that a
   majority has "rejected" A, without also being able to say
   a majority has "rejected" B?  A's only defeat is EA51,
   which is shaky (smallest majority in a cycle).  Compare
   that to B's CB65 defeat, which isn't counted against B.
   (Blake Cretney made a similar analysis of this issue
   on 1/24/2000, noting that the Schulze method neglects
   "extra" information contained in the votes which may
   undermine links in a beatpath chain.  Markus considers
   this neglect a "feature" of the Schulze method, but it
   makes sense to view it as a minor bug.)

   An argument might be made that a beatpath is not just an
   abstraction, that it is comprised of real voters too.
   But that's a dubious argument.  Consider this simple
   scenario to illustrate:
      35: ABC
      33: BCA
      32: CAB
      Majorities: BC68,AB67,CA65
   The strongest beatpath of length two or more is ABC67.
   Who are the "real voters" counted in the ABC beatpath?
   The AB67 link includes 32 voters who rank C over A, and
   the BC68 link includes 33 voters who rank C over A.  The
   strength of a beatpath depends on voters who would oppose
   the beatpath, and thus are not real voters. (This sort of
   example is one of the concerns I have about how hard it may
   be to convince people about the merits of the Schulze method,
   because there's something "smelly" about counting for a
   beatpath some voters who oppose the beatpath.)

3. Markus has written that he deems a criterion inferior if 
there exists a stronger criterion such that satisfaction of the 
stronger one does not imply failure of some other desirable 
criterion which can be satisfied when the weaker one is 
satisfied.  Consider the following criterion, stronger than 
Beatpath GMC, which I mentioned a couple of weeks ago. (At that 
time I proposed calling it the "Schulze" criterion, but since 
Markus hasn't yet accepted it I'm calling it the "Stronger 
Beatpath" criterion here.)

   "Strongest beatpath":  For all alternatives x&y, if there is
   at least one beatpath from x to y, let S(x,y) equal the
   strength of the strongest beatpath from x to y;
   else let S(x,y) equal zero.

   Stronger Beatpath criterion:  For all alternatives x, 
   if there exists an alternative y such that S(y,x) > S(x,y),
   then x must not be chosen.

Stronger Beatpath is stronger than Beatpath GMC because its 
satisfaction clearly implies satisfaction of Beatpath GMC. 
Unless there is some desirable criterion whose satisfaction is 
lost by requiring satisfaction of Stronger Beatpath, but which 
can be satisfied along with Beatpath GMC, then Beatpath GMC 
should be deemed an inferior criterion and we should discard it. 
Instead, use Stronger Beatpath -- if you don't think it's overly 
broad. (In particular, Markus should cease using Beatpath GMC, 
if he wants to be consistent about preferring to use the 
stronger criterion.)

(A note to anyone who may be logic-challenged: In my opinion, 
both Stronger Beatpath and Beatpath GMC are overly broad.  Just 
because I've defined a criterion does not imply that I advocate 
it.)

* *

Here's another criterion which might not be considered very 
important.  But it seems desirable and it distinguishes between 
MTM and Schulze:

   Define the "1st place finisher" as the given method's winner.
   Define the "Nth place finisher" as the alternative which
   would be chosen by the given method if preferences for the
   1st thru (N-1)th place finishers were neglected.

   Immunity From Squawking criterion:  The 2nd place finisher
   must never beat the winner pairwise.

Another criterion which distinguishes between MTM and Schulze is 
the Subsequence Invariance criterion I posted in February (which 
Markus kindly informed us was not original, indicating there are 
other people who place some value on it).  

There is a weaker form of Subsequence Invariance which Schulze 
also fails: "The outcome must not change if preferences for the 
last place finisher are neglected."  Assuming that a candidate 
who expects to finish last has the least incentive to compete, 
it would be nice if the outcome is unaffected by his/her 
decision whether or not to compete.  Thus, this appears to be a 
desirable criterion (though it might not be considered very 
important).

> It is likely that a method has to sacrifice some of the
> desirable properties of Schulze's method in order to do
> better here.

I don't believe MTM (majoritarian Tideman) sacrifices any 
desirable property.  More on this below.

> Smith//Copeland, for example almost certainly violates clone
> criteria, 

Correct: Copeland (which is the same as Smith//Copeland) is not 
independent from clones.  Consider 3 alternatives {x,y,z} which 
cycle.  Each has a 1-1 record so the Copeland outcome depends on 
the tie-breaker.  Assume x wins via the tie-breaker (perhaps 
without resorting to randomness, depending on the tie-breaker).  
Add a clone of y.  Then add a clone of z.  After both clone 
additions, x's record is 2-2, but there is some other 
alternative with a 3-1 record (or at least a 2.5-1.5 record).  
So, the outcome changed from x, either when the second clone was 
added or when the first clone was added.  Whether it changed 
after the second addition or after the first is irrelevant, 
since both cases are violations of independence from clones.

> whereas Schulze's method is the only method (that I'm aware
> of) that has been proven to satisfy one strong formulation of
> Clone Independence criteria. Tideman satisfies a weaker
> definition of clone independence, SD is 'mostly' clone
> independent, but fails in rare cases;  

I'm not aware that IBCM or Tideman fail to satisfy the stronger 
form of clone independence.  I do recall that a couple of years 
ago there was a discussion in EM about Tideman, which didn't use 
the RandomVoterHierarchy tie-breaker discussed later for 
Schulze's method.  Also, that discussion may have been about 
Tideman's 1987 version, not the better version defined in Zavist 
& Tideman's paper, "Complete Independence of Clones in the 
Ranked Pairs Rule." (Social Choice and Welfare, 1989).  If 
RandomVoterHierarchy is the tie-breaker, aren't IBCM and MTM 
completely independent from clones, in whatever "strong" 
formulation Norm referred to?

Markus tweaked Tideman's definition of clones and demonstrated 
independence of "tweaked" clones of the Schulze method.  But 
that tweak was not a strengthening of the independence 
criterion.  It was a weakening.  It seems to me that MTM and 
Tideman and BCM and IBCM completely satisfy it (when coupled 
with a tie-breaker such as RandomVoterHierarchy which completely 
satisfies it).

I'd like to see an example showing incompleteness of the clone 
independence of Tideman//RandomVoterHierarchy, if there is one.  
(Preferably an example for the majoritarian version of Tideman.)

> IBCM and Tideman both violate Beatpath GMC, etc. 

Why place any importance on Beatpath GMC?  It's a criterion 
lacking a reasonable justification -- see above.  Mike Ossipoff, 
the "father" of GMC, has repudiated both GMC and Beatpath GMC, 
concluding that they are overly strong.

It's hard to guess what Norm had in mind by the "etc."  Perhaps 
he meant Mike Ossipoff's GMC.

> I think that IBCM needs further study before it can be
> considered the equal of our best methods.  Some questions
> that need to be answered are: 
> 
> 1) does IBCM satisfy clone criteria?

Yes, to the best of my knowledge.  In a message I'm posting 
separately, I've written a number of definitions, lemmas, and 
propositions (awaiting peer-review confirmation that I haven't 
made mistakes) which are of general use for proofs regarding 
clone independence, tie-breaking, and a few other properties of 
voting methods.  Assuming their validity, the proof of complete 
clone independence for IBCM//RandomVoterHierarchy is fairly 
simple: all that remains is to prove is that BCM is partially 
independent of clones.  The proof for BCM is provided here.

   Refer to the definitions in the accompanying message
   "Useful Propositions re: clones & tie-breaking."

   Definition of BCM:  For all A, all V, and all Z such that
   Z is a non-empty subset of A, BCM(Z,V) is the set of
   alternatives {x in Z such that there is no y in Z
   such that [B(y,x) and #(y,x) > S(x,y,Z)]}.

   Equivalent definition of BCM:  For all A, all V, and
   all Z such that Z is a non-empty subset of A, BCM(Z,V) is
   the set of alternatives {x in Z such that there is no y in Z
   such that [B(y,x) and there is no C in Cycles(Z)
   such that (y,x) is in Smallest(C)]}.

The equivalence of the two BCM definitions can be seen by noting 
that appending x to the end of a chain from x to y makes a cycle 
in which y immediately precedes x; thus the (y,x) majority is a 
majority of that cycle.  BCM's "chain" wording can be rewritten 
to make the equivalence more obvious: "... {x in Z such that 
there is no y in Z such that [B(y,x) and there is no chain C in 
Z from x to y such that #(y,x) is less than or equal to the 
strength of C's weakest link]}."

   Definition of IBCM:  IBCM = [BCM].

Proposition "BCM1":  BCM is a correspondence.

Proof: The only condition in the definition of correspondence 
which is not obviously satisfied by BCM is that it must always 
choose at least one alternative in Z.  The following argument 
establishes, by contradiction, that BCM always chooses at least 
one alternative in Z:

Suppose the contrary, that for some A, some V, and some Z which 
is a non-empty subset of Z, BCM(Z,V) is empty.  This means that 
for all x in Z there exists y in Z such that [B(y,x) and there 
is no C in Cycles(Z) such that (y,x) is in Smallest(C)].  An 
inductive argument will establish a contradiction:  Begin by 
picking one alternative in Z arbitrarily and label it x1.  By 
assumption there must be another alternative in Z, label it x2, 
such that [B(x2,x1) and there is no C in Cycles(Z) such that 
(x2,x1) is in Smallest(C)].  Similarly, there must be an x3 in Z 
such that [B(x3,x2) and there is no C in Cycles(Z) such that 
(x3,x2) is in Smallest(C)].  Let X = x1x2x3... denote such an 
infinite sequence, defined such that, for all integers k>0, 
[B(xk+1,xk) and there is no C in Cycles(Z) such that (xk+1,xk) 
is in Smallest(C)].  Since Z is finite, at least one alternative 
must appear at least twice in X.  So without loss of generality 
let i & j denote two distinct indices in X of some alternative 
appearing at least twice in X, where 1 <= i < j <= |Z|+1.  That 
means that the reversal of a subsequence of X, xj..xi, is a 
cycle and is in Cycles(Z).  That is a contradiction, since at 
least one (xk+1,xk) majority, where i <= k < j, is in 
Smallest(xj..xi).  The contradiction refutes the contrary 
assumption, so BCM must always choose at least one alternative 
in Z.                                                        QED

Proposition "BCMPIC":  BCM is partially independent of clones.
Proof:  Suppose Y is a clone set in A, and suppose Y0 is a 
strict subset of Y.  We need to establish both of the following:

   (A\Y)^BCM(A,V) = (A\Y)^BCM(A\Y0,V).                       (1)
   Y^BCM(A,V) is empty iff Y^BCM(A\Y0,V) is empty.           (2)

The left side of (1) is the set {x in A\Y such that there is no 
z in A such that [B(z,y) and #(z,x) > S(x,z)]}.  The right side 
of (1) is the set {x in A\Y such that there is no z in A\Y0 such 
that [B(z,y) and #(z,x) > S(x,z,A\Y0)]}.  The equality of these 
two sets follows from lemma "Y#B=", lemma "YS=", lemma "XX'", 
and lemma "XY0".

An equivalent argument establishing (1) may be made using the 
equivalent definition of BCM:  The left side of (1) is the set 
{x in A\Y such that there is no z in A such that [B(z,y) and 
there is no C in Cycles(A) such that (z,x) is in Smallest(C)]}.  
The right side of (1) is the set {x in A\Y such that there is no 
z in A\Y0 such that [B(z,y) and there is no C in Cycles(A\Y0) 
such that (z,x) is in Smallest(C)]}.  The equality of these two 
sets follows from lemma "Y#B=", lemma "YSm=", lemma "XX'", and 
lemma "XY0".

To establish (2) we must consider two cases:

Case 1: For some y in Y there exists x in A\Y such that [B(x,y) 
and #(x,y) > S(y,x)].

   Let x denote such an alternative in A\Y; that is, for some y
   in Y, [B(x,y) and #(x,y) > S(y,x)].  By lemma "Y#B=" and
   lemma "YS=", the following holds:
      For all y in Y, [B(x,y) and #(x,y) > S(y,x)].
   Thus Y^BCM(A,V) is empty.  By lemma "XY0", Y^BCM(A\Y0,V)
   must also be empty.  So (2) is established in case 1.

   Case 1 could have been equivalently written as:
   Case 1':  For some y in Y there exists x in A\Y such that
   [B(x,y) and there is no C in Cycles(A) such that (x,y) is
   in Smallest(C)].
   Case 1' can be established in a manner analogous to case 1:
   Let x denote such an alternative in A\Y; that is, for some y
   in Y, [B(x,y) and there is no C in Cycles(A) such that (x,y)
   is in Smallest(C)].  By lemma "Y#B=" and lemma "YSm=", the
   following holds:
      For all y in Y, [B(x,y) and there is no C in Cycles(A)
      such that (x,y) is in Smallest(C)].
   Thus Y^BCM(A,V) is empty.  By lemma "XY0", Y^BCM(A\Y0,V)
   must also be empty.  So (2) is established in case 1'.

Case 2: For all y in Y there exists no x in A\Y such that 
[B(x,y) and #(x,y) > S(y,x)].

   We want to show that neither Y^BCM(A,V) nor Y^BCM(A\Y0,V)
   is empty, which will establish (2) in case 2.
   By lemma "XY0", there exists no x in A\Y such that
   [B(x,y) and #(x,y) > S(y,x,A\Y0)].
   Thus, a particular clone is chosen if and only if there
   is no clone which eliminates it.  That is,
      Y^BCM(A,V) = {y in Y such that there is no y' in Y
      such that [B(y',y) and #(y',y) > S(y,y')]}.            (3)
   And,
      Y^BCM(A\Y0,V) = {y in Y\Y0 such that there is no y' in
      Y\Y0 such that [B(y',y) and #(y',y) > S(y,y',A\Y0)]}.  (4)
   The argument that neither of these sets is empty parallels
   the inductive argument in the proof of proposition "BCM1"
   above (i.e., that BCM never chooses the empty set):
   Rewrite (3) and (4) using the equivalent definition of BCM
   in terms of cycles:
      Y^BCM(A,V) = {y in Y such that there is no y' in Y
      such that [B(y',y) and there is no C in Cycles(A)
      such that (y',y) is in Smallest(C)]}.                   (5)
      Y^BCM(A\Y0,V) = {y in Y\Y0 such that there is no y'
      in Y\Y0 such that [B(y',y) and there is no C in
      Cycles(A\Y0) such that (y',y) is in Smallest(C)]}.      (6)
   Then suppose to the contrary that one of the sets defined
   by (5) or (6) is empty.  Then there must be an infinite
   sequence X = y1y2y3... such that, for all integers k>0,
   [B(yk+1,yk) and there is no C in Cycles(A) (or in
   Cycles(A\Y0), depending on which set we're focussing on)
   such that (yk+1,yk) is in Smallest(C)].  Since Y is finite,
   there must be at least one alternative which appears at least
   twice in X, so there must be a pair of distinct indices i&j
   where yi=yj and 1 <= i < j <= |Y|+1.  But then the reversal
   of yi...yj, yj...yi, is a cycle (in Cycles(A) or in
   Cycles(A\Y0), depending on which set we're focussing on)
   and at least one of the (yk+1,yk) majorities (i <= k < j)
   must be in Smallest(yj...yi), a contradiction.

Thus (2) has been established in both cases.

Since (1) and (2) have been established, BCM must be partially 
independent of clones.                                       QED

Lemma "IBCM1":  IBCM is a correspondence.
Proof follows by inspection of the definition of IBCM, the 
definition of [], proposition "BCM1", lemma "GR", and lemma 
"r'|Z|".

Lemma "IBCMPIC":  IBCM is partially independent of clones.
Proof follows from the definition of IBCM, the definition of [], 
proposition "BCM1", proposition "BCMPIC" and lemma "[]PIC".

Lemma "IBCMCIC":  IBCM//RandomVoterHierarchy is a single-winner 
voting rule which is completely independent of clones.
Proof follows from lemma "IBCM1", lemma "IBCMPIC", lemma 
"RVHCIC", and lemma "GFCIC".

So, assuming no significant errors have been made in the lemmas 
or the propositions, it is accurate to say that IBCM is 
completely independent of clones (recognizing that a tie-breaker 
which is completely independent of clones is implied by the 
claim).

> 2) is IBCM monotonic? (Markus suggested that it might not be)

No, IBCM is not completely monotonic. (BCM is monotonic, but no 
one is advocating BCM.  Proof of BCM monotonicity is available 
upon request.)

Markus wrote that I claimed IBCM is monotonic, but I believe 
I've never claimed that. (I reread the messages I've posted 
which mention BCM, and didn't find such a claim.  Perhaps he 
will provide a quote of the alleged claim?)

   Example of IBCM non-monotonicity:
   6 alternatives {A,B,C,D,E,F}
   Majorities: DF69,DE68,CF67,CE66,CD65,BF64,BD63,AF62,
               AE61,FE60,EB57,DA56,CB55,AC54,BA52

   IBCM elects A.  Assume there are at least 4 voters who
   ranked A immediately below C.  Suppose that now 4 of those
   uprank A over C, increasing the AC majority from 54 to 58.
   Then IBCM elects B.  (I omit the details.)

I discovered IBCM's non-monotonicity a few days after Markus 
asked whether it's monotonic, while attempting to answer his 
question. (Obviously, my attempt to prove monotonicity ran into 
trouble since it's not monotonic. :-)  I planned to post a 
message about this after the Tideman vs. Schulze debate is 
wrapped up.  But Mike Ossipoff brought to my attention that Norm 
also asked about it, suggesting that I post this right away.

It may be reasonable to claim that IBCM is "nearly" monotonic. 
To show IBCM non-monotonicity in the large election model (which 
assumes no pairties and no equal size majorities) it appears 
that at least 6 alternatives are required.  This is more than 
the number of alternatives needed to show most non-monotonic 
methods are non-monotonic.  

However, I'm sensitive to the possibility that any violation of 
a widely-accepted criterion, even if the violation is minor or 
unlikely, could undermine the election reform effort since the 
campaign for reform will likely be poorly funded compared to the 
anti-campaign.  That would make it hard to rebut criticism even 
though the rebuttal may be reasonable, since people wouldn't 
hear it.  (That's why I prefer TopCycle//PC(wv) more than 
PC(wv); though PC(wv) is simpler and should perform well, it's 
subject to criticism due to its failure to completely satisfy 
top cycle, Condorcet loser, and clone independence.)

So it makes sense to lower IBCM and consider MTM #1.  For one 
thing, like IBCM, MTM has a significant edge over Schulze in the 
head-to-head comparison.  (See my data above.)

Also, MTM has a brief description: "Elect the leader of the 
ranking which minimizes thwarted majorities."  That seems much 
simpler than any other excellent method's brief description 
because it doesn't refer to cycles or beatpaths.  It refers to 
more familiar terms.  The definition of "thwarted" majority is 
quite intuitive: If more voters ranked x over y than vice versa 
but x doesn't finish over y, we say that the majority who ranked 
x over y is thwarted.

-snip-
> I have expressed doubts in the past about how explainable
> Schulze's method would be to members of the general public. 

Yes, Norm is one of the people I had in mind when I wrote a 
couple of weeks ago that some people in EM have written they 
think it may be too hard to explain Schulze's method.

Markus noted, shortly after, that I didn't specify who I had in 
mind (to suggest I was lying?).  Markus pointed out Blake and 
Mike as examples of people who understand Schulze's method, 
clearly missing the point that our concern is about members of 
the general public who don't study voting methods but would be 
asked to decide whether to change their voting method.

> This problem is compensated for by the method's technical
> excellence.  As an iterative method, IBCM is much less elegant
> than Schulze's method, and is no easier to explain.

That's debatable, because IBCM can be defined in a way which is 
fairly simple.  Mike Ossipoff, using the name DCD for IBCM, has 
written that he considers IBCM fairly easy to explain.  Here's a 
fairly simple description:

   Neglecting defeats which are smallest in a cycle (therefore
   shakiest), eliminate all beaten alternatives.  Repeat,
   neglecting eliminated alternatives, until further repetition
   would eliminate no more.

(Of course, that requires an explanation of cycles, if intended 
for a general audience.)

As for elegance, I agree that IBCM is less elegant than 
Schulze's method when written in terms of beatpaths, but not 
when written in terms of cycles.  Then they seem about 
equivalent in elegance.  True, IBCM requires defining 
repetition, but that is intuitive.  Schulze has inelegant 
baggage too, regarding the definition of the strength of the 
strongest beatpath from x to y when there is no beatpath from x 
to y. (Of course, that too is intuitively zero.)

MTM is quite elegant and appears easiest to explain.

> I think Tideman and SD (and perhaps SSD) may not be as good
> technically, but are all somewhat more intuitive, and
> therefore might make better public proposals than Schulze (or
> IBCM). 

I think Norm has misjudged Tideman technically on clones. (See 
above.)  Also, I think there is no reasonable justification for 
Beatpath GMC. (See above.)  So MTM (majoritarian Tideman) is 
better than Norm has suggested. 

I agree with Norm's conclusion that Tideman (more specifically, 
MTM) and SD might make better public proposals than Schulze.  

SD & SSD are not completely independent of clones, but I think 
they are practically independent in large public elections.  I 
think SD is not completely monotonic (example below) but is 
practically monotonic.  I don't know if SSD is completely 
monotonic, but below I provide an argument against proposing SSD.

It would also be useful to know whether [Schulze] & [MTM] are 
monotonic, since [MTM] is more decisive than MTM, and [Schulze] 
is more decisive than Schulze.  (The [] notation is defined in 
the accompanying message "Useful Propositions...")

Here's an example which, if I haven't erred, shows that SD is 
not completely monotonic:

   Definition of SD:
   Repeat while no alternative is unbeaten:
      Discard the non-discarded defeat(s) which is smallest
      in some unbroken cycle.
   Elect the unbeaten alternative(s).

   Example of SD non-monotonicity:
   Small majorities:  AC51,CB52,BA53,DB53,GA54
   Larger majorities: AD,FC,CE,EF,AH,HG
   (All other pairings are pairties.)

   First AC51 is dropped.  Then BA53 and DB53 are dropped.
   (CB52 is not dropped because the cycle it is in was broken
   by the dropping of AC51.)  Then GA54 is dropped and A has
   become unbeaten, so SD chooses A.

   Assume that at least 3 voters ranked A just below C.
   Suppose 3 of them uprank A over C, giving AC54.
   Now AC is not the smallest majority of any cycle;
   CB52 is the smallest majority of the A>C>B>A cycle.
   First CB52 is dropped.  Then BA53 and DB53 are dropped
   and B has become unbeaten, so SD chooses B.

   (I didn't attempt to find an example having fewer
   alternatives or fewer pairties.)

SD's definition says that cyclicity is recalculated each 
iteration, to identify the "unbroken" cycles.  Another method 
can be defined which is similar to SD, except that it calculates 
cyclicity only once, at the beginning:

   Definition of SD2:
   Repeat while no alternative is unbeaten:
      Discard the non-discarded defeat(s) which is smallest
      in some broken or unbroken cycle.
   Elect the unbeaten alternative(s).

SD2 may be worth examining.  I expect it will behave similarly, 
but not identically, to TopCycle//PC(wv), and it is probably 
monotonic.  It clearly satisfies top cycle, and perhaps it 
performs as well as SD on clones (practical independence of 
clones in large public elections.)

It would be advantageous if the method proposed for large public 
elections is also the method proposed for small groups.  It will 
probably be the case that some private groups would choose to 
adopt a good method before it's adopted by the public, and would 
then spread knowledge about their experiences with it.  So there 
may be useful synergies if the same method is proposed for both. 
This consideration implies that IBCM & SD, which are not as good 
for small groups, should not be the public proposal.  This 
leaves MTM, Schulze, and perhaps SSD.  (Also [MTM] and [Schulze] 
since they are more decisive, assuming they are monotonic, and 
maybe even if they're not completely monotonic since the extra 
decisiveness may be more important in small groups.)

SSD's definition doesn't seem nearly as simple as other methods, 
since it refers to the (dynamically recalculated) Schwartz set.  
Given that plus its iteration, people may find SSD hard to 
understand, maybe even harder than Schulze, and if that's true 
then SSD offers nothing Schulze doesn't offer.  Mike said that 
he found a person who liked SSD's definition more than SD's, but 
that's not a large enough sample to reach a conclusion.


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



More information about the Election-Methods mailing list