TY - GEN
T1 - Hardness and Algorithms for Electoral Manipulation Under Media Influence
AU - Tao, Liangde
AU - Chen, Lin
AU - Xu, Lei
AU - Xu, Shouhuai
AU - Gao, Zhimin
AU - Shi, Weidong
AU - Huang, Dian
N1 - Funding Information:
Acknowledgements. This material is based upon work supported by the “New Generation of AI 2030” major project (2018AAA0100902) and the National Science Foundation under grant no. 1433817.
Publisher Copyright:
© 2022, Springer Nature Switzerland AG.
PY - 2022
Y1 - 2022
N2 - In this paper, we study a generalization of the classic bribery problem known as electoral manipulation under media influence (EMMI). This model is motivated by modern political campaigns where candidates try to convince voters through advertising in media (TV, newspaper, Internet). When compared with the classical bribery problem, the attacker in this setting cannot directly change opinions of individual voters, but instead can execute influences via a set of manipulation strategies (e.g., advertising on a TV channel). Different manipulation strategies incur different costs and influence different subsets of voters. Once receiving a significant amount of influence, a voter will change opinion. To characterize the opinion change of each voter, we adopt the well-accepted threshold model. We prove the NP-hardness of the EMMI problem and give a dynamic programming algorithm that runs in polynomial time for a restricted case of the EMMI problem.
AB - In this paper, we study a generalization of the classic bribery problem known as electoral manipulation under media influence (EMMI). This model is motivated by modern political campaigns where candidates try to convince voters through advertising in media (TV, newspaper, Internet). When compared with the classical bribery problem, the attacker in this setting cannot directly change opinions of individual voters, but instead can execute influences via a set of manipulation strategies (e.g., advertising on a TV channel). Different manipulation strategies incur different costs and influence different subsets of voters. Once receiving a significant amount of influence, a voter will change opinion. To characterize the opinion change of each voter, we adopt the well-accepted threshold model. We prove the NP-hardness of the EMMI problem and give a dynamic programming algorithm that runs in polynomial time for a restricted case of the EMMI problem.
KW - Computational Complexity
KW - Computational Social Choice
KW - Dynamic Programming
UR - http://www.scopus.com/inward/record.url?scp=85126533233&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-97099-4_4
DO - 10.1007/978-3-030-97099-4_4
M3 - Conference contribution
AN - SCOPUS:85126533233
SN - 9783030970987
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 53
EP - 64
BT - Frontiers of Algorithmics - International Joint Conference, IJTCS-FAW 2021, Proceedings
A2 - Chen, Jing
A2 - Li, Minming
A2 - Zhang, Guochuan
PB - Springer Science and Business Media Deutschland GmbH
T2 - 15th International Workshop on Frontiers in Algorithmics, FAW 2021, held in conjunction with 2nd International Joint Conference on Theoretical Computer Science, IJTCS-FAW 2021
Y2 - 16 August 2021 through 19 August 2021
ER -