%cond3.tex: a Plain TeX file  by Rebecca Embar and Doron Zeilberger
%Enumerating Condorcet
%begin macros
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
  0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
  height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\A{{\cal A}}
\def\B{{\cal B}}
\def\C{{\cal C}}
\def\S{{\cal S}}
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\def\W{{\cal W}}
\def\1{{\overline{1}}}
\def\2{{\overline{2}}}
\parindent=0pt
\overfullrule=0in
\def\Tilde{\char126\relax}
\def\frac#1#2{{#1 \over #2}}
%\headline={\rm  \ifodd\pageno  \RightHead  \else  \LeftHead  \fi}
%\def\RightHead{\centerline{
%Title
%}}
%\def\LeftHead{ \centerline{Doron Zeilberger}}
%end macros
\centerline
{\bf 
Counting Condorcet 
}

\bigskip
\centerline
{\it Rebecca EMBAR and Doron ZEILBERGER}
\bigskip
\qquad{\it In memory of Voting guru Peter Clingerman Fishburn ( 2 Sept. 1936 - 10 June 2021)}
\bigskip

{\bf Abstract}: 
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 
$(n+3)(n+2)(n+1)n(n-1)/60$. 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.

{\bf Keywords}: Condorcet Paradox, linear recurrences, compositions, bijective proofs. \hfill\break
{\bf AMS Subject Classifications}: Primary: 05A15, 05A19; Secondary: 33F10, 91C05.

{\bf Preface: Why yet another paper on the Condorcet Paradox?}

