# 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 formal definition of \(\mathrm{DoV}_{c}(v,k,S,p)\) is as follows:  
\[\mathrm{DoV}_{c}(v,k,S,p)=max\Bigg{\{}\\ max_{k^{\prime}=0}^{k}\Big{\{}\mathrm{DoV}_{c}\left(r(v),k^{\prime},S,p \cdot b_{f(v),v}\right)+\mathrm{DoV}_{c}\left(l(v),k-k^{\prime},S,p\cdot b_{ f(v),v}\right)\Big{\}}+p\cdot b_{f(v),v}\cdot\mathcal{D}_{v},\\ max_{K^{\prime}=0}^{k-1}\Big{\{}\mathrm{DoV}_{c}\left(r(v),k^  
We can calculate and store the values in a two-dimensional array \(A[B+1,|V|]\) where the rows are the budgets (starting from zero to \(B\)), and the columns are the nodes of the tree presented as the BFS reverse order, and each cell \((i,j)\) (\(0\leqslant i\leqslant B,0\leqslant j<|V|\)) of the array refers to another array \(A^{\prime}[|F_{\eta_{j}}|]\). Then in the worst case, since the budget \(B\), and \(|F_{\eta_{j}}|\) (for any \(v_{j}\in V\)) are at most equal to \(|V|\), then we can solve the problem in polynomial time using \(O(|V|^{3})\) memory. Note that we have to fill the matrix \(A\) left-to-right and top-down, while for each cell of it we can fill the corresponding array \(A^{\prime}\) in any order.  
As the base cases, for each leaf \(v\in V\), and \(p\in F_{v}\), if \(k>0\) we set \(\text{DoV}_{c}(v,k,S,p)=\mathcal{D}_{v}\), otherwise, if \(k=0\) we have \(\text{DoV}_{c}(v,k,S,p)=p\cdot b_{f(v),p}\cdot\mathcal{D}_{v}\) which is the difference of the probability to vote for our party after and before diffusion \(S\), made by the node \(v\). In fact, if the budget is greater than zero, the node will become active for sure, and we need to consider the difference of scores, but if the budget is zero we cannot select it as a seed node and the value should be multiplied by the probability that the node will become active, i.e., \(p\cdot b_{f(v),p}\). We also define \(\text{DoV}_{c}(null,k,S,p)=0\), that is, the value of \(\text{DoV}_{c}\) for a null reference is zero. It is useful when a node has just left (resp. right) child, then the value of the function for its right (resp. left) child, regardless of the other parameters, is zero. The pseudo-code of the DP is presented in Algorithm 1, which calculates the maximum \(\text{DoV}_{c}^{\text{SPP}}\); by small changes, it can find the seed nodes too. Note that the final answer will be calculated by \(\text{DoV}_{c}(v_{root},B,\emptyset,0)\) where \(v_{root}\) is the root node of the tree, \(B\) is the budget, \(\emptyset\) represents that we have no seed node so far, and \(0\) means the parent of the root node will be activated with zero probability. The following theorem shows that the DP works well.  
```
ProcedureDoV(Tree \(T=(V,E)\), Budget \(B\)) \(A\leftarrow[B+1,|V|]\)\(\triangleright\) It is a two-dimensional array \(A[0..B,0..|V|-1]\) Name all nodes in \(V\) from \(0\) to \(|V|-1\) in BFS reverse order for\((j\gets 0;j<|V|;j\gets j+1)\)do \(F_{\eta_{j}}\leftarrow\) Set of all possible probabilities that \(f(v_{j})\) may become active for(\(i\gets 0;i<=B;i\gets i+1\))do \(\triangleright\) the variables \(i,j\) are a counter for rows and columns, respectively. \(A[i,j]\leftarrow\text{Array}[|F_{\eta_{j}}|]\)\(\triangleright\) Each cell \((i,j)\) is an array if(\(v_{j}\) is a leaf)then for(\(p\in F_{\eta_{j}}\))do \(A[i,j;p]\leftarrow\sum_{c\in C_{1}}\left(\frac{\pi_{\eta_{j}}(c)+\frac{1}{k!} \cdot p\cdot b_{f(v_{j}),v_{j}}}{1+p\cdot b_{f(v_{j}),v_{j}}}-\pi_{\eta_{j}}(c)\right)\) if(\(i=0\))then \(A[i,j;p]\gets p\cdot b_{f(v_{j}),v_{j}}\cdot A[i,j;p]\)  end if  end for continue for(\(p\in F_{\eta_{j}}\))do \(\triangleright\) If \(r(v_{j})\) or \(l(v_{j})\) does not exist, \(A[\ldots,r(v_{j})\) or \(l(v_{j})]\);...] is zero. \(\mathcal{D}_{v}\leftarrow\sum_{c\in C_{1}}\left(\frac{\pi_{\eta_{j}}(c)+\frac{k!}{k!}\cdot p\cdot b_{f(v_{j}),v_{j}}}{1+p\cdot b_{f(v_{j}),v_{j}}}-\pi_{v_{j}} (c)\right)\) \(max_{j}\leftarrow\max_{k=0}^{j}(A[k,r(v_{j});p\cdot b_{f(v_{j}),v_{j}}]+A[i-k,l(v_{j});p\cdot b_{f(v_{j}),v_{j}}])\) \(max_{j}^{\prime}\leftarrow\max_{k=0}^{j-1}(A[k,r(v_{j});1]+A[i-k-1,l(v_{j});1])\) \(A[i,j;p]\leftarrow\max(max_{j}+p\cdot b_{f(v_{j}),v_{j}}\cdot\mathcal{D}_{v}, max_{j}^{\prime}+\mathcal{D}_{v})\)  end if  end for return\(A[B,|V|-1;0]\)\(\triangleright\) The final result for the root node using all budget end
```  
**Algorithm 1**Calculating maximum \(\text{DoV}_{c}\) for e given tree \(T\) and budget \(B\) when the diffusion model is LTM and voting system is straight-party voting.  
**Theorem 5**.: _Given a tree \(T=(V,E)\) and budget \(B\), the DP Equation (3) finds a set of seed nodes \(S\)\((|S|\leqslant B)\) to maximize \(\text{DoV}_{c}^{spv}\)._  
Proof.: Consider the matrix \(A[B+1,|V|]\) where each cell \(A[k,v]\) point to another array \(A^{\prime}\) where the columns are all possible probabilities that \(f(v)\) will become active. Calculating all possible probabilities for the array \(A^{\prime}\), we have at most \(|F_{v}|\) columns for each node \(v\in V\) and budget \(0\leqslant k\leqslant B\), and for each of them, we need to calculate and store the maximum \(\text{DoV}_{c}\).  
Please note that if \(f(v)\) becomes active, it can activate \(v\) with a probability equal to the weight of the edge between them (\(b_{f(v),v}\)). It holds because each node has just one incoming edge (its parent), and the threshold of the node will be generated uniformly at random. Then the probability that the threshold of the node \(v\) be less than (or equal) to the weight of the incoming edge is \(b_{f(v),v}\).  
Let us show that all values in the arrays will be calculated correctly, by induction. To see that, consider the base cases. For each leaf \(v\in V\), the node cannot activate any other node as it has no outgoing edge. Then, these nodes cannot change the probability distribution of other nodes. In other words, each leaf will change just its own probability distribution. If \(k=0\), it means that we cannot select the node as a seed node, and we need to consider the probability of activating the node, because just activated nodes can update their probability distribution after the diffusion. Then if \(k=0\), we have \(\text{DoV}_{c}(v,k,S,p)=p\cdot b_{f(v),v}\cdot\mathcal{D}_{v}\), where \(\mathcal{D}_{v}\) is the difference of the party's score if the node \(v\) becomes active (defined in Equation (4)), and \(p\cdot b_{f(v),v}\) is the probability that the node will be activated by its parent. On the other hand, if \(k>0\), we can select \(v\) as a seed node, and it will be activated with the probability of one, then we have \(\text{DoV}_{c}(v,k,S,p)=\mathcal{D}_{v}\). Using the updating rule (defined in Section 3.1), and the definition of \(\text{DoV}_{c}^{spv}\) (defined in Equation (1)), the base cases are true.  
Let us define \((i^{\prime},j^{\prime})<(i,j)\) if \(j^{\prime}<j\), or \(j^{\prime}=j\wedge i^{\prime}<i\). We have shown that all arrays \(A^{\prime}\) related to the base cases filled out correctly. Now by induction step, assume all related arrays related to pair \((i^{\prime},j^{\prime})\) smaller than \((i,j)\) are correctly calculated. In order to calculate the \(A^{\prime}\) related to \(A[i,j]\), for each column \(p\in F_{v_{j}}\) we use following formula  
\[\text{DoV}_{c}(v_{j},i,S,p)=max\Bigg{\{}\\ max_{k=0}^{i}\Big{\{}\text{DoV}_{c}\left(r(v_{j}),k,S,p\cdot b_{f(v_{j }),v_{j}}\right)+\text{DoV}_{c}\left(l(v_{j}),i-k,S,p\cdot b_{f(v_{j}),v_{j}} \right)\Big{\}}+p\cdot b_{f(v_{j}),v_{j}}\cdot\mathcal{D}_{v_{j}},\\ max_{k=0}^{i-1}\Big{\{}\text{DoV}_{c}\left(r(v_{j}),k,S\cup\{v_{j} \},1\right)+\text{DoV}_{c}\left(l(v_{j}),i-k-1,S\cup\{v_{j}\},1\right)\Big{\}} +\mathcal{D}_{v_{j}}\Bigg{\}},\]  
in which the first maximization considers the maximum value among all possible cases that we do not select the node \(v_{j}\) as a seed node, and the second one considers the maximum value among all possible cases that we choose \(v_{j}\) as a seed node.