# Multi-Winner Election Control via Social Influence: Hardness and Algorithms for Restricted Cases
## 1 Introduction
[PERSON] and [PERSON] [13; 14] introduced the IM problem, and [PERSON] et al. formalized it [7; 15]. On the other hand, few works consider both of them together, i.e., the election control through social influence problem. [PERSON] and [PERSON] introduced the election control through SI problem regarding single-winner elections [10]. They investigated maximizing margin of victory (MoV) and probability of victory (PoV), where MoV is the difference of the score between the target candidate and the most voted opponent after and before the diffusion. The problem is considered under ICM. They showed maximizing MoV is \(NP\)-hard, and presented a \(1-\frac{1}{e}\)-approximation algorithm concerning the optimal solution. Furthermore, for maximizing PoV, they showed that it is \(NP\)-hard to approximate the problem within any constant factor. [PERSON] et al. [16; 17] extended the work using any non-increasing scoring function under LTM. They demonstrated the same approximation factor for it. [PERSON] et al. considered the problem when the attacker knows a probability distribution over the candidates instead of the exact preferences list, under LTM [8]. They showed that maximizing/minimizing the expected probability to vote for a target candidate is hard to approximate within any constant factor under unique game with small set expansion conjecture. They also presented some constant factor approximation algorithms for a relaxed version of the problem. [PERSON] and [PERSON] showed that in multi-winner elections, when the manipulator wants to maximize/minimize the number of winners in his target party, the problem is inapproximable under ICM, except \(P=NP\)[9]. They also presented some constant factor approximation algorithms when the voting system is similar to the straight-party voting. [PERSON] and [PERSON] considered some different models, like bribing nodes/voters, adding or deleting edges under LTM. They showed that the problem is hard in those models. They also presented some polynomial-time algorithms for specific cases of the problem [18]. [PERSON] et al. investigated similar models under ICM. They showed that the problem is hard even in restricted structures. Regarding the bribing nodes to influence other voters, they proved that the election control is hard even if the given graph is a line. Furthermore, considering the edge removal/additioncase, they demonstrated that the problem is hard even if the attacker has an infinite budget [19]. [PERSON] et al. considered the problem where each voter has a preference list. Each node of the graph is representative of all users with the same opinions. There is an edge between two nodes if their opinion differs by the place of an adjacent pair of candidates. They used LTM and proved that maximizing the number of votes for the target candidate is _NP_-hard and fixed parameter tractable with respect to the number of candidates [20]. Furthermore, there is another model in which voters have a preference list over candidates, and voters will change their preference list according to the majority of their neighbors' opinions [21; 22; 23]. Outline and our results. In Section 2, we define the most prominent diffusion models in the literature (called LTM and ICM) that we used in this paper. Section 3 defines our model and objective functions formally. We show that our problem is hard to approximate within any factor in a general graph when the diffusion model is LTM in Section 4. Section 5 contains the same result when the diffusion model is ICM, and the given graph is in the form of an arborescence, i.e., edges are from leaves to root of the tree. Moreover, in Section 6, we investigate the problem while the voting system is a variation of straight-party voting, where voters can vote for the parties. In other words, voters have a preference list (or probability distribution) over the candidates, but they can vote for the parties instead of candidates.