Counting Condorcet

By Rebecca Embar and Doron Zeilberger

.pdf    .tex
Appeared in- Enumerative Combinatorics and Applications 2:3 (2022) Article #S2R22

Written: April 28, 2022

We give an elegant bijective proof that the number of vote-count profiles that lead to the famous Condorcet paradox with three candidates and 2n-1 voters equals 2*binomial(n+3,5). We then use this bijection to efficiently enumerate the total number of Condorcet voting profiles with a given number of (odd) voters, and related probabilities.

Added April 29, 2022: As we said in the paper, the sequence enumerating Condorcet profiles with an odd number of voters (and three candidates) is not yet in the OEIS (we hope to put it there soon), but a search for the complementary numbers, those that do NOT lead to the Condorcet paradox namely

seq(6^(2*n1-1)-NuCo(n1),n1=2..8);

that is:

6, 204, 7236, 258936, 9291876, 333840744, 12001884264, 431639416944,

lead to the following interesting article (in Japanese) by Toshio Urata, entitled "The probability that no Condorcet winner emerges in an election"
[We thank Shigeru Mochida for translating the title and deciphering the author's name]

However we are sure that they can't compute the 10000-th term, while we can do it in second!

# Maple package

• Condorcet3.txt, A Maple package for enumerating (and computing probabilities) related to the three-candidate Condorcet Paradox.

# Sample Input and Output for Condorcet3.txt

• If you want to see the beautiful bijection between compositions of n (with non-neg. integers) with 6 parts and Condorcet vote-count profiles with 2n+3 voters
the input gives the output.

• If you want to see the first 1000 terms of the sequence
"Number of Condorcet voting-profiles when there are 2n-1 voters, (out of the total of all 62n-1 possibe voting profiles)", as well as the 10000-th term (in other words, the number of Condorcet voting-profiles with 19999 voters)
the input gives the output.

• If you want to see (again, the end of the last file) the number of Condorcet voting-profiles with 19999 voters, as well as the implied probability of that happening (assuming that each voter is equally likely to pick one of the six rankings, and that the voters' decisions are independent), obtained by dividing the former by the total number of voting profiles, namely 619999. This probability starts with .877356075296... (Note that the limiting probability as n goes to infinity (see below) is: .8773982805... (hence the convergence is fairly slow).
the input gives the output.

• If you want to see the limiting probability of the Condorcet phenomenon with three candidates to 10 decimal digits
the input gives the output.

Note that is agrees with Guilbaud's exact value if 1/4-3/(2*Pi)*arcsin(1/3)

• If you want to see the first 100 terms of the sequence enumerating the number of ways 2n-1 (out of the total of 32n-1 possibilities) , where each voter chooses either the ranking 123, 231, or 312, of a Condorcet scenario happening, as well as the 1000-th term. It also gives you a recurrence for the probabilities in the loaded case, and a few examples, and confirmations via simulation.
the input gives the output.

• If you want to see the recurrence for the probability of Condorcet if the probability distribution on
[123,132,213,231,312,321]
is [x, 1/2-2*x, x, 1/2-2*x, x, x]
As well simulating it 5000 times the input gives the output.

• If you want to see the same thing as the previous file, but with simulating it 50000 times (hence better agreement with the exact results)
the input gives the output.

• If you want to see the first 50 terms of the sequence "Probability of a Condorcet scenario with three candidates and 2n-1 voters when the prob. distribution on the six possible rankings :[123,132,213,231,312,321] are [x, 1/2 - x - y, y, 1/2 - x - y, y, x], respectively (this two-parameter family is the only case where the limiting probability is not one of {0,1/2,1})
the input gives the output.

• This plot descibes the probability of Condorcet with three candidates and 199 voters, where each voter independently picks each of the rankings 123,213,312, and 321 with probability x x, and the randkings 132 and 231 each with probability 1/2-2x, for x from 0 to 0.25.

• This plot descibes the probability of Condorcet with three candidates and 99 voters, where each independently picks
• each of the rankings 123, 321 with probability x

• each of the rankings 213, 312 with probability y

• each of the rankings 132 231 with probability 1/2-x-y