  We develop a framework that leverages the smoothed complexity analysis by
Spielman and Teng to circumvent paradoxes and impossibility theorems in social
choice, motivated by modern applications of social choice powered by AI and ML.
For Condrocet's paradox, we prove that the smoothed likelihood of the paradox
either vanishes at an exponential rate as the number of agents increases, or
does not vanish at all. For the ANR impossibility on the non-existence of
voting rules that simultaneously satisfy anonymity, neutrality, and
resolvability, we characterize the rate for the impossibility to vanish, to be
either polynomially fast or exponentially fast. We also propose a novel
easy-to-compute tie-breaking mechanism that optimally preserves anonymity and
neutrality for even number of alternatives in natural settings. Our results
illustrate the smoothed possibility of social choice -- even though the paradox
and the impossibility theorem hold in the worst case, they may not be a big
concern in practice.
