# Multi-Winner Election Control via Social Influence: Hardness and Algorithms for Restricted Cases
## 6 Multi-Winner Election Control on Tree Using Straight-Party Voting
### Multi-Winner Election Control Using Straight-Party Voting under ICM
#### 6.2.1 Maximizing \(\text{DoV}\) in Straight-Party Voting under ICM  
In this case, node \(v\) can increase our target party's score by one, if none of our target candidates are in the first position before any diffusion, and one of them is in the second position of the voter's preference list. In other words, the voter \(v\) may increase the score of our target party if \(\exists c\in C_{1}\), \(\exists c^{\prime}\in C\setminus C_{1}:\pi_{v}(c^{\prime})=1\wedge\pi_{v}(c)=2\); otherwise, the node \(v\) can influence its children and change their opinion, but it cannot affect the target party's score. We call this condition as pre-condition and show it by \(\mathbb{T}_{v}\). We define \(F_{v}\) as the set of all possible probabilities that the node \(v\) may become active (Please note that the definition of \(F_{v}\) in ICM is different from LTM). Consider a sub-tree rooted at \(v\in V\), budget \(k\), seed set \(S\), and \(p\in F_{v}\), we define \(\text{DoV}_{c}^{\prime}(v,k,S,p)\) as follows. \[\text{DoV}_{c}^{\prime}(v,k,S,p)=max\Big{\{}\\ max_{k^{\prime}=0}^{k}\{\text{DoV}_{c}^{\prime}(r(v),k^{\prime},S,p \cdot b_{v,r(v)})+\text{DoV}_{c}^{\prime}(l(v),k-k^{\prime},S,p\cdot b_{v,l(v) })\}+p\cdot\mathds{1}_{\mathbb{T}_{v}},\\ max_{k^{\prime}=0}^{k-1}\{\text{DoV}_{c}^{\prime}(r(v),k^{\prime},S \cup\{v\},b_{v,r(v)})+\text{DoV}_{c}^{\prime}(l(v),k-k^{\prime}-1,S\cup\{v\}, b_{v,l(v)})\}+\mathds{1}_{\mathbb{T}_{v}}\Big{\}}. \tag{6}\]  
As the base cases of the problem, for each leaf \(v\in V\), budget zero, and \(p\in F_{v}\) as the probability that \(v\) will become active, we set \(\text{DoV}_{c}^{\prime}(v,k,S,p)=p\cdot\mathds{1}_{\mathbb{T}_{v}}\), and for the same parameters except a budget \(k>0\) we set \(\text{DoV}_{c}^{\prime}(v,k,S,p)=\mathds{1}_{\mathbb{T}_{v}}\). (To extend the algorithm for any non-increasing scoring function \(g(\cdot)\), we need to define the base cases, respectively, as \(\text{DoV}_{c}^{\prime}(v,k,S,p)=p\cdot(\sum_{c\in C_{1},\exists c^{\prime} \in C\setminus C_{1}:\pi_{v}(c^{\prime})<\pi_{v}(c)}g(\pi_{v}(c)-1)-g(\pi_{v}(c)))\) and \(\text{DoV}_{c}^{\prime}(v,k,S,p)=\sum_{c\in C_{1},\exists c^{\prime}\in C \setminus C_{1}:\pi_{v}(c^{\prime})<\pi_{v}(c)}g(\pi_{v}(c)-1)-g(\pi_{v}(c))\).) The same as before, for each reference to a node which does not exists (\(null\)), we define \(\text{DoV}_{c}^{\prime}(null,k,S,p)=0\). In order to implement the DP Equation (6), the idea is the same as Algorithm 1. The following theorem shows that it calculates the maximum \(\text{DoV}_{c}^{spv}\) in polynomial-time. **Theorem 7**. : _Given a tree \(T=(V,E)\), and budget \(B\), the DP Equation (6) gives a set of seed nodes \(S\)\((|S|\leqslant B)\) which maximizes \(\text{DoV}_{c}^{\text{Sep}}\)._  
Proof. : In DP Equation (6), there is a maximization over two other maximization formulae. The first one considers the case that we do not select \(v\) as a seed node; in this case, we consider the probability that node \(v\) will become active, i.e., \(p\in F_{v}\). The second maximization considers selecting \(v\) as a seed node; in this state, \(v\) will be activated with probability equal to one. In both cases, the node may increase the function's value if the pre-condition holds; otherwise, it can influence its children. The same as previous proves, we show that it works by induction. Consider a two-dimensional array \(A[B+1,|V|]\) where rows are the budgets from zero to \(B\), and columns are the nodes in BFS reveres order. Each cell \(A[i,j]\)\((0\leqslant i\leqslant B,0\leqslant j<|V|)\) refers to another array \(A^{\prime}\) with the size of \(|F_{v_{j}}|\). We calculate each array related to each cell \((i,j)\) left-to-right and up-down direction. To show that the base cases are correct, note that the leaves cannot activate any other node. Their only effect is by becoming active and changing their own opinion.