{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:18:35Z","timestamp":1760239115483,"version":"build-2065373602"},"reference-count":33,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2020,10,2]],"date-time":"2020-10-02T00:00:00Z","timestamp":1601596800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Nowadays, many political campaigns are using social influence in order to convince voters to support\/oppose a specific candidate\/party. In election control via social influence problem, an attacker tries to find a set of limited influencers to start disseminating a political message in a social network of voters. A voter will change his opinion when he receives and accepts the message. In constructive case, the goal is to maximize the number of votes\/winners of a target candidate\/party, while in destructive case, the attacker tries to minimize them. Recent works considered the problem in different models and presented some hardness and approximation results. In this work, we consider multi-winner election control through social influence on different graph structures and diffusion models, and our goal is to maximize\/minimize the number of winners in our target party. We show that the problem is hard to approximate when voters\u2019 connections form a graph, and the diffusion model is the linear threshold model. We also prove the same result considering an arborescence under independent cascade model. Moreover, we present a dynamic programming algorithm for the cases that the voting system is a variation of straight-party voting, and voters form a tree.<\/jats:p>","DOI":"10.3390\/a13100251","type":"journal-article","created":{"date-parts":[[2020,10,2]],"date-time":"2020-10-02T09:39:25Z","timestamp":1601631565000},"page":"251","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Multi-Winner Election Control via Social Influence: Hardness and Algorithms for Restricted Cases"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8772-8904","authenticated-orcid":false,"given":"Mohammad","family":"Abouei Mehrizi","sequence":"first","affiliation":[{"name":"Computer Science Department, Gran Sasso Science Institute (GSSI), Viale Francesco Crispi, 67100 L\u2019Aquila AQ, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gianlorenzo","family":"D'Angelo","sequence":"additional","affiliation":[{"name":"Computer Science Department, Gran Sasso Science Institute (GSSI), Viale Francesco Crispi, 67100 L\u2019Aquila AQ, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,10,2]]},"reference":[{"key":"ref_1","unstructured":"Matsa, K.E., and Shearer, E. (2018). News Use Across Social Media Platforms 2018, Pew Research Center."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1038\/nature11421","article-title":"A 61-million-person experiment in social influence and political mobilization","volume":"489","author":"Bond","year":"2012","journal-title":"Nature"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Ferrara, E. (2017). Disinformation and social bot operations in the run up to the 2017 French presidential election. First Monday, 22.","DOI":"10.5210\/fm.v22i8.8005"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1473","DOI":"10.1177\/1461444814562445","article-title":"Seizing the moment: The presidential campaigns\u2019 use of Twitter during the 2012 electoral cycle","volume":"18","author":"Kreiss","year":"2016","journal-title":"New Media Soc."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1080\/10584609.2017.1334728","article-title":"Election Campaigning on Social Media: Politicians, Audiences, and the Mediation of Political Communication on Facebook and Twitter","volume":"35","author":"Stier","year":"2018","journal-title":"Political Commun."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1257\/jep.31.2.211","article-title":"Social media and fake news in the 2016 election","volume":"31","author":"Allcott","year":"2017","journal-title":"J. Econ. Perspect."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"105","DOI":"10.4086\/toc.2015.v011a004","article-title":"Maximizing the Spread of Influence through a Social Network","volume":"11","author":"Kempe","year":"2015","journal-title":"Theory Comput."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Abouei Mehrizi, M., Cor\u00f2, F., Cruciani, E., and D\u2019Angelo, G. (2020, January 29\u201331). Election control through social influence with unknown preferences. Proceedings of the 2020 International Computing and Combinatorics Conference, Atlanta, GA, USA.","DOI":"10.1007\/978-3-030-58150-3_32"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1007\/978-3-030-54921-3_19","article-title":"Multi-winner election control via social influence","volume":"Volume 12156","author":"Richa","year":"2020","journal-title":"Proceedings of the Structural Information and Communication Complexity\u201427th International Colloquium (SIROCCO 2020)"},{"key":"ref_10","unstructured":"Wilder, B., and Vorobeychik, Y. (2018, January 10\u201315). Controlling elections through social influence. Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), Stockholm, Sweden."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Faliszewski, P., Rothe, J., and Moulin, H. (2016). Control and Bribery in Voting, Handbook of Computational Social Choice; Cambridge University Press.","DOI":"10.1017\/CBO9781107446984.008"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"3417","DOI":"10.1007\/s10115-020-01461-4","article-title":"A survey on influence maximization in a social network","volume":"62","author":"Banerjee","year":"2020","journal-title":"Knowl. Inf. Syst."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Domingos, P., and Richardson, M. (2001, January 26\u201329). Mining the network value of customers. Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA.","DOI":"10.1145\/502512.502525"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Richardson, M., and Domingos, P. (2001, January 23\u201326). Mining knowledge-sharing sites for viral marketing. Proceedings of the 2002 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Edmonton, AB, USA.","DOI":"10.1145\/775047.775057"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Kempe, D., Kleinberg, J., and Tardos, \u00c9. (2003, January 24\u201327). Maximizing the spread of influence through a social network. Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA.","DOI":"10.1145\/956750.956769"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Cor\u00f2, F., Cruciani, E., D\u2019Angelo, G., and Ponziani, S. (2019, January 10\u201316). Exploiting social influence to control elections based on scoring rules. Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), Macao, China.","DOI":"10.24963\/ijcai.2019\/29"},{"key":"ref_17","unstructured":"Cor\u00f2, F., Cruciani, E., D\u2019Angelo, G., and Ponziani, S. (2019, January 13\u201317). Vote for me!: Election control via social influence in arbitrary scoring rule voting systems. Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS \u201919), Montreal, QC, Canada."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Bredereck, R., and Elkind, E. (2017, January 19\u201325). Manipulating opinion diffusion in social networks. Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI), Melbourne, Australia.","DOI":"10.24963\/ijcai.2017\/124"},{"key":"ref_19","unstructured":"Castiglioni, M., Ferraioli, D., and Gatti, N. (2020, January 7\u201312). Election control in social networks via edge addition or removal. Proceedings of the 2020 AAAI Conference on Artificial Intelligence, New York, NY, USA."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Faliszewski, P., Gonen, R., Kouteck\u00fd, M., and Talmon, N. (2018, January 13\u201319). Opinion diffusion and campaigning on society graphs. Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI), Stockholm, Sweden.","DOI":"10.24963\/ijcai.2018\/30"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Auletta, V., Caragiannis, I., Ferraioli, D., Galdi, C., and Persiano, G. (2015, January 9\u201312). Minority becomes majority in social networks. Proceedings of the 11th Web and Internet Economics (WINE), Amsterdam, The Netherlands.","DOI":"10.1007\/978-3-662-48995-6_6"},{"key":"ref_22","unstructured":"Brill, M., Elkind, E., Endriss, U., and Grandi, U. (2016, January 9\u201315). Pairwise diffusion of preference rankings in social networks. Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI), New York, NY, USA."},{"key":"ref_23","unstructured":"Botan, S., Grandi, U., and Perrussel, L. (2017, January 8). Propositionwise opinion diffusion with constraints. Proceedings of the 4th AAMAS Workshop (EXPLORE), Sao Paulo, Brazil."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"1852","DOI":"10.1109\/TKDE.2018.2807843","article-title":"Influence Maximization on Social Graphs: A Survey","volume":"30","author":"Li","year":"2018","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Brandt, F., Conitzer, V., Endriss, U., Lang, J., and Procaccia, A.D. (2016). Handbook of Computational Social Choice, Cambridge University Press. [1st ed.].","DOI":"10.1017\/CBO9781107446984.002"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Bharathi, S., Kempe, D., and Salek, M. (2007). Competitive influence maximization in social networks. International Workshop on Web and Internet Economics, Springer.","DOI":"10.1007\/978-3-540-77105-0_31"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"803","DOI":"10.1007\/s10878-016-0006-z","article-title":"Solution of Bharathi\u2013Kempe\u2013Salek conjecture for influence maximization on arborescence","volume":"33","author":"Lu","year":"2017","journal-title":"J. Comb. Optim."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"1678","DOI":"10.1007\/s10878-016-9991-1","article-title":"On Bharathi\u2013Kempe\u2013Salek conjecture for influence maximization on arborescence","volume":"31","author":"Wang","year":"2016","journal-title":"J. Comb. Optim."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Abouei Mehrizi, M., and D\u2019Angelo, G. (2020). Multi-Winner Election Control via Social Influence. arXiv.","DOI":"10.1007\/978-3-030-54921-3_19"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1109\/TIFS.2009.2031947","article-title":"Straight-party voting: What do voters think?","volume":"4","author":"Campbell","year":"2009","journal-title":"IEEE Trans. Inf. Forensics Secur."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1086\/685661","article-title":"Roll-Off in State Court Elections: Change Over Time and the Impact of the Straight-Ticket Voting Option","volume":"4","author":"Kritzer","year":"2016","journal-title":"J. Law Court"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Ruhl, J., and Mcdonald, R. (2019). Party Politics And Elections In Latin America, Taylor & Francis.","DOI":"10.4324\/9780429301087"},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Hershey, M. (2017). Party Politics in America, Taylor & Francis.","DOI":"10.4324\/9781315544427"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/10\/251\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:16:04Z","timestamp":1760177764000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/10\/251"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,2]]},"references-count":33,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2020,10]]}},"alternative-id":["a13100251"],"URL":"https:\/\/doi.org\/10.3390\/a13100251","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2020,10,2]]}}}