Predicting winner and estimating margin of victory in elections using sampling

摘要

Predicting the winner of an election and estimating the margin of victory of that election are favorite problems 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 predicting the winner and estimating the margin of victory is to run the election on a small sample of randomly chosen votes and predict accordingly. We analyze the performance of this algorithm for many commonly used voting rules.