[EM] Fw: IBCM, Tideman, Schulze
Norman Petry
npetry at cableregina.com
Sat May 27 17:47:34 PDT 2000
In a private e-mail sent to me on May 24th, Markus Schulze wrote:
>
>I couldn't create an example where the IBCM winner
>differs from the Tideman winner. But in so far as Steve
>wrote that the IBCM winner pairwise beats the Tideman
>winner more often than vice versa, there must be
>situations where the IBCM winner differs from the
>Tideman winner.
>
>In so far as you have made simulations with randomly
>generated voter rankings and in so far as you know
>Steve's simulations, you seem to me to be able to
>check a very large number of examples in a short time
>whether the IBCM winner differs from the Tideman
>winner in this example. Therefore I want to ask you
>to send me such an example where these two winners
>differ.
>
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:
100 Voters.
A>B 60:29
A>D 46:32
B>C 49:38
C>A 73:21
D>B 48:11
D>C 40:28
Under Tideman, this gives:
Lock C>A 73 (C>A)
Lock A>B 60 (C>A>B)
Skip B>C 49
Lock D>B 48 (C>A>B; D>B)
Lock A>D 46 (C>A>D>B)
Skip D>C 40
The Tideman(wv) winner is C.
To calculate the IBCM winner we first calculate beatpaths:
A>>B 60:49
C>>A 73:49
C>>B 60:49
D>>A 48:46
D>>B 48:46
D>>C 49:46
then:
A>B, A>B' 60:49 -> B loses
C>A, C>A' 73:49 -> A loses
D>B, D>B' 48:46 -> B loses
eliminating A, B the problem reduces to:
D>C 40:28
Therefore, the IBCM(wv) winner is D.
The Schulze(wv) winner is also D in this example.
*****
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. The
routine I used to find this example begins with a "Smith Matrix", which is
just a pairwise matrix of randomly determined values having the following
properties:
1) the vote total for each pair of candidates is <= the number of voters.
2) all the candidates are members of the Smith set.
This approach was taken because all these methods are Smith-compliant, and
large Smith sets occur very rarely in actual elections. I did try to find a
5-candidate example similar to the above using actual ballots, but was
unsuccessful (20,000 trials). This is not really surprising, however
considering that the actual ballots would produce a 3-5 candidate Smith set
about 3% of the time. Of these, less than 1% would show a difference in
result between IBCM and Tideman, and these cases will probably often contain
ties. Therefore, it might be easier to work backwards from this example to
see if a set of ballots can be constructed for it.
******
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.
>
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. 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!):
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
1 Copeland Copeland Copeland Copeland
2 IBCM(av) IBCM(av) IBCM(av) IBCM(wv)
3 IBCM(wv) IBCM(wv) IBCM(wv) IBCM(av)
4 IBCM(m) IBCM(m) IBCM(m) IBCM(m)
5 Tideman(m) Tideman(m) Tideman(wv) Tideman(wv)
6 Tideman(wv) Tideman(wv) Tideman(av) Tideman(m)
7 Tideman(av) Tideman(av) Tideman(m) Tideman(av)
8 Schulze(wv) Schulze(av) Schulze(wv) Schulze(av)
9 Schulze(av) Schulze(wv) Schulze(av) Schulze(wv)
10 Schulze(m) Schulze(m) Schulze(m) Schulze(m)
11 SD(wv) SD(av) SD(m) Goldfish(av)
12 SSD(wv) Goldfish(av) Goldfish(m) Goldfish(wv)
13 SSD(av) SD(wv) SSD(m) SD(av)
14 SSD(m) Goldfish(wv) SD(wv) SD(wv)
15 SD(m) SSD(wv) SD(av) SSD(wv)
16 Goldfish(wv) SSD(av) SSD(wv) SSD(av)
17 Goldfish(m) SD(m) SSD(av) Borda
18 SD(av) Goldfish(m) Goldfish(wv) SD(m)
19 Goldfish(av) SSD(m) Goldfish(av) PC(av)
20 PC(m) PC(av) Borda PC(wv)
21 PC(wv) PC(wv) PC(m) SSD(m)
22 PC(av) PC(m) PC(wv) Goldfish(m)
23 Borda Borda PC(av) PC(m)
******
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. 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.
Here is the distribution of Smith set sizes I found for 25,000 10-candidate
elections:
Smith Size Frequency Frequency% Trials: 25,000
1 21541 86.16% Candidates: 10
2 540 2.16% Voters 100
3 726 2.90% Involvement: 0.5
4 745 2.98% Dimensions: 1
5 566 2.26%
6 384 1.54%
7 231 0.92%
8 151 0.60%
9 94 0.38%
10 22 0.09%
Total: 25000 100.00%
This result is about what one would expect -- a gradual tapering of
frequency as Smith set size increases. There is a Condorcet winner 86% of
the time in this example, and the frequency of 2-candidate smith-sets is low
since they can only occur if there is a pairtie between two winners.
Since 3-candidate Smith sets occur about 3% of the time, and larger Smith
sets will be observed 7-9% of the time, there may be some benefit to
choosing IBCM or Tideman over Schulze on the basis of this metric alone.
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. It is likely that a method has to sacrifice some
of the desireable properties of Schulze's method in order to do better here.
Smith//Copeland, for example almost certainly violates clone criteria,
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; IBCM and Tideman
both violate Beatpath GMC, etc.
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?
2) is IBCM monotonic? (Markus suggested that it might not be)
Even if a satisfactory answer can be found for these questions, I am
doubtful that I would adopt IBCM as my preferred method. I have expressed
doubts in the past about how explainable Schulze's method would be to
members of the general public. 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. 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).
Norm Petry
p.s. I regret being unable to participate in some of the interesting
discussions that have taken place here on EM in the last couple of months --
things are very busy here! Unfortunately, this problem is likely to
continue for a while, so I may not be able to do more than lurk for the next
few weeks. Hopefully I'll have time to participate more fully when things
ease up here later in the summer.
N.
More information about the Election-Methods
mailing list