A Smoothed Impossibility Theorem on Condorcet Criterion and Participation

In 1988, Moulin proved an insightful and surprising impossibility theorem that reveals a fundamental incompatibility between two commonly-studied axioms of voting: no resolute voting rule (which outputs a single winner) satisfies Condorcet Criterion and Participation simultaneously when the number of alternatives m is at least four. In this paper, we prove an extension of this impossibility theorem using smoothed analysis: for any fixed $m\ge 4$ and any voting rule r, under mild conditions, the smoothed likelihood for both Condorcet Criterion and Participation to be satisfied is at most $1-\Omega(n^{-3})$, where n is the number of voters that is sufficiently large. Our theorem immediately implies a quantitative version of the theorem for i.i.d. uniform distributions, known as the Impartial Culture in social choice theory.