On the Cardinality of the Smith Set Under Impartial Culture with Many Alternatives

Abstract

For some integer $\ell \ge 2$, consider $m=2\ell -1$ voters, each of which has a preference ranking over $n$ alternatives. The Smith set is the smallest nonempty set of alternatives each of which defeats every alternative outside the set in a pairwise majority comparison. Under the standard benchmark impartial culture where each voter uniformly and independently chooses a random preference ranking over all alternatives, we study the asymptotic probability that the Smith set has cardinality $s$ for fixed $\ell$ and $n\to \infty$. First, we prove that the probability that the Smith set has constant cardinality $s$ goes to zero at a rate of ${\Theta }_{\ell ,s}(n^{-s(\ell -1)/\ell })$. Next, if $\min \{s,n-s\}\to \infty$, we show that this probability decays superpolynomially. Further, when $s$ and $n-s$ are both $\Theta (n)$, we prove that the probability decays exponentially and determine the exact exponential base. Finally, we prove that the probability that the Smith set contains all alternatives approaches one at a rate of ${\Theta }_{\ell }(n^{-(\ell -1)/\ell })$. These theorems resolve the conjectures in [Liu et al, Ann Stat 2026] under impartial culture.

arXiv comment20 pages