研究计算社会选择理论中,针对代理人之间的不良行为(如控制、操纵和贿赂)在竞选系统中的复杂性,并以无限多个候选人的无限得分协议为例,将计算复杂度的结果加以泛化,并展示了操纵竞选系统和图形理论问题之间的惊人联系。
May, 2010
本文从经验上研究了单记名再分配投票法(STV)的可操纵性,旨在确定计算复杂度是否真正成为操纵的障碍。作者使用了一系列选票分布,包括均匀分布和真实世界选举,发现几乎每个实验中,单个代理可以轻松地计算出如何操纵选举,或者证明单个代理操纵是不可能的。
本文证明了一个有两方联盟的问题计算如何操纵Borda投票规则是NP难的,并提出了基于箱装和多处理器调度的两种新的近似方法来计算Borda规则的操纵。实验表明,这些方法明显优于以前已知的近似方法,并能在几乎所有测试的随机生成的选举中找到最佳的操纵结果。结果表明,虽然Borda规则的联盟操纵计算是NP-hard的,但计算复杂度在实践中可能只提供弱障碍。
May, 2011
研究Monroe规则和Chamberlin-Courant规则下基于总(不)满意度的多赢家决策的复杂性,提供了计算总满意度和总不满意度的适应性和不适应性算法,并通过实验评估验证了这些算法的可用性和优越性。
Dec, 2013
本文使用近似算法的方法定量分析多胜选者投票规则,估计它们与通过审批的 Chamberlin-Courant 规则和多胜选者批准投票中定义的两个极端目标的逼近程度,并通过理论和实验方法将多赢家规则分类到这两个对立目标的数量对齐方面,研究结果提供了关于多赢家规则的基本信息,尤其是在选择这样的规则时必要的权衡。
Jan, 2018
介绍一个考虑选民不确定性的新型投票贿赂问题BVU,没有多项式$O(1)$-逼近算法,但有一种返回具有可接受误差的近似算法。
Nov, 2018
本文研究多个候选人选举中的贿赂问题, 分析了各种基于赞成票的多赢家规则的时间复杂度、近似度和可解性,重点研究了参数化的时间复杂度
Apr, 2021
我们解决了多胜者决策问题在两个投票规则下的参数化复杂性,即 Chamberslin-Courant 规则和 Monroe 规则,并证明了该问题在两个规则下都是 W[1]-hard 难解的。
Feb, 2022
通过使用位置多赢投票规则,仅在P≠NP的假设下,研究了如何找到兼具多样性和代表性的委员会的复杂度问题。
Nov, 2022
本研究解决了一个动态偏好的选民如何在两阶段委员会选举中选择最终胜出委员会的问题,特别关注第二阶段的委员会如何尽可能与第一阶段重叠。我们对Thiele规则的复杂性进行全面分析,发现批准投票是可处理的,而其他Thiele规则则普遍为难题,进一步通过实验分析补充理论结果。
Aug, 2024