May, 2011

近乎单峰选民制中操纵攻击的复杂度

PDF
TL;DR探讨在接近单峰选民群体中进行选举的 manipulative-action 算法的复杂性，提供实例以及研究不同近似程度和不同选举系统的情况下，即使只有一个 dissenter 也能将 manipulative-action 复杂度提高至 NP 完全问题的情况，同时也提供许多实例，可以容忍相当数量的 dissenter 而不增加 manipulative-action 的复杂度。
electoral briberymanipulative actionspolynomial timesingle-peakedelectorates
发现论文，激发创造
  • 选举操纵问题中的搜索与决策

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

    Feb, 2012

  • 从单峰偏好角度看：具有单峰偏好的社会更容易受到操纵和控制

    本文讨论复杂性和 NP 难度在选举保护中的应用，当选民遵循社会偏好的规范政治科学模型时，基于单峰偏好的选民的复杂性保护从未存在。

    Sep, 2009

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

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

    May, 2010

  • 带有部分信息的投票操纵复杂性

    本文探究了在不完整信息情况下的联合操纵问题及其计算性质，并提出了三种自然的操纵计算概念。我们提出的操纵问题在很多情况下都是计算上难以处理的，即使在很少信息缺失的情况下也是如此，这也使得本文的研究有着重要的实际应用意义。

    Apr, 2016

  • 一个操作问题的统一框架

    本文提出了一种统一框架来研究少数几种人的选票操作模型，并解决了 R-Swap 贿选问题的复杂性问题，同时发现选票规则的复杂性对贿选问题的难度有很大影响。

    Jan, 2018

  • 选举的多模控制攻击

    该研究探讨了选举中的控制攻击，尤其研究了攻击者采用多重攻击模式的情况，提供了处理这种攻击的算法，并证明了在各种选举系统中，甚至可以在确定性多项式时间内完美地计划这样的协同、灵活的攻击。

    Jul, 2010

  • 选举中的贿赂有多难？

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

    Aug, 2006

  • Bucklin 投票和 Fallback 投票中的操纵、贿选和竞选管理复杂度

    本文着重研究了 Bucklin 和 fallback 投票的计算抗攻击性，针对许多常见的操纵和贿赂情况进行了全面的调查，并考虑了几个 Bucklin 和 fallback 的竞选管理问题。

    Jul, 2013

  • Borda 操作的复杂性和算法

    本文证明了一个有两方联盟的问题计算如何操纵 Borda 投票规则是 NP 难的，并提出了基于箱装和多处理器调度的两种新的近似方法来计算 Borda 规则的操纵。实验表明，这些方法明显优于以前已知的近似方法，并能在几乎所有测试的随机生成的选举中找到最佳的操纵结果。结果表明，虽然 Borda 规则的联盟操纵计算是 NP-hard 的，但计算复杂度在实践中可能只提供弱障碍。

    May, 2011

  • 贿赂作为候选人成功的衡量方式：基于批准的多胜者规则的复杂性结果

    本文研究多个候选人选举中的贿赂问题，分析了各种基于赞成票的多赢家规则的时间复杂度、近似度和可解性，重点研究了参数化的时间复杂度

    Apr, 2021