# Multi-Winner Election Control via Social Influence: Hardness and Algorithms for Restricted Cases
## 1 Introduction  
Social media is an integral part of nowadays life. No one can ignore the effect of social media on different aspects of our life. Many people from all around the world are using social networks to provide/use various services like teaching/learning, spreading information, events' announcements, and advertising. It has been shown that two-thirds of American adults get news on social mediaSM [1]. It is easy to find evidence that a social influence (SI) started by few users has influenced many people. Then, social media is a kind of cheap means to spread a message among many users. Note that the power of social media is not just like spreading a message or advertising. Its power comes from the fact that a user will receive news from those who have enough authority to change his opinion, like close friends, family members, and colleagues. Since using social influence is effective and cheap, it has been attracting the attention of many political campaigns and candidates to target the user's opinion through SI. They disseminate a piece of information to change voters' opinion. Many real case studies show that campaigns used social influence to change the voters' opinion [2; 3; 4; 5]. For example, [PERSON] and [PERSON] showed that 92% of Americans remembered pro-Trump false news, and 23% remembered pro-Clinton fake news [6]. There are two well-known diffusion models used in social influence called linear threshold model (LTM) and Independent Cascade Model (ICM) [7]. In LTM, a voter accepts a message if the sum over his incoming neighbors' influence, who already accepted the message, is high enough. On the other hand, in ICM, a voter will accept a message if at least one of his incoming neighbors, who alreadyaccepted the message, can convince him to accept it (please see Section 2 for a formal definition of LTM and ICM). In this paper, we consider the multi-winner election control via social influence problem. We are given a social network of voters, a limited budget, a set of candidates each belongs to a party, a dynamic diffusion model to spread a message among the voters, and an attacker/manipulator who supports/opposes a party. When we use LT diffusion model, we assume that the attacker knows the probability that each voter wants to vote for each candidate. To take into account the incoming influence of each node \(v\), we use an updating rule based on the incoming influence from the node's incoming activated neighbors, akin to [8]. On the other hand, when we use ICM, we assume the attacker knows the exact preferences list of all voters. When a node/voter becomes active/influenced/infected, in constructive (resp. destructive) case, it will promote (resp. demote) the position of the target candidates in its/his preference list, akin to [9; 10] (see Section 3 for formal definition). Regarding both LTM and ICM, there will be several winners, and they will be elected according to the overall candidates' scores after the diffusion. In the constructive (resp. destructive) case, the attacker wants to find a set of nodes (voters), according to its budget, to start the diffusion and change the voters' opinion to maximize (resp. minimize) the number of winners from his target party. In fact, in a given directed graph, we should find some diffusion starters to influence the voters such that the difference between the number of winners from our target party, w.r.t. the number of winners in the opponent party with the most winners, after and before the diffusion is maximized (resp. minimized). We present some results, including hardness of approximation, approximation, and polynomial-time exact algorithms considering some well-known objective functions on different structures. Related works. There are many articles regarding voting manipulation (see the survey in [11]). The problem of finding a set of limited seed nodes from a given graph to maximize the expected number of influenced nodes is known as Influence Maximization (IM) problem. There exists an extensive literature about it, too [12].