# Recommending Links to Control Elections via Social Influence
## 4 Problem Statement  
Consider the scenario in which users of a social network have to vote for elections. In this work, we study the case in which an external manipulator can decide to add new links in the network in order to change the outcome of the elections and make a specific candidate win. We represent the underlying connections between users as a directed graph \(G=(V,E)\). Let \(C=\{c_{1},\ldots,c_{m}\}\) be the set of \(m\) candidates; we refer to our _target candidate_, i.e., the one that we want to make win the elections, as \(c_{*}\). Each voter \(v\in V\) has a list of preferences for the elections represented as a function \(\pi_{v}:C\rightarrow\{1,\ldots,m\}\) that represents the position of a given candidate in the preference list of \(v\), e.g., \(\pi_{v}(c_{i})=3\) for a given candidate \(c_{i}\) means that in the preference list of voter \(v\) such candidate is ranked as third. In this work, we use the model presented by [PERSON] et al. [7]: We use the Independent Cascade Mode as a model for influence diffusion, i.e., each edge \((u,v)\in E\) has an associated probability \(p_{uv}\), that is the probability to influence the neighbor. Then, the process works as follow: Starting from the seed set, when a voter \(v\) is reached by the social influence, i.e., there exists a path from a seed to \(v\), it shifts the ranking of the target candidate by one position up. If \(c_{\star}\) is already in first position, i.e., \(\pi_{v}(c_{\star})=1\), the message has no effect but the node still shares the message with its neighbors. At the end of the process, each voter \(v\in V\) casts a vote for their first ranked candidate, i.e., we consider plurality as voting system. Under _plurality rule_, each voter can only express a single preference among the candidates and that with the _plurality_ of the votes wins, i.e., it is sufficient to have the highest number of votes and there is no need of an absolute majority (\(50\%+1\) of votes). Recall that in the problem of _election control_ we want to maximize the chances of the target candidate to win the elections. To achieve that, we maximize its expected _Margin of Victory_ (MOV) with respect to the most voted opponent, akin to that defined in [7]. Let us first define the set of voters that rank candidate \(c_{i}\) in the \(j\)th position as \(V^{j}_{c_{i}}=\{v\in V:\pi_{v}(j)=c_{i}\}\). Note that initially candidate \(c_{i}\) has \(|V^{1}_{c_{i}}|\) votes. After the ICM process has quiesced, the position of \(c_{\star}\) in the preference list of each influenced node is changed by one position up, except for the voters that already have \(c_{\star}\) in the first position from the beginning. Given the set of seed nodes \(A_{0}\) and the set \(S\) of edges added to \(G\), we define the _score_ of candidate \(c_{i}\) as \(F_{A_{0}}(c_{i},S)\). Initially, i.e., before the process starts, the score of a candidate \(c_{i}\) is equivalent to the number of voters that have \(c_{i}\) in first position, i.e., \(F_{\emptyset}(c_{i},\emptyset)=|V^{1}_{c_{i}}|\). Note that, under this model, we can write the new score of \(c_{\star}\), i.e., the score after the process has quiesced, by the use of live-edge graphs. In fact, the score can be expressed by the number of voters that had \(c_{\star}\) in first position before the process plus the expected number of reachable nodes in live-edge graphs that had \(c_{\star}\) in second position, starting from the seed set \(A_{0}\). Recall that a live-edge graph \(X=(V,E^{\prime})\) is a subset of graph \(G\) where each edge \((u,v)\in E\) is selected to be part of \(E^{\prime}\) independently at random with a probability \(p_{uv}\). Hence, \(X\) has probability to be sampled equal to \(\mathbf{P}(X)=\prod_{c\in E^{\prime}}p_{uv}\prod_{c\in E\setminus E^{\prime} }(1-p_{uv})\). Let us define \(R_{A_{0}}(X,V^{2}_{c_{\star}})\) as the set of reachable nodes in set \(V^{2}_{c_{\star}}\) from the seed set \(A_{0}\) in live-edge graph \(X\) and \(\mathcal{G}(S)\) define the set of all possible live-edge graphs.