Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR15-037 | 20th February 2015 17:20

#### Sample Complexity for Winner Prediction in Elections

TR15-037
Authors: Arnab Bhattacharyya, Palash Dey
Publication: 11th March 2015 06:00
More formally, we introduce the {\em $(\epsilon, \delta)$-winner determination problem}, where given an election on $n$ voters and $m$ candidates in which the margin of victory is at least $\epsilon n$ votes, the goal is to determine the winner with probability at least $1-\delta$. The margin of victory of an election is the smallest number of votes that need to be modified in order to change the election winner. We show interesting lower and upper bounds on the number of samples needed to solve the $(\epsilon, \delta)$-winner determination problem for many common voting rules, including scoring rules, approval, maximin, Copeland, Bucklin, plurality with runoff, and single transferable vote. Moreover, the lower and upper bounds match for many common voting rules in a wide range of practically appealing scenarios.