研究计算社会选择理论中,针对代理人之间的不良行为(如控制、操纵和贿赂)在竞选系统中的复杂性,并以无限多个候选人的无限得分协议为例,将计算复杂度的结果加以泛化,并展示了操纵竞选系统和图形理论问题之间的惊人联系。
May, 2010
本文从经验上研究了单记名再分配投票法(STV)的可操纵性,旨在确定计算复杂度是否真正成为操纵的障碍。作者使用了一系列选票分布,包括均匀分布和真实世界选举,发现几乎每个实验中,单个代理可以轻松地计算出如何操纵选举,或者证明单个代理操纵是不可能的。
研究Monroe规则和Chamberlin-Courant规则下基于总(不)满意度的多赢家决策的复杂性,提供了计算总满意度和总不满意度的适应性和不适应性算法,并通过实验评估验证了这些算法的可用性和优越性。
Dec, 2013
本文研究了三种修改投票规则的方法,即修改计分规则、淘汰制规则和基于竞赛图的规则,并分析了部分投票对计分规则和基于竞赛图的规则中可能出现的策略投票情况及其计算复杂度。
May, 2014
本文使用近似算法的方法定量分析多胜选者投票规则,估计它们与通过审批的 Chamberlin-Courant 规则和多胜选者批准投票中定义的两个极端目标的逼近程度,并通过理论和实验方法将多赢家规则分类到这两个对立目标的数量对齐方面,研究结果提供了关于多赢家规则的基本信息,尤其是在选择这样的规则时必要的权衡。
Jan, 2018
本文研究了基于批准的多赢家选举规则的噪声模型,发现该选举方式对合理噪声始终具有鲁棒性,并提出了按照鲁棒性等级划分的相关规则。
Feb, 2020
本文研究了使用行为数据分析单赢家和多赢家认可投票情景下的投票行为和预测模型,并提出了一种新的模型更有效地捕捉多获胜者认可投票情景中的现实行为。
Dec, 2020
本文研究多个候选人选举中的贿赂问题, 分析了各种基于赞成票的多赢家规则的时间复杂度、近似度和可解性,重点研究了参数化的时间复杂度
Apr, 2021
研究了Minisum批准投票规则的泛化版本Conditional Minisum,在允许选民表达议题间依赖的同时保证了问题的高可计算性,并提供了一些用于该问题的近似和精确算法。
Feb, 2022
通过使用位置多赢投票规则,仅在P≠NP的假设下,研究了如何找到兼具多样性和代表性的委员会的复杂度问题。
Nov, 2022