[EM] Condorcet cycle and FBLE probabilities... serious & instructive error; slick example
Warren Smith
wds at math.temple.edu
Tue Nov 29 20:36:50 PST 2005
Unfortunately I recently discovered an important error
I made which has contaminated a number of claims by me
about Condorcet cycles. This error and its fix are both
very instructive.
Here it is.
Assume there are V voters, V large, each of whom cast any of
the 6 possible votes ABC, BAC, ACB, BCA, CAB, CBA
randomly, independently, equally likely for all 6 votes,
in a 3-candidate Condorcet election..
Then what is the probability of an A>B>C>A clockwise condorcet cycle?
Well, I had thought, "obviously" this probability was 1/8,
since of the possible directions of the AB, BC, CA pairwise
defeats, obviously each was a coin flip so +++ would occur with
(1/2)^3 = 1/8 chance.
WRONG!
The problem is that these 3 coin flips are not independent.
They are in fact anti-correlated. E.g. if A defeats B, that makes it
LESS LIKELY than 50% than B defeats C. You can see this because
this sum of 6 i.i.d. normal random variables (using 3-letter variable names)
ABC+ACB+CAB-BAC-BCA-CBA (which is >0 iff A defeats B)
is ANTI-CORRELATED to this sum
ABC+BAC+BCA-ACB-CAB-CBA (which is >0 iff B defeats C);
indeed the covariance is +1-1-1-1-1+1 = -2, not 0.
Hence the +++ probability (needed for a cycle) is LESS than 1/8.
OK, so then, after some moderately hairy mathematics, I managed to convince
myself that the true answer is not 1/8 but rather
(3*arccos(1/3)-pi)/(4*pi)
= (3*arctan(sqrt(8))-pi)/(4*pi)
= 1/22.79466514287532325999940091693424175364975794663703925246052384042...
(which by the way is provably irrational)
while 1.4 billion Monte Carlo computer experiments find
1/(22.79453 +- 0.00321) using 1 sigma error bars
which seems fully acceptably close to the claimed exact result, so I must be right... :)
Now FBLE (Favorite-Betrayal Lesser-Evil) scenarios, and cycles, come up in Condorcet
not 1/4=25% of the time, but rather 1/11.39=8.78% of the time (in this model).
This jibes rather better with Andrew Myer's claims that Condorcet cycles are fairly rare
in practice. (Actually I would expect them to be rarer in practice than they are in this model.)
Now what about Condorcet where we now allow candidate-equality-rankings and we
do it with "winning votes" instead of "margins"? The proponents of these
two improvements believed/hoped that the percentage of FBLE scenarios would be
reduced this way. I claim these proponents are correct: Monte Carlo experiments
where all 12 nontrivial vote types
C>A>B, C>B>A, B>A>C, B>C>A, A>B>C, A>C>B,
C>A=B, C=B>A, B=A>C, B>C=A, A>B=C, A=C>B
are considered equally likely, find that
the probability of a clockwise cycle is
1/37.38 which is less than it used to be (1/22.79)
and that it is no longer true that asymptotically 100% of the cyclic scenarios have FBLE;
instead, only 67.5% of them do. The net effect, then, is a reduction in FBLE probability
(in our model of all elections equally likely) to 41% of what it used to be
with margins and equality-rankings-forbidden, namely to 3.6%.
Is 3.6% small enough that we need not worry about FBLE anymore so that ER-Condorcet(wv)
will not lead to 2-party domination? Well... a voter still can argue 100% of the time that if
he is convinced the third-party candidate cannot win, then it does not hurt
to betray him and vote the lesser-evil top, and it helps 3.6% of the time.
What matters is the comparison between probability of "third party guy wins" and
"3.6% probability that favorite-betrayal works". So, at least in the USA, the third party
guy wins well below 1% of the time in federal and governor elections, so
by that logic even 3.6% would still be enough to lead to self-reinforcing 2-party domination
even with ER-condorcet(wv). Or at least, it's enough to make you worry.
Of course then you could make arguments about how realistic this whole model is, etc,
but I will refrain.
So the morals seem to be:
* voting keeps managing to do nonobvious things designed to destroy my self-esteem.
* ER-condorcet(wv) proponents have some basis for their claims.
* is favorite-betrayal a problem in Condorcet? Debatable.
-------
Incidentally, as my parting shot, I mention the following
11-voter 3-candidate election example proving that Condorcet schemes with
ranking-equalities allowed suffer from favorite-betrayal, and that is true whether
you use "winning-votes" or "margins".
#voters their vote
2 A>B>C
3 C>A>B
4 C=B>A
2 A>B>C
Defeats are A>B by 7:4, B>C by 4:3, and C>A by 7:4. There is an A>B>C>A cycle
in which B>C is the weakest defeat (measured by either winning votes or by margins), so
that C is elected.
Notice that the two A>B>C voters shown on the bottom line can
turn the "lesser evil" B into the Condorcet Winner by "betraying" their
favorite "third party" candidate A and voting B>A>C or B>A=C or B>C>A.
However, changing their vote instead to
A=B>C or A>B=C or A=C>B or A>C>B or A>B>C or B=C>A or A=B=C (or C>B>A or C>A>B or C>A=B)
does not suffice: then C still uniquely wins in all cases. Hence favorite-betrayal of
A was strategically necessary.
All this is true regardless of whether you use "margins" or "winning votes."
wds
More information about the Election-Methods
mailing list