论文标题
基于抽样的赢家预测在地区选举中
Sampling-Based Winner Prediction in District-Based Elections
论文作者
论文摘要
在一个地区的选举中，我们应用一项投票规则$ r $来决定每个地区的获奖者，而在最多地区赢得最多地区的候选人是选举的获胜者。我们提出了有效的基于抽样的算法，以预测本文基于地区选举系统的获胜者。当$ r $是多元性的，并且众所周知，胜利的余量至少是总人口的$ \ varepsilon $分数时，我们提出了一种算法来预测获胜者。我们算法的示例复杂性是$ \ Mathcal {O} \ left（\ frac {1} {\ varepsilon^4} \ log log \ frac {1} {\ varepsilon} {\ varepsilon} \ log \ log \ frac \ frac {1}Δ\ right）$。我们通过证明，从天然类别的算法中证明，当$ r $是多元性时，任何算法都必须在区域选举中预测获胜者，必须采样至少$ω\ weft（\ frac {1} {1} {\ varepsilon^4} 4} \ log \ frac \ frac \ frac \ frac {1} frac {1} $ right）$投票。然后，我们将此结果扩展到任何投票规则$ r $。宽松地说，我们证明我们可以预测基于地区的选举的获胜者，其额外的间接费用为$ \ Mathcal {o} \ left（\ frac {1} {\ varepsilon^2} \ varepsilon^2} \ log \ log \ log \ frac {1}δ\ right）我们进一步扩展了我们的算法，当时胜利的余地未知，但我们只有两个候选人。然后，当每个地区的一系列偏好均单峰时，我们将考虑中位投票规则。我们表明，可以用$ \ Mathcal {o} \ left（\ frac {1} {\ varepsilon^4} \ log \ frac {1} {\ varepsilon} {\ varepsilon} \ log \ frac \ frac {1} frac samples nestrance and Smooter nestrance and Smoots y时，也可以相互controrts nistamples，即使是均可订阅范围，否则，既然订单''最后，我们还显示了一些结果，以估计在加法和乘法误差范围内基于地区选举的胜利余量。
In a district-based election, we apply a voting rule $r$ to decide the winners in each district, and a candidate who wins in a maximum number of districts is the winner of the election. We present efficient sampling-based algorithms to predict the winner of such district-based election systems in this paper. When $r$ is plurality and the margin of victory is known to be at least $\varepsilon$ fraction of the total population, we present an algorithm to predict the winner. The sample complexity of our algorithm is $\mathcal{O}\left(\frac{1}{\varepsilon^4}\log \frac{1}{\varepsilon}\log\frac{1}δ\right)$. We complement this result by proving that any algorithm, from a natural class of algorithms, for predicting the winner in a district-based election when $r$ is plurality, must sample at least $Ω\left(\frac{1}{\varepsilon^4}\log\frac{1}δ\right)$ votes. We then extend this result to any voting rule $r$. Loosely speaking, we show that we can predict the winner of a district-based election with an extra overhead of $\mathcal{O}\left(\frac{1}{\varepsilon^2}\log\frac{1}δ\right)$ over the sample complexity of predicting the single-district winner under $r$. We further extend our algorithm for the case when the margin of victory is unknown, but we have only two candidates. We then consider the median voting rule when the set of preferences in each district is single-peaked. We show that the winner of a district-based election can be predicted with $\mathcal{O}\left(\frac{1}{\varepsilon^4}\log\frac{1}{\varepsilon}\log\frac{1}δ\right)$ samples even when the harmonious order in different districts can be different and even unknown. Finally, we also show some results for estimating the margin of victory of a district-based election within both additive and multiplicative error bounds.
