局部投票对策略投票的计算影响
通过对候选人的完整排序偏好的难以确定性我们研究了能够通过查询选民关于 t <m 个候选人的规则计算的投票规则。在先前研究的基础上,我们的研究全面描述了对于任何 1≤t < m 时可以计算的位置评分规则集合,特别地,这不包括多数派规则。然后,我们将这一结论推广到单可变投票 (淘汰投票) 中也出现了类似的不可能性结果。这些负面结果是信息理论的,并且与查询数量无关。最后,对于可以用有限大小的查询计算的评分规则,我们针对决定得分最大候选人的确定性或随机算法必须进行的查询数量提供了参数化的上界和下界。对于确定性算法而言,我们的边界是完全相同的,然而对于随机算法而言,确定其精确的查询复杂度是一个具有挑战性的开放问题,我们解决了其中一个特殊情况。
Feb, 2024
本文从经验上研究了单记名再分配投票法 (STV) 的可操纵性,旨在确定计算复杂度是否真正成为操纵的障碍。作者使用了一系列选票分布,包括均匀分布和真实世界选举,发现几乎每个实验中,单个代理可以轻松地计算出如何操纵选举,或者证明单个代理操纵是不可能的。
May, 2010
本文探讨了得票规则定义的广泛类别下的可能获胜者问题的计算复杂度,发现对于除了多数制、否决制和得分向量为(2,1,...,1,0)的所有纯得分规则外,所有但一个规则在无限数量的候选人和未加权投票者情况下是 NP 完全的,而他们可以通过多数制和否决制在多项式时间内得出结果。
Nov, 2009
本文探究了在不完整信息情况下的联合操纵问题及其计算性质,并提出了三种自然的操纵计算概念。我们提出的操纵问题在很多情况下都是计算上难以处理的,即使在很少信息缺失的情况下也是如此,这也使得本文的研究有着重要的实际应用意义。
Apr, 2016
本文研究使用认可选票选举多个获胜者的三种显著选举法的计算方面,包括满意认可投票、比例认可投票和重新加权认可投票,并证明了比例认可投票的获胜者计算是 NP-hard 问题,研究了这些规则的各种策略性方面和计算复杂性。在许多情况下,本文表明,代理或团体代理人无法根据其他代理人固定的认可选票计算出如何投票最佳的 NP-hard 问题。
Jul, 2014
研究计算社会选择理论中,针对代理人之间的不良行为(如控制、操纵和贿赂)在竞选系统中的复杂性,并以无限多个候选人的无限得分协议为例,将计算复杂度的结果加以泛化,并展示了操纵竞选系统和图形理论问题之间的惊人联系。
May, 2010
通过使用不同类型的有限信息,我们测量了不同投票方法对权为筹委会选举中的操纵程度,发现某些投票方法,如 Borda 方法,在有限信息下可以被神经网络高度操纵,而其他投票方法,如 Instant Runoff 方法,尽管能被具有完全信息的理想操纵者操纵,但实际上不容易被操纵。
Jan, 2024
研究了委员会选举结果对输入偏好顺序的微小变化的稳健性,探讨了不同投票规则的影响,发现单个偏好顺序内相邻候选人的一次交换可能导致最多一个委员会成员被替换或整个委员会被替换,并证明了计算导致选举结果改变的最小交换数通常是 NP-hard 的,但是存在自然的 FPT 算法,最后对一些规则的实验评估了改变选举结果所需的平均随机交换次数。
Jul, 2017
通过可视化 SNTV、STV、Bloc、k-Borda、Monroe、Chamberlin-Courant 和 HarmonicBorda 等流行的多个获奖选票规则的集体输出,我们研究了生成的按二维欧几里得模型选举的多项获奖投票的三种应用,并使用结果来确定每个应用程序最适合哪些规则。特别地,我们发现 STV 表现出色,而 Bloc 规则表现不佳。
Jan, 2019
本文提出了一种考虑选民有限理性和可靠信息获取的策略性投票模型,该模型基于局部优势的行为启发式方法,建立了投票均衡,证明了其在广泛的局部优势关系中存在,经过大量的仿真实验证明,该模型的这种策略性投票的行为模式模拟了常见的人类投票模式,如杜弗格定律。
Apr, 2014