多数否决: 一种实现最优度量扭曲的简单投票规则
研究Monroe规则和Chamberlin-Courant规则下基于总(不)满意度的多赢家决策的复杂性,提供了计算总满意度和总不满意度的适应性和不适应性算法,并通过实验评估验证了这些算法的可用性和优越性。
Dec, 2013
研究度量扭曲问题:有两个点集V和C,它们在相同的度量空间中,我们的目标是选择C中一点,其到V点的总距离尽可能小。我们提出了使用排名作为输入的算法,并提供了它们的扭曲界限。
Apr, 2020
本文研究多个候选人选举中的贿赂问题, 分析了各种基于赞成票的多赢家规则的时间复杂度、近似度和可解性,重点研究了参数化的时间复杂度
Apr, 2021
我们解决了多胜者决策问题在两个投票规则下的参数化复杂性,即 Chamberslin-Courant 规则和 Monroe 规则,并证明了该问题在两个规则下都是 W[1]-hard 难解的。
Feb, 2022
本文研究了基于代理人的顺序偏好设计投票规则的问题,并使用“变形度量”来衡量投票规则的性能,旨在最大化所有代理人的快乐度,文中研究了两个不同的投票变形世界:功利变形和度量变形,并证明了可以通过设计新的投票规则同时达到两种变形下的最优性能。
May, 2023
我们引入了一种新的定义,即在度量空间中,对于一个要表示的集合V(如文件或选民)和一组可能的代表C,我们的标准要求对于V的任何包含theta分数的子集S,S到其在R中最佳的theta*k个点的平均距离与其到C中所有点的最佳theta*k个点的平均距离相比,不超过一个因子gamma。
Dec, 2023
通过对候选人的完整排序偏好的难以确定性我们研究了能够通过查询选民关于t < m个候选人的规则计算的投票规则。在先前研究的基础上,我们的研究全面描述了对于任何1≤t < m时可以计算的位置评分规则集合,特别地,这不包括多数派规则。然后,我们将这一结论推广到单可变投票(淘汰投票)中也出现了类似的不可能性结果。这些负面结果是信息理论的,并且与查询数量无关。最后,对于可以用有限大小的查询计算的评分规则,我们针对决定得分最大候选人的确定性或随机算法必须进行的查询数量提供了参数化的上界和下界。对于确定性算法而言,我们的边界是完全相同的,然而对于随机算法而言,确定其精确的查询复杂度是一个具有挑战性的开放问题,我们解决了其中一个特殊情况。
Feb, 2024