Boris Pittel
The Ohio State University
Title
On Condorcet coalitions in a voting contest with voters randomly ranking candidates
Abstract
We study a probabilistic model (impartial culture) of a voting contest with $m$ candidates and $n$ voters, each voter linearly ordering candidates, uniformly and independently of other voters. A Condorcet winner is a candidate who gets more than $n/2$ votes in a pairwise contest with every other candidate. There is a sizable evidence, theoretical and numerical, that a Condorcet winner is unlikely. Recently we proved that for $n\gg m^4\gg 1$, the likelihood of a Condorcet winner is $O(m^2/n^{1/2})+\Theta(m^{-1}\log^{1/2}m)\to 0$, and it gets significantly lower still for candidates {\it partially, and independently}, ordered by voters. In 2015, Elkind et.al introduced a notion of Condorcet winning set (coalition) of candidates, such that any other candidate loses in a pairwise contest with at least one of inside candidates. They proved existence of a Condorcet coalition of size at most $\log m$. In 2020, Jiang et.al found that $\log m$ can be replaced with a constant $16$. In 2026, Lassota et.al proved existence of a Condorcet coalition of size $3$ in a spatial model of voting. These results motivated a more recent work by Charikar et.al, and Song et.al, proving--for the general model--existence of a Condorcet coalition of size $6$, and $5$ respectively, and by Zilberstein et.al, formulating a conjecture that, if confirned, would prove existence of a Condorcet coalition of size $4$ for any preference lists. For {\it the impartial culture case} and $n\gg m^4\gg 1$, we show that the {\it expected} number of Condorcet coalitions of size $\ell\ge 2$ is at least of order $m^{\ell-2}\log^{1/2}m$, and we conjecture that the {\it likely} number of the coalitions of size $3$ is at least of order $m\log^{1/2}m$.