Sequential Manipulation Against Rank Aggregation: Theory and Algorithm

Abstract

Rank aggregation with pairwise comparisons is widely encountered in sociology, politics, economics, psychology, sports, etc . Given the enormous social impact and the consequent incentives, the potential adversary has a strong motivation to manipulate the ranking list. However, the ideal attack opportunity and the excessive adversarial capability cause the existing methods to be impractical. To fully explore the potential risks, we leverage an online attack on the vulnerable data collection process. Since it is independent of rank aggregation and lacks effective protection mechanisms, we disrupt the data collection process by fabricating pairwise comparisons without knowledge of the future data or the true distribution. From the game-theoretic perspective, the confrontation scenario between the online manipulator and the ranker who takes control of the original data source is formulated as a distributionally robust game that deals with the uncertainty of knowledge. Then we demonstrate that the equilibrium in the above game is potentially favorable to the adversary by analyzing the vulnerability of the sampling algorithms such as Bernoulli and reservoir methods. According to the above theoretical analysis, different sequential manipulation policies are proposed under a Bayesian decision framework and a large class of parametric pairwise comparison models. For attackers with complete knowledge, we establish the asymptotic optimality of the proposed policies. To increase the success rate of the sequential manipulation with incomplete knowledge, a distributionally robust estimator, which replaces the maximum likelihood estimation in a saddle point problem, provides a conservative data generation solution. Finally, the corroborating empirical evidence shows that the proposed method manipulates the results of rank aggregation methods in a sequential manner.

Accepted by IEEE TPAMI URL: https://ieeexplore.ieee.org/document/10564181

References in corpus (9)

• Spectral Method and Regularized MLE Are Both Optimal for Top-$K$ Ranking
• A Survey of Game Theoretic Approaches for Adversarial Machine Learning in Cybersecurity Tasks
• Poisoning Attack against Estimating from Pairwise Comparisons
• Lagrangian Inference for Ranking Problems
• A Tale of HodgeRank and Spectral Method: Target Attack Against Rank Aggregation Is the Fixed Point of Adversarial Game
• 1-Wasserstein Distance on the Standard Simplex
• Generalized Results for the Existence and Consistency of the MLE in the Bradley-Terry-Luce Model
• Optimal Full Ranking from Pairwise Comparisons
• Asymptotically Optimal Sequential Design for Rank Aggregation