# Multi-Winner Election Control via Social Influence: Hardness and Algorithms for Restricted Cases
## 3 Multi-Winner Election Control: Models and Objective Functions
### Multi-Winner Election Control under LTM  
In this model, we investigate the case that the adversary does not know the preferences list of the voters; instead of that, for each voter, the attacker has a probability distribution over all candidates. This model is similar to the model known as probabilistic linear threshold ranking (PLTR) defined in [8]. Since most voters do not reveal their preferences in social media, then it is a realistic assumption. The adversary tries to maximize/minimize the number of winners in his target party. For each node \(v\in V\), we show \(\pi_{v}\) as the probability distribution of the voter/node \(v\) over all candidates; we define \(\pi_{v}(c)\) as the probability that the voter \(v\) votes for a specific candidate \(c\in C\). Then for every node \(v\in V\), and candidate \(c\in C\) we have \(\pi_{v}(c)\in[0,1]\), and \(\sum_{c\in C}\pi_{v}(c)=1\). In LTM, each node has an incoming influence, which shows the amount of pressure from incoming neighbors to support/oppose a target party. We use this incoming influence of node \(v\in V\) to change its probability distribution. Let us define \(\hat{\pi}_{v}\) as the probability distribution of node \(v\) after \(S\). Respectively, \(\hat{\pi}_{v}(c)\) is the probability that node \(v\) will vote for candidate \(c\in C\) after \(S\). We use \(A_{S}\) to show the set of nodes that will become active after \(S\). We consider a single message which spreads among the voters. The message contains some constructive/destructive information targeting all candidates in the target party. When a node \(v\) becomes active, its probability distribution will change according to the incoming influence from its activated neighbors. We have to normalize the vector in order to make sure that the sum of the probabilities is equal to one, after \(S\). For constructive model the probability distribution of a node \(v\in A_{S}\) changes as follows. \[\forall c\in C_{1}:\hat{\pi}_{v}(c)=\frac{\pi_{v}(c)+\frac{1}{|C_{1}|}\sum_{u \in A_{S}\cap N_{v}^{o}}b_{uv}}{1+\sum_{u\in A_{S}\cap N_{v}^{o}}b_{uv}},\]  
\[\forall c\in C\setminus C_{1}:\hat{\pi}_{v}(c)=\frac{\pi_{v}(c)}{1+\sum_{u\in A _{S}\cap N_{v}^{o}}b_{uv}}.\]Recall that \(N_{v}^{i}\) is the set of incoming neighbors of node \(v\). Furthermore, considering the destructive case, the probability distribution of an active node \(v\in A_{S}\) will change as follows. \[\forall c\in C_{1}:\pi_{v}(c)=\frac{\pi_{v}(c)}{1+\sum_{u\in A_{S} \cap N_{v}^{i}}b_{uv}}\] \[\forall c\in C\setminus C_{1}:\tilde{\pi}_{v}(c)=\frac{\pi_{v}(c) +\frac{1}{|C\setminus C_{1}|}\sum_{u\in A_{S}\cap N_{v}^{i}}b_{uv}}{1+\sum_{u \in A_{S}\cap N_{v}^{i}}b_{uv}}\]  
By these changes (and normalization), we guarantee that the sum of the probability for each node is equal to 1. In both constructive and destructive cases, the probability distribution of inactive nodes \(v\in V\setminus A_{S}\) will not change after \(S\), i.e., \(\pi_{v}=\pi_{v}\). Let us define the expected number of votes for candidate \(c\in C\) after \(S\), as \(\mathcal{F}(c,S)=\mathrm{E}_{A_{S}}[\sum_{v\in V}\pi_{v}(c)]\); similarly, \(\mathcal{F}(c,\emptyset)=\mathrm{E}[\sum_{v\in V}\pi_{v}(c)]\) is the expected number of votes for candidate \(c\in C\) before any diffusion. **Example 1**. : _Assume there are two parties supporting two candidates each, i.e., \(C=C_{1}\cup C_{2}\), \(C_{1}=\{c_{1}^{1},c_{2}^{1}\},C_{2}=\{c_{1}^{2},c_{2}^{2}\}\). There are five nodes in the given graph \(G=(V,E)\), where their connections form a star and the weight of all edges is one, i.e., \((v_{1},v_{2}),(v_{1},v_{3}),(v_{1},v_{4}),(v_{1},v_{5})\in E\), \(b_{v_{1},v_{2}}=b_{v_{1},v_{3}}=b_{v_{1},v_{4}}=b_{v_{1},v_{5}}=1\). Let us consider the probability distribution of each node \(v\in V\) as \(\pi_{v}=\pi_{v}(c_{1}^{1}),\pi_{v}(c_{2}^{1}),\pi_{v}(c_{1}^{2}),\pi_{v}(c_{2}^ {2})\). We set the probability distribution of all nodes as \(\frac{1}{8},\frac{1}{8},\frac{3}{8},\frac{3}{8}\).