May, 2011

Borda 操作的复杂性和算法

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

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

    Apr, 2016

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

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

    Jul, 2013

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

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

    May, 2010

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

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

    Jan, 2018

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

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

    May, 2010

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

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

    Feb, 2012

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

    探讨在接近单峰选民群体中进行选举的 manipulative-action 算法的复杂性，提供实例以及研究不同近似程度和不同选举系统的情况下，即使只有一个 dissenter 也能将 manipulative-action 复杂度提高至 NP 完全问题的情况，同时也提供许多实例，可以容忍相当数量的 dissenter 而不增加 manipulative-action 的复杂度。

    May, 2011

  • 选举中可能的获胜者和联盟操纵问题的核化复杂度

    本文针对计算社会选择理论中可能获胜者问题，以及围绕所述问题的投票规则和多项式核心化方面的挑战等，进行了研究，并对常见投票规则的可能获胜者问题是否具有多项式核心化进行了描述，同时，对所研究问题与合谋操纵问题的关系进行了探讨。

    May, 2014

  • 选举中的贿赂有多难？

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

    Aug, 2006

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

    本研究探讨了在多轮选举中通过战略性地打破平局控制选举结果的计算复杂度问题，证明了在这种情况下决定打破平局来保证预定结果是 NP 难的，即使使用两轮投票规则，也不能保证选举不被控制。

    Apr, 2013