A Smoothed Impossibility Theorem on Condorcet Criterion and Participation
share
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≥ 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-Ω(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.
READ FULL TEXT