Estimating the Margin of Victory of an Election Using Sampling
Estimating the Margin of Victory of an Election Using Sampling
复制标题
使用抽样估计选举的胜利幅度
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Y. Narahari
中科院分区：
文献类型：
--
作者：
P. Dey;Y. Narahari
选举的胜选优势幅度是衡量选举结果稳健性的一个有用指标。它在确定选举后审计、民意调查等各种算法的样本量方面也起着至关重要的作用。在这项工作中，我们提出了基于高效抽样的算法来估计选举的胜选优势幅度。更正式地说，我们引入了（c，e，δ） - 胜选优势幅度问题，即给定一场有n个选民的选举e，目标是在cM(e)+en的加法因子范围内估计e的胜选优势幅度M(e)。我们针对许多常用的投票规则研究了（c，e，δ） - 胜选优势幅度问题，包括计分规则、认可投票、巴克林投票、极大极小投票以及科普兰α投票：我们观察到，即使对于那些计算胜选优势幅度是NP难的投票规则，也可能存在基于高效抽样的算法，正如在极大极小投票规则和科普兰α投票规则的情况中所观察到的那样。
The margin of victory of an election is a useful measure to capture the robustness of an election outcome. It also plays a crucial role in determining the sample size of various algorithms in post election audit, polling etc. In this work, we present efficient sampling based algorithms for estimating the margin of victory of elections. More formally, we introduce the (c, e, δ)-MARGIN OF VICTORY problem, where given an election e on n voters, the goal is to estimate the margin of victory M(e) of e within an additive factor of cM(e)+en. We study the (c, e, δ)-MARGIN OF VICTORY problem for many commonly used voting rules including scoring rules, approval, Bucklin, maximin, and Copelandα: We observe that even for the voting rules for which computing the margin of victory is NP-Hard, there may exist efficient sampling based algorithms, as observed in the cases of maximin and Copelandα voting rules.