Ranking Abuse via Strategic Pairwise Data Perturbations

📄 arXiv: 2604.17805v1 📥 PDF

作者: Junyi Yao, Zihao Zheng, Jiayu Long

分类: cs.LG, cs.AI, cs.GT

发布日期: 2026-04-20

💡 一句话要点

提出自适应子集选择攻击（ASSA）以研究基于MLE排序系统在对抗性扰动下的脆弱性

🎯 匹配领域: 支柱一：机器人控制 (Robot Control)

关键词: 排序系统 对抗攻击 最大似然估计 数据操纵 子集选择 鲁棒性 集体决策

📋 核心要点

  1. 基于MLE的成对排序系统在汇总偏好时被广泛应用，但其在策略性数据操纵下的鲁棒性有待研究。
  2. 论文提出自适应子集选择攻击（ASSA），通过寻找最具影响力的扰动子集，高效攻击MLE排序系统。
  3. 实验表明，少量策略性投票者即可显著改变全局排名，揭示MLE排序机制对结构化扰动的敏感性。

📝 摘要（中文）

本文研究了基于最大似然估计（MLE）的成对排序系统（如Bradley-Terry模型）在策略性数据操纵下的鲁棒性。我们着重研究了MLE排序系统在对抗性扰动下的脆弱性，并将操纵任务建模为一个受约束的组合优化问题，并提出了一种自适应子集选择攻击（ASSA）来有效地识别高影响力扰动。在合成数据和真实选举数据集上的实验结果表明，基于MLE的排序表现出明显的相变行为：超过一个小的扰动预算后，少数具有策略性的投票者可以显著改变全局排名。我们的方法在约束预算下始终优于随机和贪婪基线。这些发现揭示了基于MLE的排序机制对结构化扰动的根本敏感性，并强调了在集体决策系统中需要更鲁棒的聚合方法。

🔬 方法详解

问题定义：论文旨在研究基于最大似然估计（MLE）的成对排序系统，如Bradley-Terry模型，在面对恶意数据扰动时的脆弱性。现有方法缺乏对策略性攻击的有效防御，使得排名结果容易被操纵。具体来说，攻击者可以通过修改少量成对比较结果，显著改变最终的全局排名，从而影响决策过程。

核心思路：论文的核心思路是将攻击问题建模为一个受约束的组合优化问题，目标是找到一组最具影响力的扰动，使得在满足扰动预算约束的前提下，排名结果的变化最大化。为了高效地解决这个NP-hard问题，论文提出了一种自适应子集选择攻击（ASSA）算法。

技术框架：ASSA算法主要包含以下几个阶段：1) 初始化：随机选择一个扰动子集作为初始解。2) 迭代优化：在每次迭代中，算法评估当前扰动子集中每个扰动的边际收益（即移除该扰动后排名结果的变化）。然后，算法选择收益最小的扰动移除，并尝试添加其他未被选择的扰动，以寻找能够最大化排名变化的扰动。3) 收敛判断：当迭代达到最大次数或排名变化小于阈值时，算法停止。

关键创新：ASSA算法的关键创新在于其自适应的子集选择策略。与随机或贪婪方法不同，ASSA能够动态地调整扰动子集，并专注于寻找最具影响力的扰动。通过迭代地评估和替换扰动，ASSA能够更有效地探索搜索空间，从而找到更优的攻击策略。

关键设计：ASSA算法的关键设计包括：1) 扰动预算：限制攻击者可以修改的成对比较结果的数量。2) 排名变化度量：用于衡量排名结果变化的指标，例如Kendall tau距离。3) 边际收益评估：用于评估每个扰动对排名结果的影响。4) 迭代停止条件：用于控制算法的运行时间。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，ASSA算法在合成数据和真实选举数据集上均优于随机和贪婪基线。在有限的扰动预算下，ASSA能够显著改变全局排名，揭示了基于MLE的排名系统对结构化扰动的敏感性。例如，在某些数据集上，仅需修改少量投票即可使特定候选人的排名发生显著变化。

🎯 应用场景

该研究成果可应用于提升在线投票系统、推荐系统和众包平台的安全性。通过理解和量化排名系统在对抗性攻击下的脆弱性，可以设计更鲁棒的排名算法和防御机制，防止恶意用户操纵排名结果，确保公平性和可靠性。未来的研究可以探索更复杂的攻击策略和更有效的防御方法，以应对日益增长的网络安全威胁。

📄 摘要（原文）

Pairwise ranking systems based on Maximum Likelihood Estimation (MLE), such as the Bradley-Terry model, are widely used to aggregate preferences from pairwise comparisons. However, their robustness under strategic data manipulation remains insufficiently understood. In this paper, we study the vulnerability of MLE-based ranking systems to adversarial perturbations. We formulate the manipulation task as a constrained combinatorial optimization problem and propose an Adaptive Subset Selection Attack (ASSA) to efficiently identify high-impact perturbations. Experimental results on both synthetic data and real-world election datasets show that MLE-based rankings exhibit a sharp phase-transition behavior: beyond a small perturbation budget, a limited number of strategic voters can significantly alter the global ranking. In particular, our method consistently outperforms random and greedy baselines under constrained budgets. These findings reveal a fundamental sensitivity of MLE-based ranking mechanisms to structured perturbations and highlight the need for more robust aggregation methods in collective decision-making systems.