← 返回论文列表

贿赂对排名聚合的影响
Bribery's Influence on Ranked Aggregation

作者: Pallavi Jain, Anshul Thakur
arXiv: 2603.28574v1
分类: cs.GT, cs.CC
📝 论文摘要
Kemeny共识是社会选择理论中一种著名的排序聚合方法。该方法在给定一组排序的情况下，旨在找到一个排序$Π$，使得其与输入排序之间的总Kendall tau距离最小化。计算Kemeny共识是NP难问题，甚至验证给定排序是否为Kemeny共识也是coNP完全问题。Fitzsimmons与Hemaspaandra [IJCAI 2021] 通过操纵性操作证明了实现期望共识的计算不可行性。Kemeny共识是与Kemeny规则相关的优化问题。本文研究一个与Kemeny规则相关的判定问题——Kemeny分值问题，其目标是判定是否存在一个排序$Π$，使得其与给定排序之间的总Kendall tau距离不超过$k$。已知Kemeny分值的计算属于NP完全问题。本文探讨了多种操纵行为对Kemeny分值问题的影响：在给定一组排序、整数$k$及排序$X$的前提下，判定是否可能通过操纵给定排序，使得$X$与操纵后排序的总Kendall tau距离不超过$k$。我们证明该问题在多种操纵行为下均存在多项式时间解法。值得注意的是，这些相同的操纵行为在Kemeny共识问题中已被证明具有计算复杂性。

📊 核心分析

🎯 研究动机
该论文旨在研究操纵行为对排名聚合问题的影响。研究背景是： - Kemeny共识(Kemeny Consensus)是社会选择理论中著名的排名聚合方法，但计算复杂度高（NP难） - 已有研究证明通过操纵行为达成期望共识是计算困难的 - 本文聚焦于Kemeny规则的决策问题版本——Kemeny分数(Kemeny Score)问题
🔧 核心方法
论文采用以下技术方法： - 研究Kemeny分数(Kemeny Score)决策问题的操纵变体：给定一组排名、整数k和目标排名X，判断是否可以通过操纵使X与操纵后排名的总肯德尔τ距离(Kendall tau distance)不超过k - 分析多种具体操纵行为（如贿赂(bribery)、控制(control)等）对该问题的影响 - 使用计算复杂性理论方法，证明该操纵问题在多项式时间内可解
💡 核心创新
论文的核心创新点在于发现了计算复杂性的“反转现象”： - 针对Kemeny分数(Kemeny Score)的操纵问题，证明多种操纵行为可以在多项式时间内解决 - 这与已知结论形成鲜明对比：同样的操纵行为对Kemeny共识(Kemeny Consensus)问题是计算困难的（NP难） - 揭示了同一排名聚合规则不同问题变体（优化vs决策）对操纵行为具有完全不同的计算复杂性特征
🏆 总体贡献
论文对该领域的整体贡献包括： - 首次系统分析了操纵行为对Kemeny分数问题的计算复杂性影响 - 发现了排名聚合中操纵问题复杂性的重要不对称性：决策问题比优化问题更容易被操纵 - 为社会选择理论的计算方面提供了新的理论见解，特别是关于规则鲁棒性与问题表述形式的关系 - 为设计抗操纵的排名聚合机制提供了理论基础