# 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 LTM
#### 6.1.1 Maximizing \(\mathrm{DoV}\) in Straight-Party Voting under LTM
The last term in each maximization is the increased amount of \(\text{DoV}_{c}\) in the node \(v_{j}\), which is according to the probability that \(v_{j}\) will become active. Note that in the above formula, we are using the value of \(\text{DoV}_{c}\) for the children of \(v_{j}\), and the nodes are sorted as the BFS reverse order, then all required values are correctly calculated before, and we are selecting the maximum value among all possible cases. Then \(\text{DoV}_{c}(v_{j},i,S,p)\) will find the maximum possible value of \(\text{DoV}_{c}^{spv}\) correctly and concludes the proof. For the destructive model, we define \(\text{DoV}_{d}(v,k,S,p)\) as the maximum difference of probability to vote for our target party before and after \(S\) in the sub-tree rooted at \(v\), while the budget is \(k\) and \(p\in F_{v}\) is the probability that \(f(v)\) will become active. Formally, we define \(\text{DoV}_{d}(v,k,S,p)\) as follows. \[\text{DoV}_{d}(v,k,S,p)=max\Bigg{\{}\\ max_{k^{\prime}=0}^{k}\Big{\{}\text{DoV}_{d}\left(r(v),k^{\prime},S,p \cdot b_{f(v),p}\right)+\text{DoV}_{d}\left(l(v),k-k^{\prime},S,p\cdot b_{f(v),p }\right)\Big{\}}+p\cdot b_{f(v),p}\cdot\mathcal{D}^{\prime}_{v},\\ max_{k^{\prime}=0}^{k-1}\Big{\{}\text{DoV}_{d}\left(r(v),k^{ \prime},S\cup\{v\},1\right)+\text{DoV}_{d}\left(l(v),k-k^{\prime}-1,S\cup\{v \},1\right)\Big{\}}+\mathcal{D}^{\prime}_{v}\Bigg{\}}, \tag{5}\]  
where \(\mathcal{D}^{\prime}_{v}=\sum_{c\in C_{1}}\left(\pi_{v}(c)-\frac{\pi_{v}(c)}{ 1+p\cdot b_{f(v),p}}\right)\) is the difference that the node \(v\) can apply. Moreover, for the base cases of the problem, for each leaf \(v\in V\), and each probability \(p\in F_{v}\), if \(k=0\) we need to consider the probability that the node will become active, then \(\text{DoV}_{d}(v,k,S,p)=p\cdot b_{f(v),p}\cdot\mathcal{D}^{\prime}_{v}\); otherwise, if \(k>0\), we have \(\text{DoV}_{d}(v,k,S,p)=\mathcal{D}^{\prime}_{v}\). Furthermore, we set \(\text{DoV}_{c}(null,k,S,p)=0\). The same as constructive case, for implementation we need a tow-dimensional array \(A[B+1,|V|]\). Moreover, for each cell \((i,j),0\leqslant i\leqslant B,0\leqslant j<|V|\), we keep another array \(A^{\prime}[|F_{v_{j}}|]\), where \(F_{v_{j}}\) is the set of possible probabilities that the node \(f(v_{j})\) can become active. The following theorem shows that by filling the matrix \(A\) left-to-right and up-down direction, we can find the optimal answer for \(\text{DoV}_{d}^{spv}\). Theorem 5.1: _Given a tree \(T=(V,E)\) and a budget \(B\), using the DP Equation (5), we can find a set of seed nodes \(S\left(|S|\leqslant B\right)\) to maximize \(\text{DoV}_{d}^{spv}\)._  
Proof. : The proof is similar to Theorem 5.1, except for the base cases and the way of updating each activated node's probability distribution after the diffusion. Since a leaf cannot activate any other node, the only change that it can make is updating its own probability distribution. According to the updating rule (in Section 3.1), and the definition of \(\text{DoV}_{d}^{spv}\) (defined in Equation (2)), the base cases hold. Furthermore, by induction, we can see that the DP Equation (5) will find the maximum value of \(\text{DoV}_{d}^{spv}\) correctly.