# Multi-Winner Election Control via Social Influence: Hardness and Algorithms for Restricted Cases
## 3 Multi-Winner Election Control: Models and Objective Functions
### Objective Functions  
In this paper, our goal is to maximize/minimize the number of winners from our target party. Then the objective functions are the same as [9]. Considering both IC and LT models, we define \(\mathcal{F}(C_{1},S)\) as the number of candidates in \(C_{1}\) that are among the winners. Formally, consider a set of given activated nodes \(A_{S}\), which became active after \(S\). Let us define \(\mathcal{F}_{A_{S}}(c)\) as the expected number of votes that candidate \(c\) will receive while \(A_{S}\) is the set of activated nodes. We set \(\mathcal{Y}_{A_{S}}(c)\) as the number of candidates \(c^{\prime}\in C\setminus\{c\}\) where the expected number of their votes is less than \(c\). In order to consider the tie-breaking rule, if \(\mathcal{F}_{A_{S}}(c_{i}^{j})=\mathcal{F}_{A_{S}}(c_{i^{\prime}}^{j})\), then \(c_{i}^{j}\) has more priority than \(c_{i^{\prime}}^{j}\) if \(j<j^{\prime}\), or \(j=j^{\prime}\wedge i<i^{\prime}\). Then \(\mathcal{Y}_{A_{S}}(c)\) is defined as  
\[\mathcal{Y}_{A_{S}}(c_{i}^{j})=\Big{|}\{c_{i^{\prime}}^{j^{\prime}}\in C\mid \mathcal{F}_{A_{S}}(c_{i}^{j})>\mathcal{F}_{A_{S}}(c_{i^{\prime}}^{j^{\prime}} )\vee(\mathcal{F}_{A_{S}}(c_{i}^{j})=\mathcal{F}_{A_{S}}(c_{i^{\prime}}^{j^{ \prime}})\wedge(j<j^{\prime}\vee(j=j^{\prime}\wedge i<i^{\prime}))\}\Big{|}.\]  
By this definition, we define \(\mathcal{F}(C_{1},S)\) as the expected number of winners from party \(C_{1}\), i.e., \(\mathcal{F}(C_{1},S)=\mathds{E}_{A_{S}}\big{[}\sum_{c\in C_{1}}\mathds{1}_{ \mathcal{Y}_{A_{S}}(c)\geqslant(t-1)k}\big{]}\).  
Now, let us define the first objective function as Difference of Winners (DoW), where is the difference between the number of winners in our target party before and after \(S\). Formally, in constructive (resp., destructive) model we define DoW\({}_{c}\) (resp., DoW\({}_{d}\)) as  
\[\text{DoW}_{c}(C_{1},S) =\mathcal{F}(C_{1},S)-\mathcal{F}(C_{1},\emptyset),\] \[\text{DoW}_{d}(C_{1},S) =\mathcal{F}(C_{1},\emptyset)-\mathcal{F}(C_{1},S).\]  
The problem of constructive difference of winners (CDW) asks for finding a set of seed nodes \(S\) (\(|S|\leqslant B\)) to maximize DoW\({}_{c}(C_{1},S)\). Similarly, destructive difference of winners (DDW) refers to the problem of finding a set of seed node \(S\) (\(|S|\leqslant B\)) to maximize DoW\({}_{d}(C_{1},S)\).  
As the second objective function, we define a more compelling one called Margin of Victory (MoV). For constructive case, we define it as DoW plus the difference between the number of winners in the opponent parties with the most winners after and before \(S\). Formally, for constructive (resp., destructive) case, we define MoV\({}_{c}\) (resp., MoV\({}_{d}\)) as  
\[\text{MoV}_{c}(C_{1},S) =\mathcal{F}(C_{1},S)-\mathcal{F}(C_{A}^{S},S)-\big{(}\mathcal{F} (C_{1},\emptyset)-\mathcal{F}(C_{u},\emptyset)\big{)},\] \[\text{MoV}_{d}(C_{1},S) =\mathcal{F}(C_{1},\emptyset)-\mathcal{F}(C_{u},\emptyset)-\big{(} \mathcal{F}(C_{1},S)-\mathcal{F}(C_{A}^{S},S)\big{)},\]  
where \(C_{u},C_{u}^{S}\), respectively, are the opponent parties with the most winner before and after \(S\).  
The constructive margin of victory (CMV) problem is looking for a set of seed nodes \(S\) (\(|S|\leqslant B\)) in order to maximize MoV\({}_{c}(C_{1},S)\). Similarly, destructive margin of victory (DMV) refers to the problem of finding a set of seed nodes \(S\) (\(|S|\leqslant B\)) to maximize MoV\({}_{d}(C_{1},S)\).