有关条件最小和赞成投票在具有相互依赖问题的选举中的计算方面
研究计算社会选择理论中,针对代理人之间的不良行为(如控制、操纵和贿赂)在竞选系统中的复杂性,并以无限多个候选人的无限得分协议为例,将计算复杂度的结果加以泛化,并展示了操纵竞选系统和图形理论问题之间的惊人联系。
May, 2010
研究Monroe规则和Chamberlin-Courant规则下基于总(不)满意度的多赢家决策的复杂性,提供了计算总满意度和总不满意度的适应性和不适应性算法,并通过实验评估验证了这些算法的可用性和优越性。
Dec, 2013
本文研究使用认可选票选举多个获胜者的三种显著选举法的计算方面,包括满意认可投票、比例认可投票和重新加权认可投票,并证明了比例认可投票的获胜者计算是 NP-hard问题,研究了这些规则的各种策略性方面和计算复杂性。在许多情况下,本文表明,代理或团体代理人无法根据其他代理人固定的认可选票计算出如何投票最佳的NP-hard问题。
Jul, 2014
该研究建立了多赢家选举和分配问题之间的联系,通过展示基于批准的多赢家选举规则如何被解释为分配方法。他们考虑了几个多赢家规则,并观察到它们导致在比例代表制文献中得到很好证明的分配方法。例如,他们表明比例批准投票导致D'Hondt方法,而Monroe的规则则导致最大余数方法。他们还考虑了分配方法的性质,并展示了能够满足这些性质的多赢家规则。
Nov, 2016
我们介绍了一种算法框架,用于处理多获胜者投票问题,并在特定属性方面保持公平。该框架可以满足多个非不相交属性的公平性要求,并且可以指定一个评分函数。我们研究了单调和次模评分函数的计算复杂度,针对各种属性组结构和评分函数类型提出了几种近似算法和匹配的近似难度结果。我们还进行了模拟实验,结果表明添加公平约束可能不会对分数产生显著影响。
Oct, 2017
该研究开发出一种新框架,使得计算社会选择与数据库管理之间的联系更紧密,从而使得针对选票规则、候选人、选民、问题和立场的复杂查询能够得到支持,并且研究了相应的计算复杂度。
May, 2018
本文研究多个候选人选举中的贿赂问题, 分析了各种基于赞成票的多赢家规则的时间复杂度、近似度和可解性,重点研究了参数化的时间复杂度
Apr, 2021
通过对候选人的完整排序偏好的难以确定性我们研究了能够通过查询选民关于t < m个候选人的规则计算的投票规则。在先前研究的基础上,我们的研究全面描述了对于任何1≤t < m时可以计算的位置评分规则集合,特别地,这不包括多数派规则。然后,我们将这一结论推广到单可变投票(淘汰投票)中也出现了类似的不可能性结果。这些负面结果是信息理论的,并且与查询数量无关。最后,对于可以用有限大小的查询计算的评分规则,我们针对决定得分最大候选人的确定性或随机算法必须进行的查询数量提供了参数化的上界和下界。对于确定性算法而言,我们的边界是完全相同的,然而对于随机算法而言,确定其精确的查询复杂度是一个具有挑战性的开放问题,我们解决了其中一个特殊情况。
Feb, 2024