# Recommending Links to Control Elections via Social Influence
## 5 Approximation Result  
In this section, we first show that the change in score of the candidate \(c_{\star}\) is a monotone and submodular function. This allows us to give a constant factor approximation using the result given in [24]. The authors proved that, if a solution approximates the change in score of the target candidate within a factor \(\alpha\), then this solution provides a \(\alpha/3\) approximation to the \(\textsc{MoV}\). Let us first denote the change in score of candidate \(c_{\star}\) as  
\[g^{+}_{A_{0}}(c_{\star},S)=F_{A_{0}}(c_{\star},S)-F_{A_{0}}(c_{\star},\mathcal{ O})=\sum_{X\in\mathcal{G}(S)}\mathbf{P}(X)|R_{A_{0}}(X,V^{2}_{c_{i}})|\]  
It directly follows that the function \(g^{+}_{A_{0}}(c_{\star},S)\) is a non-negative linear combination of functions \(R_{A_{0}}(X,V^{2}_{c_{\star}})\). In the next lemma, we show that \(R_{A_{0}}(X,V^{2}_{c_{\star}})\) in live-edge \(X\) is a monotone submodular function of the initial set of nodes \(A_{0}\). This allows us to prove that also \(g^{+}_{A_{0}}(c_{\star},S)\) is monotone and submodular with respect to \(A_{0}\) (Theorem 1). Lemma 1: _Given a set of nodes \(A_{0}\subseteq V\), two live-edge graphs \(X,Y\) s.t. \(E_{X}\subseteq E_{Y}\) and \(E_{Y}\setminus E_{X}\subseteq A_{0}\times V\), and an edge \((u,v)\in(A_{0}\times V)\setminus(E\cup E_{Y})\). Then,_  
\[|R_{A_{0}}(Y^{+},V^{2}_{c_{\star}})\setminus R_{A_{0}}(Y,V^{2}_{c_{\star}})| \leq|R_{A_{0}}(X^{+},V^{2}_{c_{\star}})\setminus R_{A_{0}}(X,V^{2}_{c_{\star} })|,\]  
_where \(X^{+}=X\cup\{(u,v)\}\) and \(Y^{+}=Y\cup\{(u,v)\}\)._  
Proof. : Note that we can decompose \(R_{A_{0}}(X^{+},V^{2}_{c_{\star}})=|R_{A_{0}}(X,V^{2}_{c_{\star}})|+|R_{A_{0}}( \{(u,v)\},V^{2}_{c_{\star}})|-|R_{A_{0}}(X\cap\{(u,v)\},V^{2}_{c_{\star}})|\) and \(R_{A_{0}}(Y^{+},V^{2}_{c_{\star}})=|R_{A_{0}}(Y,V^{2}_{c_{\star}})|+|R_{A_{0}}( \{(u,v)\},V^{2}_{c_{\star}})|-|R_{A_{0}}(Y\cap\{(u,v)\},V^{2}_{c_{\star}})|\). Then, since \(E_{X}\subseteq E_{Y}\) and \(E_{Y}\setminus E_{X}\subseteq A\times V\) we have that \(R_{A_{0}}(X,V^{2}_{c_{\star}})\subseteq R_{A_{0}}(Y,V^{2}_{c_{\star}})\) and \(R_{A_{0}}(X\cap\{(u,v)\},V^{2}_{c_{\star}})\subseteq R_{A_{0}}(Y\cap\{(u,v)\},V^{2}_{c_{\star}})\). Thus,  
\[|R_{A_{0}}(Y^{+},V^{2}_{c_{\star}})|-|R_{A_{0}}(Y,V^{2}_{c_{\star} })|=|R_{A_{0}}(\{(u,v)\},V^{2}_{c_{\star}})|-|R_{A_{0}}(Y\cap\{(u,v)\},V^{2}_{ c_{\star}})|\] \[\leq|R_{A_{0}}(\{(u,v)\},V^{2}_{c_{\star}})|-|R_{A_{0}}(X\cap\{(u, v)\},V^{2}_{c_{\star}})|=|R_{A_{0}}(X^{+},V^{2}_{c_{\star}})|-|R_{A_{0}}(X,V^{2}_{c_{ \star}})|.\qed\]  
We can now prove the following theorem. Theorem 5.1: _Given a graph \(G=(V,E)\), a seed set \(A_{0}\), \(g^{+}_{A_{0}}(c_{\star},S)\) is monotonically increasing submodular function of sets \(S\subseteq(A_{0}\times V)\setminus E\)._  
Proof. : First, we need to prove that \(g^{+}_{A_{0}}(c_{\star},S)\) is a monotonically increasing function, formally \(g^{+}_{A_{0}}(c_{\star},S\cup\{(u,v)\})\geq g^{+}_{A_{0}}(c_{\star},S)\), for each edge \((u,v)\in(A_{0}\times V)\setminus(E\cup S)\). \[ \begin{split}&\mathcal{S}^{+}_{A_{0}}(c_{\star},S\cup\{(u,v)\})- \mathcal{S}^{+}_{A_{0}}(c_{\star},S)=\\ &\sum_{X\in\mathcal{G}(S\cup v)}\mathbf{P}(X)|R_{A_{0}}(X,V^{2}_{ \epsilon_{\star}})|-\sum_{X\in\mathcal{G}(S)}\mathbf{P}(X)|R_{A_{0}}(X,V^{2}_ {\epsilon_{\star}})|=\\ &\sum_{X\in\mathcal{G}(S)}\left(\mathbf{P}(X)p_{uv}|R_{A_{0}}(X^ {+},V^{2}_{\epsilon_{\star}})|+\mathbf{P}(X)(1-p_{uv})|R_{A_{0}}(X,V^{2}_{ \epsilon_{\star}})|-\mathbf{P}(X)|R_{A_{0}}(X,V^{2}_{\epsilon_{\star}})|\right) =\\ &\sum_{X\in\mathcal{G}(S)}\left(\mathbf{P}(X)p_{uv}|R_{A_{0}}(X^ {+},V^{2}_{\epsilon_{\star}})|-\mathbf{P}(X)p_{uv}|R_{A_{0}}(X,V^{2}_{\epsilon _{\star}})|\right)=\\ &\sum_{X\in\mathcal{G}(S)}\mathbf{P}(X)p_{uv}\left(|R_{A_{0}}(X^ {+},V^{2}_{\epsilon_{\star}})|-|R_{A_{0}}(X,V^{2}_{\epsilon_{\star}})|\right) \geq 0.\end{split} \]  
The last equation holds since \(R_{A_{0}}(X,V^{2}_{\epsilon_{\star}})\subseteq R_{A_{0}}(X^{+},V^{2}_{\epsilon _{\star}})\).