Sequential Manipulation Against Rank Aggregation: Theory and Algorithm

doi:10.1109/TPAMI.2024.3416710

	Sequential Manipulation Against Rank Aggregation: Theory and Algorithm
	Ma, Ke 1; Xu, Qianqian 2; Zeng, Jinshan 3; Liu, Wei 4; Cao, Xiaochun 5; Sun, Yingfei 1; Huang, Qingming 2,6
	2024-12-01
发表期刊	IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE
ISSN	0162-8828
卷号	46 期号:12 页码:9353-9370
摘要	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.
关键词	Online manipulation adversarial learning pairwise comparison ranking aggregation
DOI	10.1109/TPAMI.2024.3416710
收录类别	SCI
语种	英语
资助项目	National Key R&D Program of China[2018AAA0102000] ; National Natural Science Foundation of China[62236008] ; National Natural Science Foundation of China[U21B2038] ; National Natural Science Foundation of China[U23B2051] ; National Natural Science Foundation of China[61931008] ; National Natural Science Foundation of China[62122075] ; National Natural Science Foundation of China[61976202] ; National Natural Science Foundation of China[62025604] ; National Natural Science Foundation of China[62376257] ; National Natural Science Foundation of China[62376110] ; Youth Innovation Promotion Association CAS ; Strategic Priority Research Program of the Chinese Academy of Sciences[XDB0680000] ; Innovation Funding of ICT, CAS[E000000] ; Fundamental Research Funds for the Central Universities ; Thousand Talents Plan of Jiangxi Province[jxsq2019201124] ; Jiangxi Provincial Natural Science Foundation for Distinguished Young Scholars[20224ACB212004] ; Tencent Marketing Solution Rhino-Bird Focused Research Program
WOS研究方向	Computer Science ; Engineering
WOS类目	Computer Science, Artificial Intelligence ; Engineering, Electrical & Electronic
WOS记录号	WOS:001364431200119
出版者	IEEE COMPUTER SOC
引用统计
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/41097
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Xu, Qianqian; Huang, Qingming
作者单位	1.Univ Chinese Acad Sci, Sch Elect Elect & Commun Engn, Beijing 100049, Peoples R China 2.Chinese Acad Sci, Inst Comp Technol, Key Lab Intelligent Informat Proc, Beijing 100190, Peoples R China 3.Jiangxi Normal Univ, Sch Comp & Informat Engn, Nanchang 330022, Jiangxi, Peoples R China 4.Tencent Data Platform, Shenzhen 518054, Peoples R China 5.Sun Yat Sen Univ, Sch Cyber Sci & Technol, Shenzhen Campus, Shenzhen 518107, Peoples R China 6.Univ Chinese Acad Sci, Key Lab Big Data Min & Knowledge Management BDKM, Sch Comp Sci & Technol, Beijing 100049, Peoples R China
推荐引用方式 GB/T 7714	Ma, Ke,Xu, Qianqian,Zeng, Jinshan,et al. Sequential Manipulation Against Rank Aggregation: Theory and Algorithm[J]. IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE,2024,46(12):9353-9370.
APA	Ma, Ke.,Xu, Qianqian.,Zeng, Jinshan.,Liu, Wei.,Cao, Xiaochun.,...&Huang, Qingming.(2024).Sequential Manipulation Against Rank Aggregation: Theory and Algorithm.IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE,46(12),9353-9370.
MLA	Ma, Ke,et al."Sequential Manipulation Against Rank Aggregation: Theory and Algorithm".IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 46.12(2024):9353-9370.