Multi-Winner Election Control via Social Influence: Hardness and Algorithms for Restricted Cases
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 netw...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-10-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/13/10/251 |
| _version_ | 1797551932389195776 |
|---|---|
| author | Mohammad Abouei Mehrizi Gianlorenzo D'Angelo |
| author_facet | Mohammad Abouei Mehrizi Gianlorenzo D'Angelo |
| author_sort | Mohammad Abouei Mehrizi |
| collection | DOAJ |
| description | 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’ 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. |
| first_indexed | 2024-03-10T15:52:45Z |
| format | Article |
| id | doaj.art-57cfd5c213e84931a02a506f617c50ce |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-03-10T15:52:45Z |
| publishDate | 2020-10-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-57cfd5c213e84931a02a506f617c50ce2023-11-20T15:55:40ZengMDPI AGAlgorithms1999-48932020-10-01131025110.3390/a13100251Multi-Winner Election Control via Social Influence: Hardness and Algorithms for Restricted CasesMohammad Abouei Mehrizi0Gianlorenzo D'Angelo1Computer Science Department, Gran Sasso Science Institute (GSSI), Viale Francesco Crispi, 67100 L’Aquila AQ, ItalyComputer Science Department, Gran Sasso Science Institute (GSSI), Viale Francesco Crispi, 67100 L’Aquila AQ, ItalyNowadays, 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’ 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.https://www.mdpi.com/1999-4893/13/10/251computational social choiceelection controlmulti-winner electionsocial influenceinfluence maximization |
| spellingShingle | Mohammad Abouei Mehrizi Gianlorenzo D'Angelo Multi-Winner Election Control via Social Influence: Hardness and Algorithms for Restricted Cases Algorithms computational social choice election control multi-winner election social influence influence maximization |
| title | Multi-Winner Election Control via Social Influence: Hardness and Algorithms for Restricted Cases |
| title_full | Multi-Winner Election Control via Social Influence: Hardness and Algorithms for Restricted Cases |
| title_fullStr | Multi-Winner Election Control via Social Influence: Hardness and Algorithms for Restricted Cases |
| title_full_unstemmed | Multi-Winner Election Control via Social Influence: Hardness and Algorithms for Restricted Cases |
| title_short | Multi-Winner Election Control via Social Influence: Hardness and Algorithms for Restricted Cases |
| title_sort | multi winner election control via social influence hardness and algorithms for restricted cases |
| topic | computational social choice election control multi-winner election social influence influence maximization |
| url | https://www.mdpi.com/1999-4893/13/10/251 |
| work_keys_str_mv | AT mohammadaboueimehrizi multiwinnerelectioncontrolviasocialinfluencehardnessandalgorithmsforrestrictedcases AT gianlorenzodangelo multiwinnerelectioncontrolviasocialinfluencehardnessandalgorithmsforrestrictedcases |