单转移可投票性的实证研究
研究计算社会选择理论中,针对代理人之间的不良行为(如控制、操纵和贿赂)在竞选系统中的复杂性,并以无限多个候选人的无限得分协议为例,将计算复杂度的结果加以泛化,并展示了操纵竞选系统和图形理论问题之间的惊人联系。
May, 2010
本文证明了一个有两方联盟的问题计算如何操纵Borda投票规则是NP难的,并提出了基于箱装和多处理器调度的两种新的近似方法来计算Borda规则的操纵。实验表明,这些方法明显优于以前已知的近似方法,并能在几乎所有测试的随机生成的选举中找到最佳的操纵结果。结果表明,虽然Borda规则的联盟操纵计算是NP-hard的,但计算复杂度在实践中可能只提供弱障碍。
May, 2011
本研究探讨了当操纵者只有部分投票者的信息时的操纵问题,并研究了在不同投票规则下计算占优操纵的难度,同时探讨了如何限制其他投票者信息以防止投票的策略行为。
Jun, 2011
本研究探讨了在多轮选举中通过战略性地打破平局控制选举结果的计算复杂度问题,证明了在这种情况下决定打破平局来保证预定结果是NP难的,即使使用两轮投票规则,也不能保证选举不被控制。
Apr, 2013
本文研究了三种修改投票规则的方法,即修改计分规则、淘汰制规则和基于竞赛图的规则,并分析了部分投票对计分规则和基于竞赛图的规则中可能出现的策略投票情况及其计算复杂度。
May, 2014
本文研究使用认可选票选举多个获胜者的三种显著选举法的计算方面,包括满意认可投票、比例认可投票和重新加权认可投票,并证明了比例认可投票的获胜者计算是 NP-hard问题,研究了这些规则的各种策略性方面和计算复杂性。在许多情况下,本文表明,代理或团体代理人无法根据其他代理人固定的认可选票计算出如何投票最佳的NP-hard问题。
Jul, 2014
本文主要研究多胜选规则下SHIFT BRIBERY问题的复杂性,特别关注于SNTV、Bloc、k-Borda以及Chamberlin-Courant规则及其近似变种的情况,发现当规则基于近似算法时,SHIFT BRIBERY问题的复杂度会受到影响。
Jan, 2016
本文探究了在不完整信息情况下的联合操纵问题及其计算性质,并提出了三种自然的操纵计算概念。我们提出的操纵问题在很多情况下都是计算上难以处理的,即使在很少信息缺失的情况下也是如此,这也使得本文的研究有着重要的实际应用意义。
Apr, 2016
通过对候选人的完整排序偏好的难以确定性我们研究了能够通过查询选民关于t < m个候选人的规则计算的投票规则。在先前研究的基础上,我们的研究全面描述了对于任何1≤t < m时可以计算的位置评分规则集合,特别地,这不包括多数派规则。然后,我们将这一结论推广到单可变投票(淘汰投票)中也出现了类似的不可能性结果。这些负面结果是信息理论的,并且与查询数量无关。最后,对于可以用有限大小的查询计算的评分规则,我们针对决定得分最大候选人的确定性或随机算法必须进行的查询数量提供了参数化的上界和下界。对于确定性算法而言,我们的边界是完全相同的,然而对于随机算法而言,确定其精确的查询复杂度是一个具有挑战性的开放问题,我们解决了其中一个特殊情况。
Feb, 2024