Apr, 2013

通过打平票来操纵选举的难度有多大？

PDF
TL;DR本研究探讨了在多轮选举中通过战略性地打破平局控制选举结果的计算复杂度问题，证明了在这种情况下决定打破平局来保证预定结果是 NP 难的，即使使用两轮投票规则，也不能保证选举不被控制。
computational complexityelection controltie-breaking functionmulti-round electionsvoting rule
发现论文，激发创造
  • 混合选举拓宽了复杂度理论对控制的抵抗

    本研究介绍了一种将两种或更多候选人匿名选举方案相结合的方法，并研究了一种构建防范所有 20 种标准选举控制方法的选举方案。

    Aug, 2006

  • 少数选民的选举：候选人控制容易实现

    本文研究针对选民人数为参数的选举候选人控制的计算复杂度，并考虑了添加和删除候选人以及组合情景。在考虑几个基本投票规则时，结果显示，以选民人数为参数的候选人控制的计算复杂度比许多选民时的设置更加多样化。

    Nov, 2014

  • 加权选举控制

    本文研究加权选举结果的控制问题，通过添加和删除选民探讨了研究有分值规则的加权选举结果控制的复杂度，得到了针对许多 NP 完全情况的多项式时间算法和近似算法。

    May, 2013

  • 任何人都不行：排除替代方案的复杂性

    本文研究了多方利益汇聚的漏洞和系统对特定干扰的保护能力，结论是没有一种方法可以完全保护，最终还是要根据控制形式来选择最佳的利益汇聚策略方法。同时，我们也发现在处理数据时某些 tie-handling rules 处理方式的不同会使得漏洞性差异很大。

    Jul, 2005

  • 选举中的贿赂有多难？

    本文探讨了在选举中进行贿选的复杂度问题，包括得分协议和 Dodgson 投票等不同的投票系统以及不同情况下的选择。结果表明贿选的复杂度与具体情况密切相关，即使在同一类的选举方式（例如，多数票、Borda、k approval 和 veto 中）中，对加权选民进行贿选的复杂度也可能是 NP 完全的，而对于设定了个人贿选门槛的选民则是 P 的，还有许多分析结果。

    Aug, 2006

  • 控制 k - 表决选举的复杂性

    研究计算社会选择理论中，针对代理人之间的不良行为（如控制、操纵和贿赂）在竞选系统中的复杂性，并以无限多个候选人的无限得分协议为例，将计算复杂度的结果加以泛化，并展示了操纵竞选系统和图形理论问题之间的惊人联系。

    May, 2010

  • 嘈杂选举中可能获胜者

    文章研究了选举中预测获胜者的问题，给出了根据不同选举规则计算加减候选人和选民的控制变体的算法和 #P - 完全性结果。

    May, 2014

  • 多获胜者投票规则中的稳健性

    研究了委员会选举结果对输入偏好顺序的微小变化的稳健性，探讨了不同投票规则的影响，发现单个偏好顺序内相邻候选人的一次交换可能导致最多一个委员会成员被替换或整个委员会被替换，并证明了计算导致选举结果改变的最小交换数通常是 NP-hard 的，但是存在自然的 FPT 算法，最后对一些规则的实验评估了改变选举结果所需的平均随机交换次数。

    Jul, 2017

  • 选举操纵问题中的搜索与决策

    本研究发现，在大多数情况下，选举操纵和选举管理的控制可以在多项式时间内成功实现，但生成成功的操纵行为可能需要超出多项式时间。

    Feb, 2012

  • 单转移可投票性的实证研究

    本文从经验上研究了单记名再分配投票法 (STV) 的可操纵性，旨在确定计算复杂度是否真正成为操纵的障碍。作者使用了一系列选票分布，包括均匀分布和真实世界选举，发现几乎每个实验中，单个代理可以轻松地计算出如何操纵选举，或者证明单个代理操纵是不可能的。

    May, 2010