Complexity of Election Evaluation and Probabilistic Robustness

When dealing with election data it is reasonable to assume that the votes are incomplete or noisy. The reasons are manifold and range from cost-intensive elicitation to manipulation. We study the important questions of evaluating elections with incomplete data and the robustness of elections with noisy data from a computational point of view. To capture different motivations, we consider three models for the distribution of preferences: the uniform distribution over the completions of incomplete preferences inspired by the possible winner problem, the dispersion around complete preferences, also called Mallows noise model, and a model in which the distribution over the votes of each voter is explicitly given. We consider both approval vector preferences and linear order preferences and show that the complexity of the problem can vary greatly depending on the voting rule, the distribution model, and the parameterization.