# 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
Then there are two cases if the pre-condition holds for a leaf \(v\): First, the budget is more than zero, then \(v\) can be a seed node and increase the amount of \(\text{DoV}_{c}^{\prime}\) by one. Second, if the budget is zero, \(v\) can increment \(\text{DoV}_{c}^{\prime}\) with the probability of becoming active through its parent, i.e., in expected, it will be \(p\cdot\mathds{1}_{\mathbb{T}_{v}}\) where \(p\in F_{v}\) is the probability that \(v\) will be activated through its parent. Note that if the pre-condition does not hold, the leaf cannot make any effect, and in both cases, its effect is equal to zero. Let us say \((i^{\prime},j^{\prime})<(i,j)\) if \(i^{\prime}<j\), or \(j^{\prime}=j\wedge i^{\prime}<i\). As the step of induction, assume that all cells \((i^{\prime},j^{\prime})\) smaller that \((i,j)\) are filled correctly for \(0\leqslant i\leqslant B,0\leqslant j<|V|\). In order to calculate the array \(A^{\prime}\) related to the cell \((i,j)\), for each \(p\in F_{v_{j}}\) we have to calculate the result of the following function. \[\text{DoV}_{c}^{\prime}(v_{j},i,S,p)=max\Big{\{}\\ max_{k=0}^{i}\big{\{}\text{DoV}_{c}^{\prime}(r(v_{j}),k,S,p\cdot b _{v_{j},r(v_{j})})+\text{DoV}_{c}^{\prime}(l(v_{j}),i-k,S,p\cdot b_{v_{j},l(v _{j})})\big{\}}+p\cdot\mathds{1}_{\mathbb{T}_{v}},\\ max_{k=0}^{i-1}\big{\{}\text{DoV}_{c}^{\prime}(r(v_{j}),k,S\cup\{v_{ j}\},b_{v_{j},r(v_{j})})+\text{DoV}_{c}^{\prime}(l(v_{j}),i-k-1,S\cup\{v_{j}\},b_{v_{j},l(v _{j})})\big{\}}+\mathds{1}_{\mathbb{T}_{v}}\Big{\}}.\]  
There is a maximization over two cases. Let us check each case separately. The first case considers all possible cases to split the budget into two parts for its children \(r(v_{j})\) and \(l(v_{j})\) (the first and second terms) when \(v_{j}\) is not selected as a seed node. It finds the split with the maximum outcome using the \(\text{DoV}_{c}^{\prime}\) of its children, which are calculated correctly. In this case, since the node \(v_{j}\) is not a seed node, then the probability that its right (resp. left) child will become active is \(p\cdot b_{v_{j},r(v_{j})}\) (resp. \(p\cdot b_{v_{j},l(v_{j})}\)). The fixed-term is the amount of change that the node \(v_{j}\) can afford to maximize our target party's score. If the pre-condition holds, then with the probability of \(p\) it will increase the score by one, that is \(p\cdot\mathds{1}_{\mathbb{T}_{v}}\). The second maximization investigates the same situation except that it selects \(v_{j}\) as a seed node (if \(i>0\)) and uses the value \(\text{DoV}_{c}^{\prime}\) of its children to find the best split for the \(i-1\) remaining budgets. In this case, the node \(v_{j}\) can increase our party's score by one (if the pre-condition holds) as it is selected as a seed node and will be activated for sure. (To generalize the proof using any non-increasing scoring function \(g(\cdot)\), we should change the updating part of each maximization (the fixed part) as \(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 \(\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))\), respectively.) Note that all corresponding values for the children of \(v_{j}\) are correctly calculated before because the nodes are sorted as BFS reverse order. Finally, it finds the maximum value among the two cases. For the destructive case of the problem, we define pre-condition \(\mathbb{T}_{v}^{\prime}\) as \(\exists c\in C_{1}:\pi_{v}(c)=1\). Then for a node \(v\), if it becomes active and \(\mathbb{T}_{v}^{\prime}\) holds, the node will decrease the party's score by one; otherwise, \(v\) cannot change it. For each sub-tree rooted at \(v\), budget \(k\), and \(p\in F_{v}\), let us define \(\text{DoV}_{d}^{\prime}(v,k,S,p)\) as follows.