[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