[EM] PC, Tideman & Schulze - Winner Comparison

[Norman Petry]

Dear Markus,

I have carried out the simulation you requested:

>let's say that X is the PC winner, Y is the Tideman winner
>and Z is the Schulze winner. In so far as you have made
>simulations, I want to ask you to post to the EM list the
>following details:
>
>1) In how many cases are X and Y the same candidate and
>   Z a different candidate?
>2) In how many cases are X and Z the same candidate and
>   Y a different candidate?
>3) In how many cases are Y and Z the same candidate and
>   X a different candidate?
>4) In how many cases are X, Y and Z three different
>   candidates?
>5) In how many cases are X, Y and Z the same candidate?

Since all three methods of interest satisfy the Condorcet criterion, using
individual ballots and a full spatial analysis would be very time consuming,
and the result would not do a good job of highlighting the differences
between the three methods.  Therefore, rather than simulating 'Plain
Condorcet' (Minimax(wv)), I substituted Smith//Minimax(wv).  This allowed me
to compare the methods using artificially constructed 'Smith Matrices' of
various sizes, rather than simulating full elections (for which all three
methods almost always choose the same winner (>95%).  Tideman and Schulze
will of course only differ in their choices from among the Smith set (since
they are both Smith compliant).  The results for PC would differ more from
both Tideman and Schulze than Smith//PC, but otherwise the results should be
similar to what's shown here.  Here are the simulation results for 10,000
Smith sets of 3-15 candidates, expressed as percentages:

Candidates SmC=Tid=Sch SmC=Sch<>Tid Tid=Sch<>SmC SmC<>Tid<>Sch SmC=Tid<>Sch
     3          0.9871       0.0036       0.0029        0.0000       0.0064
     4          0.8112       0.1309       0.0534        0.0011       0.0034
     5          0.7442       0.1803       0.0661        0.0059       0.0035
     6          0.6778       0.2348       0.0749        0.0095       0.0030
     7          0.6281       0.2792       0.0744        0.0137       0.0046
     8          0.5910       0.3158       0.0729        0.0162       0.0041
     9          0.5492       0.3513       0.0720        0.0233       0.0042
    10          0.5272       0.3831       0.0591        0.0260       0.0046
    11          0.4914       0.4195       0.0575        0.0258       0.0058
    12          0.4775       0.4382       0.0526        0.0268       0.0049
    13          0.4482       0.4678       0.0485        0.0297       0.0058
    14          0.4254       0.4894       0.0434        0.0357       0.0061
    15          0.4122       0.5046       0.0425        0.0345       0.0062

Trials:    10,000      SmC = Smith//Plain Condorcet(wv)
Voters:    100         Tid = Tideman(wv)
                       Sch = Schulze(wv)

(note that the above table should be viewed in a mono-spaced font for
readability).

My observations:

1) As the size of the smith set increases, the likelihood that all three
methods choose different winners increases slightly (not surprising), but
there's almost always some agreement (>95%).
2) Unless there is a consensus winner, Smith//PC and Tideman almost never
agree on their choice (<1%).  The Schulze method is somewhere between the
two in terms of results, since it is more likely to agree with the Tideman
winner than Smith//PC is when there is no consensus (4-7%)
3) Most importantly, Schulze and Smith//PC are in agreement on the choice of
winner over 90% of the time, regardless of the size of the Smith set,
whereas Tideman's method diverges in its choices as the size of the Smith
set increases (adding the first two columns of data makes this obvious).

I would interpret the result this way:

PC, Smith//PC:

The minimax method is designed to minimise voter dissatisfaction with a
particular choice, in the event that the result of the pairwise contest is
inconclusive (no Condorcet winner).  This seems like a fair way to break
circular ties.  Furthermore, other simulations I've carried out show that
this approach (assuming sincere voting) is the best tiebreaker at maximising
social utility (Simpson-Kramer, or PC(av) provides higher accuracy/social
utility than the copeland tiebreaker, for example). Unfortunately, it does
so at any cost -- many desireable guarantees that a pairwise method could
provide (Smith compliance, reversal symmetry, clone independence, etc.) need
to be sacrificed to satisfy this goal, which exposes the method to
criticism.

Schulze, SSD, SD:

The Schulze beatpath method has the same 'flavour' as plain Condorcet, in
that it also generally minimises voter dissatisfaction  when there is no
Condorcet winner.  However, it is willing to compromise on this goal when
choosing the least-opposed candidate would result in a violation of some
useful criteria.  Since this is VERY RARELY necessary in practice, it is a
good tradeoff to make, in my opinion.
I regard SSD and SD as close *approximations* of the Schulze method which
would be good practical choices to adopt if the beatpath method is not
considered sufficiently intuitive.  SSD is easier to explain, but the method
is not fully clone-independent when confronted with pairties.  Going
further, SD is even easier to understand, but it's necessary to sacrifice
clone independence and monotonicity (in extremely rare cases) to get that
simplification.  As a group, these methods provide a useful range of
tradeoffs between simplicity and quality of results.

Tideman:

Tideman's method goes its own way, probably because it aims first of all to
determine the best social ranking, rather than the best single-winner.  As a
result, the harder the test of the election method becomes (ie: the larger
the smith set), the more Tideman's result will tend to diverge from the
winner chosen by these other methods.  The question is -- is Tideman's
method making better and better choices as the problem size increases, or is
this divergence detrimental?  I suspect the latter, but I'll leave it to you
to argue the point.


--
Norm Petry

p.s. If you or anyone else at EM would like a copy of the latest version of
my simulation software so you can confirm or expand on these results, please
let me know.  I've also got an excel spreadsheet which shows the above data
in barchart form, if you're interested.


-----Original Message-----
From: Markus Schulze <schulze at sol.physik.tu-berlin.de>
To: npetry at accesscomm.ca <npetry at accesscomm.ca>;
schulze at sol.physik.tu-berlin.de <schulze at sol.physik.tu-berlin.de>
Date: October 29, 2000 5:23 AM
Subject: Re: [EM] Discover Magazine article


>Dear Norman,
>
>let's say that X is the PC winner, Y is the Tideman winner
>and Z is the Schulze winner. In so far as you have made
>simulations, I want to ask you to post to the EM list the
>following details:
>
>1) In how many cases are X and Y the same candidate and
>   Z a different candidate?
>2) In how many cases are X and Z the same candidate and
>   Y a different candidate?
>3) In how many cases are Y and Z the same candidate and
>   X a different candidate?
>4) In how many cases are X, Y and Z three different
>   candidates?
>5) In how many cases are X, Y and Z the same candidate?
>
>Markus Schulze
>