The Experimental Mathematics of Voting By Shalosh B. EKHAD and Doron ZEILBERGER

By using the Maple package http://www.math.rutgers.edu/˜ zeilberg/tokhniot/LinDiophantus one derives the following theorem (in less than 20 seconds, see

http://www.math.rutgers.edu/~zeilberg/tokhniot/oLinDiophantus2), the following theorem.

Theorem 1 The weighted generating function of The Condorcet scenario 1 → 2 → 3 → 1 (with three candidates 1, 2, 3 and according to the weight

x123^{NumberOf123} ⋯ x321^{NumberOf321}t^{N}umberOfV otes

is

\frac{(1 + t^{3}x123 x231 x312 ) t^{3}x312 x123 x231}{(1 − t^{2}x123 x321 ) (1 − t^{2}x213 x312 ) (1 − t^{2}x312 x123 ) (1 − t^{2}x132 x231 ) (1 − t^{2}x123 x231 ) (1 − t^{2}x231 x312 )} .

By applying the ‘umbra’

x123^{a123} ⋯ x321^{a321} → (a123 + … + a321)!/((a123! ⋯ a321!) · 6^{a123+...+a321})

to the above one generating functions, one gets a differential equation (via WZ-theory) that translates into a recurrence that translates (for the odd part) to the following theorem. Theorem 2: Suppose three candidates, 1,2, and 3, are running for office, and there are 2n − 1 voters, each of them choosing one of the 3!=6 possible ranking with the same probability (1/6). The votes are counted and it turns out that in the vote of 1 vs. 2, 1 won 2 vs. 3, 2 won 1 vs. 3, 3 won In other words, there is a cycle 1 → 2 → 3 → 1. Let a(n) be the probability of that happening times 6^{2n−1} (i.e. the numerator) The integer sequence, a(n), satisfies the following linear recurrence equation with polynomial coefficients

−1296 \frac{n (2 n + 3) (2 n + 1) a (n)}{(n + 1) (n + 2)^{2}} + 36 \frac{(2 n + 3) (22 n^{2} + 33 n + 12) a (n + 1)}{(n + 1) (n + 2)^{2}}

−4 \frac{(19 n^{2} + 57 n + 45) a (n + 2)}{(n + 2)^{2}} + a (n + 3) = 0 .

The asymptotic expression for a(n) is 0.043869914022955 − 0.021101164 n^{−1} + O(n^{−2}) .

By symmetry, this is also the probability of the scenario 1 → 3 → 2 → 1. So doubling the asympotic expression for the Condorcet scenario is

0.087739828045910 − 0.042202328 n^{−1} .

Corollary: The probability for a strict Condorcet scenario with three candidates and 2n−1 voters tends as n → ∞ to a constant, that is approximately equal to 0.087739828045910 …, and that should be named the Condorcet constant.

Comment This number was first derived by cosnsiderable human effort by W.V. Gehrlein and P.C. Fishburn, The probability of paradox of voting: a computable solution, J. of Economic Theory 13 (1976), 14-25 [bottom of page 17, left column, where the complementary probability, 0.91226 (only to five digits) is given]

Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA;

DoronZeil at gmail dot com ; http://www.math.rutgers.edu/~zeilberg/ .

Exclusively published in The Personal Journal of Shalosh B. Ekhad and Doron Zeilberger

(http://www.math.rutgers.edu/~zeilberg/pj.html) .

Nov. 3, 2016