Sample Complexity for Winner Prediction in Elections
Sample Complexity for Winner Prediction in Elections
复制标题
选举中获胜者预测的样本复杂性
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
P. Dey
中科院分区：
文献类型：
--
作者：
Arnab Bhattacharyya;P. Dey
预测选举的赢家是新闻媒体专家和计算社会选择理论家最喜欢的问题。由于在典型的预测场景中，通常不可能引出所有选民的偏好，因此用于预测获胜者的常用算法是在随机选择的小样本选票上进行选举，并将获胜者作为预测输出。我们分析了该算法在许多常见投票规则下的性能。
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 (e, δ)-winner determination problem, where given an election on n voters and m candidates in which the margin of victory is at least en votes, the goal is to determine the winner with probability at least 1-δ. 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 (e, δ)-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.