Boris Pittel
The Ohio State University
Title
On likelihood of a Condorcet winner for uniformly random and independent voter preferences
Abstract
We study a mathematical model of a voting contest with m voters and n candidates, each voter ranking the candidates in order of preference, without ties. A Condorcet winner is a candidate who gets more than m/2 votes in pairwise contest with every other candidate. An “impartial culture” setting is the case when each voter chooses his/her candidate preference list uniformly at random from all n! preference lists, and does it independently of all other voters. For impartial culture case, Robert May and Lisa Sauermann showed that when m = 2k − 1 is fixed (k = 2 and k > 2 respectively), and n grows indefinitely, the probability of a Condorcet winner is small, of order n^{-(k−1)/k}. We show that when m, n \to \infty grow indefinitely and m >> n^4, the probability is at most of order n^{-1} (log n)^{1/2} \cdot log log n + n^2/m^{1/2} \to 0.
