[EM] Probability of Condorcet Winners (was: Re: Approval Voting fish (3), selected replies)

[Norman Petry]

In response to Craig Carey, Mike Ossipoff wrote (4 Mar 00):

>>Can any explain that the basis of the method: does it have a trace of
>>  plausibility to it?. Whereas for large problems, Condorcet can't find
>>  an answer for
>>  0.999999999999999999999999999999999999999999999 of all elections,
>
>You're probably referring that there won't always be one candidate
>who beats each one of the others. For one thing, no one agrees
>that it will be as rare as you say. And if you'd paid attention
>to anything that's been said about Condorcet's method, you'd
>know that Condorcet said what to do when no one beats everyone.
>You've got to read before you write. People haven't got time
>to read statements that you write when you don't have a clue about
>the topic.

I agree with Mike that this is a rather unlikely outcome.  One of the things
I've been working on are simulations of various voting methods.  I described
the approach in my posting of 8 Feb 00.  One of the results that emerged
from this work was the percentage of cases without a Condorcet winner.  Here
are the results for a normally-distributed electorate with a 1D issue space
and fairly high involvement (but still some truncation), showing how the
frequency of Condorcet winners varies as a function of the number of
candidates:

Trials: 10000
Involvement: 0.8
Dimensions: 1

Candidates CWs
2 9929
3 9894
4 9850
5 9791
6 9727
7 9669
8 9647
9 9561
10 9537
11 9496
12 9417
13 9398
14 9327
15 9263

The following example shows how the frequency of Condorcet winners varies as
a function of the number of dimensions (note the very high degree of
truncation in this example):

Trials: 10000
Involvement: 0.3
Candidates: 7

Dimensions CWs
1 9158
2 9544
3 9603
4 9603
5 9573
6 9557
7 9556
8 9538
9 9535
10 9540

In the following example, I assumed that voters would be uniformly
distributed, rather than normally distributed to see if this would affect
the result (it doesn't, particularly).  This example shows how the number of
CWs varies as a function of involvement:

Trials: 10000
Candidates: 4
Dimensions: 1

Involvement CWs
0.1 9492
0.2 9651
0.3 9709
0.4 9721
0.5 9742
0.6 9783
0.7 9809
0.8 9853
0.9 9825
1.0 9777

Note that all of these examples used an electorate of 100 voters.  This
increases the likelihood of ties, and therefore slightly *understates* the
probability of Condorcet winners in public elections.  I have done many
similar tests, but won't bore you with any more results unless someone
expresses interest.  In summary:

1) The frequency of Condorcet winners declines gradually as the number of
candidates increases.  Extrapolating from my data, I expect that an election
having a "0.999999999999999999999999999999999999999999999" probability of no
Condorcet winner would require tens of thousands of candidates.

2) Increasing the "dimensionality" of the data reduces the likelihood of
voting cycles. The one-dimensional case is the most difficult, always.

3) As truncation increases ("involvement" approaches 0), voting cycles
become slightly more probable.

4) There will be no Condorcet winner about 5% of the time, under most
reasonable assumptions.  These few cases will require a suitable tiebreaker,
and as Mike has pointed out, we have several good ones to choose from.

Of course, like any simulation, mine is based on certain assumptions, and
the results can be questioned on those grounds.  The basic assumption I have
made is that a sincere, but somewhat "lazy" electorate is voting.  That is,
voters will always rank according to sincere preferences, but each voter
will truncate his/her ballot at some randomly-determined point.  For these
results to be similar to real life, the specific method chosen should be as
strategy-proof as possible, so that the expressed preferences are close to
the sincere preferences.

I would be interested to know the assumptions that underlie Craig Carey's
result for Condorcet's method.


-- Norman Petry