# 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 ICM  
Our model is similar to the work presented in [9]. We briefly mention the model bellow. In this model, despite LTM, we assume that the attacker knows the voters' preference list. Each voter \(v\in V\) has a preferences list \(\pi_{v}\). Abusing the notations, \(1\leqslant\pi_{v}(c)\leqslant tk\) is the rank of candidate \(c\) in the preference list of the voter \(v\). After the diffusion, inactive voters will keep their original opinions, i.e., \(\forall v\in V\setminus A_{S}:\tilde{\pi}_{v}=\pi_{v}\); however, the activated voters will change their preferences list as follows. Remind that \(A_{S}\) is the set of activated nodes after \(S\).  
* Constructive: For each node \(v\in A_{S}\) and for each target candidate \(c\in C_{1}\), the new position of \(c\) in \(\tilde{\pi}_{v}\) is \[\tilde{\pi}_{v}(c)=\left\{\begin{array}{ll}\pi_{v}(c)-1&\text{if }\exists\ c^{ \prime}\in C\setminus C_{1}\text{ s.t. }\pi_{v}(c^{\prime})<\pi_{v}(c)\\ \pi_{v}(c)&\text{otherwise,}\end{array}\right.\] also, for other candidates \(c\in C\setminus C_{1}\), if there is a candidate \(c^{\prime}\in C\setminus C_{1}\) s.t. \(\pi_{v}(c^{\prime})=\pi_{v}(c)+1\), then we set \(\tilde{\pi}_{v}(c)=\pi_{v}(c)\); otherwise the new rank of the candidate \(c\) will be calculated as follows. \[\tilde{\pi}_{v}(c)=\pi_{v}(c)+|\{c^{\prime\prime}\in C_{1}\mid\pi_{v}(c^{ \prime\prime})>\pi_{v}(c)\wedge(\
exists\tilde{c}\in C\setminus C_{1}:\pi_{v} (c)<\pi_{v}(\bar{c})<\pi_{v}(c^{\prime\prime}))\}|\;.\]
* Destructive: For each node \(v\in A_{S}\) and for each target candidate \(c\in C_{1}\), we have \[\tilde{\pi}_{v}(c)=\left\{\begin{array}{ll}\pi_{v}(c)+1&\text{if }\exists\ c^{ \prime}\in C\setminus C_{1}\text{ s.t. }\pi_{v}(c^{\prime})>\pi_{v}(c)\\ \pi_{v}(c)&\text{otherwise,}\end{array}\right.\] while for \(c\in C\setminus C_{1}\), if there exists a candidate \(c^{\prime}\in C\setminus C_{1}\) s.t. \(\pi_{v}(c^{\prime})=\pi_{v}(c)-1\) we set \(\tilde{\pi}_{v}(c)=\pi_{v}(c)\), otherwise we have \[\tilde{\pi}_{v}(c)=\pi_{v}(c)-|\{c^{\prime\prime}\in C_{1}\mid\pi_{v}(c^{ \prime\prime})<\pi_{v}(c)\wedge(\
exists\tilde{c}\in C\setminus C_{1}:\pi_{v} (c^{\prime\prime})<\pi_{v}(\bar{c})<\pi_{v}(c))\}|\;.\]  
In this article, we consider the plurality scoring rule for simplicity, where just the most preferred candidate of each voter gets one score. However, the results can be extended for any non-increasing scoring function, e.g., \(k\)-approval, anti-plurality, and [PERSON]'s rule [25]. Let us denote by \(\mathcal{F}(c,\emptyset),\mathcal{F}(c,S)\), the expected score of candidate \(c\) before and after \(S\), respectively; formally, \(\forall c\in C:\mathcal{F}(c,\emptyset)=\sum_{v\in V}\mathds{1}_{\pi_{v}(c)=1 },\mathcal{F}(c,S)=\mathds{E}_{A_{S}}\Big{[}\sum_{v\in V}\mathds{1}_{\pi_{v}( c)=1}\Big{]}\). (If we want to generalize the problem and consider any non-increasing scoring function \(g(\cdot)\), the functions would be defined as \(\mathcal{F}(c,\emptyset)=\sum_{v\in V}g(\pi_{v}(c)),\mathcal{F}(c,S)=\mathds{ E}_{A_{S}}\Big{[}\sum_{v\in V}g(\tilde{\pi}_{v}(c)))|\)).  
**Example 2**.: _Consider the graph \(G\) and candidates \(C\) in Example 1. Let set the voters' preference list as follows._  
\[\pi_{v_{1}} =c_{1}^{1}\succ c_{2}^{1}\succ c_{1}^{2}\succ c_{2}^{2},\] \[\pi_{v_{2}} =c_{1}^{2}\succ c_{2}^{1}\succ c_{1}^{2}\succ c_{2}^{2},\] \[\pi_{v_{3}} =c_{2}^{2}\succ c_{1}^{2}\succ c_{1}^{1}\succ c_{2}^{1},\] \[\pi_{v_{4}} =c_{1}^{2  
\[\pi_{v_{4}} =c_{2}^{1}\succ c_{1}^{1}\succ c_{1}^{2}\succ c_{2}^{2},\] \[\pi_{v5} =c_{1}^{1}\succ c_{2}^{2}\succ c_{2}^{1}\succ c_{1}^{2},\]  
and the candidates' score will be as follows.  
\[\mathcal{F}(c_{1}^{1},S) =\mathcal{F}(c_{2}^{1},S)=2,\] \[\mathcal{F}(c_{1}^{2},S) =0,\] \[\mathcal{F}(c_{2}^{2},S) =1,\]  
and both of the target candidates get more vote than their opponents.