The Smoothed Possibility of Social Choice
This work addresses theoretical barriers in social choice for AI and ML applications, though it is incremental in applying existing smoothed analysis to this domain.
The paper tackles paradoxes and impossibility theorems in social choice by applying smoothed complexity analysis, showing that the likelihood of Condorcet's paradox vanishes exponentially with more agents and characterizing rates for the ANR impossibility to vanish, while proposing a tie-breaking mechanism that preserves anonymity and neutrality.
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.