One of the most fascinating paradoxes is the {\bf Condorcet Paradox} [C] (see section 2.1 of [GM] for a very lucid and engaging account, and [BF], section 8, and [GF], for a comprehensive one).
In its simplest form there are $n$ voters and three candidates
(let's call them, unoriginally, $1$,$2$, and $3$ rather than the original {\it Pierre, Paul, and Jaques}).
Each voter must decide on one of the six complete rankings 
$$
123, \quad  132, \quad    213,  \quad  231, \quad  312, \quad  321 \quad  .
$$
Hence there are altogether $6^n$  {\it voting profiles}. Suppose that
$x_{123}$ voters picked the ranking $123$, $x_{132}$ voters picked the ranking $132$, 
$x_{213}$ voters picked the ranking $213$, $x_{231}$ voters picked the ranking $231$, $x_{312}$ voters picked the ranking $312$, and $x_{321}$ voters picked the ranking $321$.


So each voting profile leads, in a unique way to what we will call a {\it vote-count profile}.
$$
[x_{123},  x_{132},  x_{213},  x_{231},  x_{312},  x_{321}] \quad.
$$

For any two candidates $i$ and $j$, where $i \neq j$ and $1 \leq i, j \leq 3$ we say that $i$ beats $j$ if the number of voters who prefer $i$ to $j$ {\bf strictly} exceeds the number of voters who prefer $j$ to $i$.

A {\bf Condorcet scenario} happens when there is a {\it cycle} : $1$ beats $2$, $2$ beats $3$, and, surprise!, $3$ beats $1$, or vice versa.

A natural question is:

{\it ``Out of the $6^n$ possible voting profiles, how many  exhibit the Condorcet paradox?''}

In this article, we will describe how to compute these numbers in linear time and constant memory (linear-memory if you go by bit-size). 

For example we will show how to compute {\bf exactly} this number when there are $199$ voters. It happens to be the following integer


6211370515760300852136923742146263204611276496186703609937916433495661887654521$\backslash$ \hfill\break
53230295756825424993178166865007031915448766743811211727287337544489420000 \quad .

Hence the {\bf probability} of such a scenario, assuming that each voter picks a ranking uniformly at random, and the choices are {\it independent}, is:
$$
0.08731495004375520042327324685214106122590492980125416\dots
$$


Similarly, almost as fast, we can get the {\bf exact}  number of Condorcet voting-profiles with $19999$ voters. 
This happens to be a certain 15562-digit integer that is too large to reproduce here, but can be seen here:

{\tt https://sites.math.rutgers.edu/\~{}zeilberg/tokhniot/oCondorcet3e.txt} \quad .

It implies that the probability is
$$
0.0877356075296129282604035628906239948940764715\dots  \quad .
$$


Using asymptotics we can very accurately estimate the {\it limiting} probability,  as $n$ goes to infinity. It agrees, to any desired accuracy, with Guilbaud's 1952 exact value (see [BF], p. 205) 
$$
\frac{1}{4} -\frac{3}{2\pi} \sin^{-1} (\frac{1}{3}) \, = \, 0.08773982805\dots \quad .
$$

In particular, the present paper will result in a new sequence in the OEIS, that starts as follows

0, 12, 540, 21000, 785820, 28956312, 1058809752, 38545567632, 1399354322652, 50707958458872, 1835099465988360, 66348521294296176, 2397139928161319640, \hfil\break
86559958069097395440, 3124302168622853150640, 112729791393354644416800 , \dots


Its description is `number of Condorcet voting profiles with three candidates and $2n-1$ voters (starting with $n=1$)'.

To our surprise, this important sequence (viewed April 21, 2022) was not in the OEIS [S]. Neither did a search for $28956312$ (the number with $11$ voters) 
in  {\bf JSTOR} (that has 1879 articles  containing the words `Condorcet' and `Paradox') return  anything. 


The Condorcet paradox is a precursor of Ken Arrow's famous {\it impossibility theorem} [A] that
states that there does not exist {\it any} social choice function that is {\bf always} guaranteed to give
a clear-cut ranking of all the candidates, under some very reasonable set of ``axioms". This theorem, that was the subject of a whole book [A],
and that ultimately lead to a Nobel prize, with  the benefit of hindsight, now has a one-page proof [Y].

\vfill\eject

{\bf Counting All Vote-Count Profiles}

As mentioned above, a vote-count profile with $n$ voters (and three candidates) is a list of non-negative integers
$$
[x_{123},  x_{132},  x_{213},  x_{231},  x_{312},  x_{321}] \quad ,
$$
that add up to $n$, in other words, it is (what we call) a composition of $n$ into $6$ parts.

{\bf Definition}: A composition of $n$ into $k$ parts is a list $(x_1, \dots, x_k)$ of $k$  {\bf non-negative} integers that add-up to $n$.

(Note that the usual definition of {\it composition} requires that the entries are strictly positive. Of course there is a trivial bijection
between our kind of compositions of $n$ into $k$ parts and the usual kind of compositions of $n+k$ into $k$ parts.)

We first need a simple very well-known lemma.

{\bf Lemma 1}: The number of compositions (in our sense) of $n$ into $k$ parts is
$$
{{n+k-1} \choose {k-1}} \quad .
$$

Let's recall three proofs.

{\bf First Proof}: The (ordinary) generating function of the set of {\it non-negative} integers is $1+x+x^2+ \dots = \frac{1}{1-x}$. Hence the generating function
of compositions into $k$ parts is $(\frac{1}{1-x})^k=(1-x)^{-k}$. Hence the number of composition of $n$ is the coefficient of $x^n$ in $(1-x)^{-k}$, in other words
$$
(-1)^n \, {{-k} \choose {n}} \, = \, (-1)^n \frac{ (-k)(-k-1) \cdots (-k-(n-1))}{n!} \, = \, \frac{k(k+1) \cdots (k+n-1)}{n!} \, = \, {{n+k-1} \choose {k-1}} \quad .
$$

{\bf Second Proof}: Let $A(n,k)$ be the number of compositions of $n$ into $k$ non-negative integers. Let $(x_1, \dots, x_k)$ be such a composition. 
If $x_k=0$ then it is equi-numerous with $A(n,k-1)$. If $x_k \geq 1$ then mapping it to ($x_1, \dots, x_{k-1},x_k-1)$ gives an element counted by $A(n-1,k)$. Hence
$$
A(n,k) \, = \, A(n,k-1) \, + \, A(n-1,k) \quad.
$$
Now use induction to prove that $A(n,k)={{n+k-1} \choose {k-1}}$ \quad .

{\bf Third Proof}: The mapping 
$$
(x_1, \dots, x_k) \rightarrow \, \{ x_1+1, x_1+x_2+2, \dots, x_{1}+x_{2}+ \dots + x_{k-1}+k-1 \} \quad,
$$
is a bijection to the family of $(k-1)$-element subsets of $\{1,2, \dots, n+k-1\}$ \quad.


Hence we have the following corollary.

{\bf Corollary}: The {\bf total} number of {\bf vote-count profiles} with three candidates and $2n-1$ voters is
$$
{{2n+4} \choose {5}} \quad .
$$


{\bf Counting Condorcet Vote-Count Profiles}

Given a vote-count profile  $[x_{123},  x_{132},  x_{213},  x_{231},  x_{312},  x_{321}]$,  when does it produce a $1 \rightarrow 2 \rightarrow  3 \rightarrow 1$ cycle?

$1$ beats $2$ if

$$
x_{123} + x_{132} + x_{312} > x_{213} + x_{231} + x_{321}  \quad ;
\eqno(C12)
$$
$2$ beats $3$ if
$$
x_{123} + x_{213} + x_{231} >  x_{132} + x_{312} + x_{321} \quad ;
\eqno(C23)
$$
$3$ beats $1$ if
$$
x_{231} + x_{321} + x_{312} > x_{213} + x_{123} + x_{132} \quad .
\eqno(C31)
$$

So we have to count, out of all the compositions of $2n-1$ into $6$ parts those that satisfy the above three inequalities (and at the end double them to account for the reverse cycle).

We will now prove the following crucial theorem, and give an elegant bijective proof.

{\bf Theorem 1}: The number of {\bf Condorcet vote-count  profiles} with three candidates and $2n-1$ voters is
$$
2 {{n+3} \choose {5}} \quad .
$$

{\bf Proof}: Consider the affine-linear mapping from compositions of $n-2$ into $6$ parts to $1231$ Condorcet vote-count profiles
$$
[x_1,x_2,x_3,x_4,x_5,x_6] \rightarrow [ x_{1}+x_{4}+x_{6}+1, x_{2}, x_{3}, x_{2}+x_{4}+x_{5}+1, x_{3}+x_{5}+x_{6}+1, x_{1}] \quad .
$$
In other words
$$
x_{123} \,= \, x_{1}+x_{4}+x_{6}+1 \quad, \quad
x_{132} \, = \, x_2  \quad, \quad
x_{213} \, = \, x_3  \quad, \quad
$$
$$
x_{231} \, = \,  x_{2}+x_{4}+x_{5}+1 \quad, \quad
x_{312} \,= \,  x_{3}+x_{5}+x_{6}+1 \quad, \quad
x_{321}\, = \, x_1 \quad .
$$

It is readily seen that indeed 
$$
x_{123}+  x_{132}+  x_{213}+  x_{231}+  x_{312}+  x_{321} \, = \, 2n-1 \quad,
$$
and that the three inequalities $(C12)$, $(C23)$ and $(C31)$ hold. Indeed
$$
(x_{123} + x_{132} + x_{312}) -( x_{213} + x_{231} + x_{321}) \,= \, 2x_6+1 > 0 \quad ,
$$
$$
(x_{123} + x_{213} + x_{231})-  ( x_{132} + x_{312} + x_{321}) \, = \, 2x_4+1 >0 \quad ,
$$
$$
(x_{231} + x_{321} + x_{312})-  (x_{213} + x_{123} + x_{132}) \, = \, 2x_5+1 > 0 \quad,
$$
since all the $x_i$ are (by definition) non-negative.

The inverse bijection is
$$
[x_{123}, x_{132}, x_{213}, x_{231}, x_{312}, x_{321}] \rightarrow [x_1 , x_2,x_3,x_4,x_5,x_6] \quad.
$$
where
$$
x_1=x_{321} \quad, \quad
x_2=x_{132} \quad, \quad
x_3=x_{213} \quad, \quad
$$
$$
x_4 \, = \,
\frac{(x_{123} + x_{213} + x_{231} )- ( x_{132} + x_{312} + x_{321})-1}{2} \quad ,
$$
$$
x_5=\frac{(x_{231} + x_{321} + x_{312} )- ( x_{213} + x_{123} + x_{132})-1}{2} \quad ,
$$
$$
x_6=\frac{(x_{312} + x_{132} + x_{123} )- (x_{321} + x_{231} + x_{213} )- 1}{2} \quad .
$$


Note that $x_1,x_2,x_3$ are non-negative, of course, and so are $x_4,x_5,x_6$ thanks to the three inequalities. Also adding them gives $n-2$ (check!) .


It is also readily seen that these mappings are inverses of each other. Hence the number of Condorcet vote-count profiles with $2n-1$ voters and the cycle $1231$
equals the number of compositions of $n-2$ into $6$ parts, that by the above lemma equals  ${{n-2+5} \choose {5}}={{n+3} \choose {5}}$. By symmetry the
number of vote-count profiles with the reverse cycle also equals this, so doubling  proves the theorem.


{\bf Corollary}: If every vote-count profile is equally likely, the probability of it being Condorcet is
$$
\frac{2\,{{n+3} \choose {5}}}
{{{2n+4} \choose {5}}} \quad,
$$
that converges to $\frac{1}{16}=0.0625$ as $n \rightarrow \infty$.

{\bf Counting Condorcet Voting-Profiles}

Each {\bf vote-count} profile with $2n-1$ voters
$$
[x_{123}, x_{132}, x_{213}, x_{231}, x_{312}, x_{321}] \quad,
$$
gives rise to
$$
\frac{(2n-1)!}
{x_{123}!\, x_{132}! \, x_{213}! \, x_{231}!  \, x_{312}! \, x_{321}!} \quad
$$
{\bf voting-profiles} (where order matters).

What's nice about our bijective proof is that it gives us a `parametric representation' of a typical Condorcet vote-count profile, and hence we immediately have the
following proposition.

{\bf Proposition 1}: Let $a(n)$ be the number of Condorcet voting-profiles with three candidates and $2n-1$ voters, then it is given by the following $5$-fold sum:
$$
a(n)=
2\, \sum_{i_1=0}^{n-2} \quad \sum_{i2=0}^{n-2-i_1} \quad \sum_{i_3=0}^{n-2-i_1-i_2}\ \quad \sum_{i4=0}^{n-2-i_1-i_2-i_3} \quad \sum_{i_5=0}^{n-2-i_1-i_2-i_3-i_4}
$$
$$
\, 
\frac{\left(2 n -1\right)!}{\left(n -1-i_{2}-i_{3}-i_{5}\right)! i_{2}! i_{3}! \left(i_{2}+i_{4}+i_{5}+1\right)! \left(n -1-i_{1}-i_{2}-i_{4}\right)! i_{1}!} \quad .
$$

It follows from {\bf Wilf-Zeilberger} theory  [PWZ], and more specifically from the mutli-variable Zeilberger algorithm, that there {\bf exists} a linear recurrence with polynomial coefficients.
It can be easily found algorithmically [AZ], but it is even easier to find it by `guessing' that can be made fully rigorous {\it a posteriori}. This leads to the next theorem.

{\bf Theorem 2}: The number of Condorcet voting profiles with three candidates and $2n-1$ voters, let's call it $a(n)$, satisfies the following third-order recurrence
$$
a(n) \, = \,
\frac{4 \left(19 n^{2}-57 n +45\right) }{\left(n -1\right)^{2}} \cdot  a (n -1) -\frac{36 \left(2 n -3\right) \left(22 n^{2}-99 n +111\right)}{\left(n -2\right) \left(n -1\right)^{2}} \cdot a(n-2)
$$
$$
+
\frac{1296 \left(n -3\right) \left(2 n -3\right) \left(2 n -5\right) }{\left(n -2\right) \left(n -1\right)^{2}} \cdot a(n-3) \quad,
$$
subject to the initial conditions $a(1)=0$, $a(2)=12$, and $a(3)=540$.

Using this recurrence we can compute many terms! See

{\tt https://sites.math.rutgers.edu/\~{}zeilberg/tokhniot/oCondorcet3b.txt} \quad .


{\bf Restricted Choices}

Suppose that instead of allowing all six rankings, every voter has to pick from the restricted set $\{123, 231,312\}$.
Using similar reasonings we have the following theorem.

{\bf Theorem 3}: The number of Condorcet voting-profiles where all the choices are from $\{123,231,312\}$, let's call it $b(n)$, satisfies the
second-order linear recurrence
$$
\frac{36 \left(2 n +1\right) b \! \left(n \right)}{n +1}-\frac{\left(17 n +13\right) b \! \left(n +1\right)}{n +1}+b \! \left(n +2\right)
 = 0 \quad ,
$$
subject to the initial conditions $b(1)=0$ and $b(2)=6$. 

For the sake of the OEIS, the first $12$ terms:
$$
0, 6, 90, 1050, 11130, 112266, 1099098, 10550826, 99899514, 936435786, 8711707290, 80572452714 \quad .
$$

{\bf Loaded Choices}

If each voter, {\it independently}, rolls a six-faced die marked with the six permutations of $\{1,2,3\}$ where the probability of the ranking $\pi$ is $p_\pi$ then,
again  thanks to the bijection we have the following proposition.


{\bf Proposition 2}: If each of the $2n-1$ voters, picks, independently, one of the six ranking with distribution
$$
[p_{123} , p_{132} , p_{213} , p_{231}, p_{312} , p_{321}] \quad,
$$
(where of course they add-up to $1$), then
the probability of a Condorcet voting-profile is given by the following $5$-fold sum
$$
2\, \sum_{i_1=0}^{n-2} \quad \sum_{i2=0}^{n-2-i_1} \quad \sum_{i_3=0}^{n-2-i_1-i_2}\ \quad \sum_{i4=0}^{n-2-i_1-i_2-i_3} \quad \sum_{i_5=0}^{n-2-i_1-i_2-i_3-i_4} \, (2 n -1)! \cdot
$$
$$
\frac{p_{123}^{n -1-i_{2}-i_{3}-i_{5}}}{(n -1-i_{2}-i_{3}-i_{5})!} \cdot
\frac{p_{132}^{i_2}}{i_2!} \cdot
\frac{p_{213}^{i_3}}{i_3!} \cdot
\frac{p_{231}^{i_2+i_4+i_5+1}}{ (i_2+i_4+i_5+1)!} \cdot
\frac{p_{312}^{n -1-i_1-i_2-i_4}} { (n -1-i_{1}-i_{2}-i_{4})!} \cdot
\frac{p_{321}^{i_1}}{ i_1!}  \quad .
$$

This enables us to easily compute the Condorcet probability for $n\leq 50$ (i.e. up to $99$ voters). Alas, while we know {\it for sure} that
there is a recurrence, for general $p_{123}, \dots, p_{321}$, it was too complicated for our computer to discover, since it involves {\it symbol-crunching} with {\bf five} free parameters.

Nevertheless, we found recurrences for two important  special cases. One with two parameters, and the other one with one parameter.
Before stating them, let's make a few observation about the {\it limiting probabilities}.

If in the three inequalities $(C12)$,$(C23)$,$(C31)$, you replace $x_{123}$ by $p_{123}$ etc., and they {\bf all strictly hold}, or {\bf all strictly do not hold}, then,
since the expectations of $x_\pi$ is $n\,p_\pi$ for ($\pi \in S_3$), it follows from the {\it Law of Large Numbers}, that the probability of a Condorcet scenario always tends to $1$ (with cycles $1231$ and $3213$ respectively),
as $n$ goes to infinity. If one of 
the three inequalities  strictly holds but the other two stricly do not (or vice versa), then  the probability goes to $0$. If two of them strictly hold and one of becomes an equality, 
or if two of them strictly do not hold and one of becomes an equality, then the  probability of a Condorcet tends to $\frac{1}{2}$.

{\bf The Border-Line Distributions}

It follows that  the {\bf interesting} cases are those where  all the three inequalities $(C12)$, $(C23)$, and $(C31)$, with the $x_\pi$ replaced by $p_\pi$, turn into {\bf equalities}.
These are the only probability distributions on $S_3$  where the limiting probabilities of Condorcet are not one of $\{0,\frac{1}{2},1\}$. 
This happens if and only if

$$
p_{123} + p_{132} + p_{312} =p_{213} + p_{231} + p_{321}  \quad ,
$$
$$
p_{123} + p_{213} + p_{231}=  p_{132} + p_{312} + p_{321} \quad ,
$$
$$
p_{231} + p_{321} + p_{312} =p_{213} + p_{123} + p_{132} \quad ,
$$
and of course,
$$
p_{123} + p_{132} + p_{213} + p_{231} + p_{312} + p_{321}=1 \quad .
$$

It is easy to see that a parametric solution of these four equations with six unknowns is:
$$
[p_{123} \, , \, p_{132} \, , \,  p_{213} \, , \,  p_{231} \, , \,  p_{312} \, , \, p_{321}] \, = \,
\left[\, x \,, \, \frac{1}{2}-x -y \, , \,  y \, , \,  \frac{1}{2}-x -y \, , \,   y \, , \, x \, \right] \quad,
$$
where $0 \leq x,y$ and $x+y \leq \frac{1}{2}$. We call these distributions the {\it borderline cases}.

We did not succeed in computing a recurrence for the Condorcet probability in the general border-line case (i.e. for general $x$ and $y$), but when $x=y$ we have the following theorem.

{\bf Theorem 4}: Suppose that each of the $2n-1$ voters independently picks each of the rankings 
$123$, $213$, $312$ and $321$ with probability $x$,  and each of the rankings $132$ and $231$ with probability $\frac{1}{2}-2x$, where, of course, $0 \leq x \leq \frac{1}{4}$,
then, the probability of a Condorcet scenario  satisfies a certain fifth-order linear recurrence
equation with polynomial coefficients that is too complicated to reproduce here, but can be found in the following output file \hfill\break
{\tt https://sites.math.rutgers.edu/\~{}zeilberg/tokhniot/oCondorcet3f.txt} \quad .



{\bf A recurrence where the only allowed rankings are 123,231,312}

We have the following theorem. 

{\bf Theorem 5}: Suppose that each of the $2n-1$ voters independently picks the ranking $123$ with probability $p_{123}$, the ranking $231$ with probability $p_{231}$ and the
ranking $312$ with probability $1-p_{123}-p_{231}$ then, the probability of a Condorcet scenario, let's call it, $c(n)$, satisfies a certain fourth-order linear recurrence
equation with polynomial coefficients that is too complicated to reproduce here, but can be found in the following output file

{\tt https://sites.math.rutgers.edu/\~{}zeilberg/tokhniot/oCondorcet3d.txt} \quad .


{\bf The Maple package {\tt Condorcet3.txt}}

Everything here (and more) is implemented in the Maple package {\tt Condorcet3.txt}, available from the front of this article

{\tt https://sites.math.rutgers.edu/\~{}zeilberg/mamarim/mamarimhtml/cond3.html} \quad,

where there are also numerous output files. The main procedures are

$\bullet$ {\tt NuCo(n)}: inputs a positive integer $n$ and outputs the exact number of Condorcet voting profiles with three candidates and $2n-1$ voters.

For example, to get the number with $19999$ voters, type {\tt NuCo(10000);} \quad.

$\bullet$ {\tt PrCo(n,P)}: that inputs a positive integer $n$ and a probability distribution on $S_3$, 
$$
P=[p_{123},p_{132},p_{213},p_{231},p_{312},p_{321} ] \quad,
$$
and outputs the probability of a Condorcet scenario with three candidates and $2n-1$ voters. Since we were unable to find a recurrence, it does it directly, using Proposition $2$.
Hence can only go as far as $n=50$ in a reasonable amount of time. For example, to get the probability (in decimals) of a Condorcet scenario with
$59$ voters and probability distribution $[1/8,1/8,1/8,1/8,1/8,3/8]$, type

{\tt evalf(PrCo(30,[1/8,1/8,1/8,1/8,1/8,3/8]); } \quad,

getting $0.016838561353436318553\dots$. 

The corresponding probability with $79$ voters is gotten from

{\tt evalf(PrCo(40,[1/8,1/8,1/8,1/8,1/8,3/8]));}, getting $0.00888551620820918\dots$. Note that it tends to $0$, as it should.

$\bullet$ {\tt PrCoSp(n,p123,p231)}: it inputs a positive integer {\tt n}  and positive numbers {\tt p123, p231} such that their sum is less than $1$, and computes 
the   Condorcet probability   with $2n-1$ voters if each voter picks,  independently,  $123$ with probability {\tt p123},  $231$, with probability {\tt p231} and 
$312$ with probability {\tt 1-p123-p231}. Since it uses the above-mentioned recurrence, one can go very far.

For example, to get the probability when there are $1999$ voters and the probability of a $123$ is $\frac{1}{4}$, the probability of a $231$ is $\frac{1}{5}$, 
(and hence the probability of $321$ is $\frac{11}{20}$, type

{\tt evalf(PrCoSp(1000,1/4,1/5));} \quad,

getting $3.683198869\cdot 10^{-6}$.


$\bullet$ {\tt PrCoEq(n,x)}: it inputs a positive integer {\tt n}  and a positive number {\tt x}
(between $0$ and $\frac{1}{4}$, or leave $x$ symbolic), and it outputs the probability of a Condorcet scenario with probability distribution

$$
[p_{123},p_{132},p_{213},p_{231},p_{312},p_{321} ]=[x, \frac{1}{2}-2x, x, \frac{1}{2}-2x, x, x]  \quad.
$$

(Note that this is a {\it borderline case}). For example, typing

{\tt evalf(PrCoEq(2000,1/10));} \quad ,

gives $0.07718855192$, that tells you that this is the probability of a Condorcet scenario (with three candidates, as always in this paper) with $3999$ voters, if each voter, picks, independently,
$123$, $213$, $312$, and $321$  each with probability $\frac{1}{10}$ and picks $132$ and $231$ each with probability $\frac{3}{10}$.

Again since we have a recurrence, we can go very far. Note that $x$ can also be {\it symbolic}. Typing

{\tt plot(PrCoEq(100,x),x=0..1/4);}

would give a nice plot viewable here:

{\tt      https://sites.math.rutgers.edu/\~{}zeilberg/mamarim/mamarimhtml/cond3plot.html} \quad.

In addition we have a simulation procedures {\tt ApCo(v,P,K)}, that  estimates the probability of a Condorcet scenario with a loaded die $P$  and $v$ voters, by running it $K$ times.
We are happy to report that all our predictions were confirmed, within the {\it sampling error}.

{\bf Conclusion and Further Work}

We have defined an elegant, human-generated, bijection between compositions 
of $n-2$ into six parts,  and {\it Condorcet vote-count profiles} with three candidates and $2n-1$  voters, that proved that their number is
$2 {{n+3} \choose {5}}$.  Next we employed this useful bijection, combined with algorithmic proof theory [PWZ] and experimental mathematics, to enumerate
{\it Condorcet voting profiles}  with three candidates,  and to efficiently compute probabilities of interest.

We implemented everything in Maple, and produced lots of interesting output. Most importantly
we have created two new sequences for the OEIS [S].

It would be interesting to extend our approach to other situations, for example the one discussed in [MTV], and
for a number of candidates larger than three.


{\bf Acknowledgment}: Many thanks are due to Robert Dougherty-Bliss for useful discussions and very insightful comments.

{\bf References}

[AZ] Moa Apagodu and Doron Zeilberger,
{\it Multi-Variable Zeilberger and Almkvist-Zeilberger Algorithms and the Sharpening of Wilf-Zeilberger Theory},
Adv. Appl. Math. {\bf 37} (2006), 139-152. \hfill\break
{\tt https://sites.math.rutgers.edu/\~{}zeilberg/mamarim/mamarimhtml/multiZ.html} \quad .


[A] Kevin J. Arrow, {\it ``Social choice and individual values''}, John Wiley, New York, 1951.

[BF] Steven J. Brams and Peter C. Fishburn, {\it Voting Procedures}, Ch. 4 in ``{\it Handbook of Social Choice and Welfrare}'', Vol. 1, edited by K.J. Arrow, A.K. Sen and K. Suzumura, Elsevier, 2002.

[C] Marie Jean Antoine Nicolas de Caritat, Marquis de Condorcet,
{\it Essai sur l'application de l'analyse \`a la probabilt\'e des d\'ecisions rendues \`a la plurait\`e de voix},
Paris, 1785.

[GF] William V. Gehrlein and Peter C. Fishburn, {\it The probability of the paradox of voting: A computable solution}, J. of Economic Theory {\bf 13}
(1976), 14-25.

[GM] Ein-Ya Gura and Michael B. Maschler, {``Insights into Game Theory''}, Cambridge University Press, 2008.

[MTV] V. Merlin, M. Tataru, F. Valognes, {\it On the Likelihood of Condorcet Profiles},  \hfill\break
{\tt https://www.unamur.be/eco/recherche/cahiers/2000/223.pdf}

[PWZ] Marko Petkovsek, Herbert S. Wilf and Doron Zeilberger,
{\it A=B}, AK Peters, Wellesley, (1996).  {\tt https://sites.math.rutgers.edu/\~{}zeilberg/AeqB.pdf} \quad .

[S] Neil J. A. Sloane, {\it  The On-Line Encyclopedia of Integer Sequences (OEIS)},  \hfill\break
{\tt https://oeis.org/} \quad .

[Y] Ning Neil Yu, {\it A one-shot proof of Arrow's impossibility theorem}, Economic Theory {\bf 59} (2012), 523-525.

\bigskip
\hrule
\bigskip
Rebecca Embar and Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen
Rd., Piscataway, NJ 08854-8019, USA. \hfill\break
Email: {\tt  re271 at math dot rutgers dot edu} \quad, \quad {\tt DoronZeil] at gmail dot com}   \quad .


Written: April 29, 2022.

\end


