Probability of a Condorcet Winner for Large Electorates: An Analytic Combinatorics Approach

Abstract

We study the probability that a given candidate is an α-winner, that is, preferred over every other candidate j by at least a fraction α_j of the voters. This general framework encompasses the classical notion of a Condorcet winner, corresponding to α = (½,…,½). Assuming voters have independent preferences, we derive general results and apply them to prominent models such as Impartial Culture and the Mallows model. While previous work relies on probabilistic arguments to derive the limiting probability for a fixed number of candidates 𝑚 as the number of voters 𝑛 tends to infinity, we use techniques from the field of analytic combinatorics to compute not only this limit but also convergence rates, and we provide a method for obtaining higher-order terms in the asymptotic expansion. In particular, we refine existing results on the Condorcet winner under Impartial Culture by establishing the following asymptotic behavior for its probability: a_0,m + a_1,m,nn^-1/2 + Ο(n^-1), where we give explicit expressions for the coefficients a_0,m and a_1,m,n. The latter depends on the parity of the number of voters n only through its parity, while the number of candidates 𝑚 is fixed in our asymptotic regime. Along the way, we derive technical results in multivariate analytic combinatorics that may be of independent interest.