[EM] Condorcet cycle and FBLE probabilities... serious & instructive error; slick example

[Warren Smith]

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