Robust Voting Rules: A Modern Approach to Social Choice Theory
Nisarg Shah
March 05, 2014

Social choice theory traditionally studies mechanisms for aggregating subjective preferences of individuals towards collective decisions. In our work, we analyze an alternative setting motivated by modern computational paradigms such as crowdsourcing and human computation (e.g., EteRNA), where the opinions expressed by individuals are estimates of an underlying true ranking of the alternatives (the opinions are typically viewed as samples from a probabilistic noise model), and the goal is to find the maximum likelihood estimator (MLE) for the true ranking under a chosen noise model. This approach still requires choosing the noise model upfront, which is usually unknown in practice.

To address this problem, we study voting rules that are robust against a wide family of noise models, making extremely weak assumptions on the noise governing voters evaluation mistakes. To achieve this goal, we relax the MLE requirement to accuracy in the limit: the voting rule should be almost surely accurate when the number of voters is large, as is the case in most settings of interest. In our current work (under submission), we also accurately pinpoint the unique voting rule that is accurate in the limit for essentially all reasonable noise models, simultaneously.