本文研究了投票系统中贿赂问题的计算复杂度,特别关注 Swap Bribery 的 k-approval 情况,并研究了不同成本函数对问题计算复杂性的影响。结果表明,对于某些特定情况,该问题可以用多项式时间解决,而对于更一般化的情况则是 NP 困难的。同时,对于某些自然参数,该问题具有固定参数易解性与 W [1] 难度。
Nov, 2010
本研究发现,在大多数情况下,选举操纵和选举管理的控制可以在多项式时间内成功实现,但生成成功的操纵行为可能需要超出多项式时间。
Feb, 2012
本文着重研究了 Bucklin 和 fallback 投票的计算抗攻击性,针对许多常见的操纵和贿赂情况进行了全面的调查,并考虑了几个 Bucklin 和 fallback 的竞选管理问题。
Jul, 2013
本文研究多个候选人选举中的贿赂问题,分析了各种基于赞成票的多赢家规则的时间复杂度、近似度和可解性,重点研究了参数化的时间复杂度
Apr, 2021
该研究考虑在候选人随时出现的情况下,通过投票选择或拒绝候选人,使用最大期望分数方法来计算委员会并评估其在代表选民方面的比例。
Feb, 2022
本文探讨了在选举中进行贿选的复杂度问题,包括得分协议和 Dodgson 投票等不同的投票系统以及不同情况下的选择。结果表明贿选的复杂度与具体情况密切相关,即使在同一类的选举方式(例如,多数票、Borda、k approval 和 veto 中)中,对加权选民进行贿选的复杂度也可能是 NP 完全的,而对于设定了个人贿选门槛的选民则是 P 的,还有许多分析结果。
Aug, 2006
研究不同投票制度中为什么有些具有轻松操纵的 NP 完全性质,而其他一些则具有较难操纵的多项式时间,发现了多样的嫌恶情感是决定性因素:对于每个给候选人分配两个或两个以上的点值的打分协议选举系统来说,它是 NP 完全的,对于其他系统,则可以多项式时间内操纵。
Apr, 2005
本文研究了多方利益汇聚的漏洞和系统对特定干扰的保护能力,结论是没有一种方法可以完全保护,最终还是要根据控制形式来选择最佳的利益汇聚策略方法。同时,我们也发现在处理数据时某些 tie-handling rules 处理方式的不同会使得漏洞性差异很大。
Jul, 2005
本文提出了一种统一框架来研究少数几种人的选票操作模型,并解决了 R-Swap 贿选问题的复杂性问题,同时发现选票规则的复杂性对贿选问题的难度有很大影响。
Jan, 2018
本文研究使用认可选票选举多个获胜者的三种显著选举法的计算方面,包括满意认可投票、比例认可投票和重新加权认可投票,并证明了比例认可投票的获胜者计算是 NP-hard 问题,研究了这些规则的各种策略性方面和计算复杂性。在许多情况下,本文表明,代理或团体代理人无法根据其他代理人固定的认可选票计算出如何投票最佳的 NP-hard 问题。
Jul, 2014