Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Brandt, F., Conitzer, V., Endriss, U., Lang, J., Procaccia, A.D.: Handbook of Computational Social Choice. Cambridge University Press, New York (2016)
Bredereck, R., Chen, J., Faliszewski, P., Nichterlein, A., Niedermeier, R.: Prices matter for the parameterized complexity of shift bribery. Inf. Comput. 251, 140–164 (2016)
Bredereck, R., Faliszewski, P., Niedermeier, R., Talmon, N.: Complexity of shift bribery in committee elections. In: Proceedings of the 30th AAAI Conference on Artificial Intelligence, pp. 2452–2458 (2016)
Brelsford, E., Faliszewski, P., Hemaspaandra, E., Schnoor, H., Schnoor, I.: Approximability of manipulating elections. In: Proceedings of the 23rd AAAI Conference on Artificial Intelligence, vol. 1, pp. 44–49 (2008)
Castiglioni, M., Ferraioli, D., Gatti, N.: Election control in social networks via edge addition or removal. In: Proceedings of the 34th AAAI Conference on Artificial Intelligence, vol. 34, pp. 1878–1885 (2020)
Chekuri, C., Clarkson, K.L., Har-Peled, S.: On the set multicover problem in geometric settings. ACM Trans. Algorithms 9(1), 1–17 (2012)
Chen, L., et al.: Protecting election from bribery: new approach and computational complexity characterization. In: Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems, pp. 1894–1896 (2018)
Corò, F., Cruciani, E., D’Angelo, G., Ponziani, S.: Vote for me! Election control via social influence in arbitrary scoring rule voting systems. In: Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems, pp. 1895–1897 (2019)
Elkind, E., Faliszewski, P.: Approximation algorithms for campaign management. In: Internet and Network Economics, pp. 473–482 (2010)
Elkind, E., Faliszewski, P., Slinko, A.: Swap bribery. In: Proceedings of the 2nd International Symposium on Algorithmic Game Theory, pp. 299–310 (2009)
Faliszewski, P., Gonen, R., Kouteckỳ, M., Talmon, N.: Opinion diffusion and campaigning on society graphs. In: Proceedings of the 27th International Joint Conference on Artificial Intelligence, pp. 219–225 (2018)
Faliszewski, P., Hemaspaandra, E., Hemaspaandra, L.A.: How hard is bribery in elections? J. Artif. Intell. Res. 35, 485–532 (2009)
Faliszewski, P., Hemaspaandra, E., Hemaspaandra, L.A.: Multimode control attacks on elections. J. Artif. Intell. Res. 40, 305–351 (2011)
Faliszewski, P., Reisch, Y., Rothe, J., Schend, L.: Complexity of manipulation, bribery, and campaign management in bucklin and fallback voting. In: Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems, pp. 1357–1358 (2014)
Fowler, E.F., Franz, M., Ridout, T.N.: The big lessons of political advertising in 2018. The Conversation (2018). http://theconversation.com/the-big-lessons-of-political-advertising-in-2018-107673. Accessed 3 Dec
Guo, J., Niedermeier, R.: Exact algorithms and applications for tree-like weighted set cover. J. Discrete Algorithms 4(4), 608–622 (2006)
Hua, Q.S., Yu, D., Lau, F.C., Wang, Y.: Exact algorithms for set multicover and multiset multicover problems. In: Proceedings of the 20th International Symposium on Algorithms and Computation, pp. 34–44 (2009)
Lin, B.: The parameterized complexity of k-biclique. In: Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 605–615 (2014)
Mehrizi, M.A., D’Angelo, G.: Multi-winner election control via social influence: hardness and algorithms for restricted cases. Algorithms 13(10), 251 (2020)
Parkes, D.C., Xia, L.: A complexity-of-strategic-behavior comparison between Schulze’s rule and ranked pairs. In: Proceedings of the 26th AAAI Conference on Artificial Intelligence, pp. 1429–1435 (2012)
Van Bevern, R., Chen, J., Hüffner, F., Kratsch, S., Talmon, N., Woeginger, G.J.: Approximability and parameterized complexity of multicover by c-intervals. Inf. Process. Lett. 115(10), 744–749 (2015)
Wilder, B., Vorobeychik, Y.: Controlling elections through social influence. In: Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems, pp. 265–273 (2018)
Xia, L.: Computing the margin of victory for various voting rules. In: Proceedings of the 13th ACM Conference on Electronic Commerce, pp. 982–999 (2012)
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.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 Springer Nature Switzerland AG
About this paper
Cite this paper
Tao, L. et al. (2022). Hardness and Algorithms for Electoral Manipulation Under Media Influence. In: Chen, J., Li, M., Zhang, G. (eds) Frontiers of Algorithmics. IJTCS-FAW 2021. Lecture Notes in Computer Science(), vol 12874. Springer, Cham. https://doi.org/10.1007/978-3-030-97099-4_4
Download citation
DOI: https://doi.org/10.1007/978-3-030-97099-4_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-97098-7
Online ISBN: 978-3-030-97099-4
eBook Packages: Computer ScienceComputer Science (R0)