Smoothed Analysis of Social Choice Revisited

A canonical problem in social choice is how to aggregate ranked votes: that is, given n voters’ rankings over m candidates, what voting rule f should we use to aggregate these votes and select a single winner? One standard method for comparing voting rules is by their satisfaction of axioms — properties that we want a “reasonable” rule to satisfy. Unfortunately, this approach leads to several impossibilities: no voting rule can simultaneously satisfy all the properties we would want, at least in the worst case over all possible inputs. Motivated by this, we consider a relaxation of this worst case requirement: a “smoothed” model of social choice, where votes are independently perturbed with small amounts of noise. If no matter which input profile we start with, the probability of an axiom being satisfied post-noise becomes large as the number of voters n grows, we take it to be as good as satisfied — called “smoothed-satisfied” — even if it may be violated in the worst case. Within our smoothed model - a mild restriction of Lirong Xia’s - we give a cohesive overview of when smoothed noise is sufficient to overcome axiomatic impossibilities. We give simple sufficient conditions for smoothed-satisfaction or smoothed-violation of several axioms and paradoxes, including most that have been studied plus some previously unstudied. We then observe that in a practically important subclass of noise models, convergence to smoothed satisfaction is prohibitively slow as n grows. Motivated by this, we prove bounds specifically within a canonical noise model from this subclass — the Mallows model. Here, we find a more nuanced picture on exactly when smoothed analysis can help.