利用抽样估算选举的胜利边界
统计学选举学家研究了在通常非常困难获取全部选民偏好的情况下,最常用的赢家预测算法是将选举在少量随机选票中运行,并将获胜者作为预测结果的性能。研究了 $(\epsilon, \delta)$-winner determination 问题,并给出了多种常见投票规则下解决该问题所需样本数量的有趣下界和上界。
Feb, 2015
本文利用基于抽样的算法预测基于选区的选举中的获胜者,证明了预测选举结果的最低样本复杂度,并扩展了模型以适用于各种投票规则和未知的胜利余数情况,同时提供了估算胜利余数的方法和误差范围
Feb, 2022
研究选举活动中的投票管理场景,外部方可以购买选票,目的是使其首选候选人获胜,同时尽可能少地支付,提出了一种 2 - 逼近算法,适用于大多数评分规则并且适用于加权选民,可以应用于商业环境的竞选活动管理。同时,提出了对两种 Condorcet 一致规则(即 Copeland 准则和 maximin)的求近似算法。
Mar, 2010
本文旨在使用最大相对超支差(MRO)来推断是否出现错误,当全手动计数的条件下的 MRO 小于 1 时,选举结果必须与表面结果一致,对于 2006 年明尼苏达州的联邦参议员选举使用 MRO 测试的 P 值为 4.05%,是 Stark 发现的一半以内。
Nov, 2008
研究 Monroe 规则和 Chamberlin-Courant 规则下基于总 (不) 满意度的多赢家决策的复杂性,提供了计算总满意度和总不满意度的适应性和不适应性算法,并通过实验评估验证了这些算法的可用性和优越性。
Dec, 2013
选举中一个重要的问题是确定在一些选票缺失的情况下候选人是否能够成为赢家。我们研究了当选票被截断时的缺失选票决策问题,证明了在单个可转移选票、最低得分和 Copeland 方面,缺失选票决策问题是 NP 完全的,并提出了一种特殊情况的位置评分规则,使问题可以在多项式时间内计算。我们在截断排名中的结果与完整排名的结果不同,因为当候选人数量或缺失选票数量受限时,它们的难度结果仍然成立,而我们则证明该问题在任一情况下都可以在多项式时间内解决。
Oct, 2023