  Predicting the winner of an election is a favorite problem both for news
media pundits and computational social choice theorists. Since it is often
infeasible to elicit the preferences of all the voters in a typical prediction
scenario, a common algorithm used for winner prediction is to run the election
on a small sample of randomly chosen votes and output the winner as the
prediction. We analyze the performance of this algorithm for many common voting
rules.
  More formally, we introduce the $(\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.
