Exploiting Social Influence to Control Elections Based on Scoring Rules

1 Introduction

All of us have specific personal opinions on certain topics, such as lifestyle or consumer products. These opinions, normally formed on personal life experience and information, can be conditioned by the interaction with our friends leading to a change in our original opinion on a particular topic if a large part of our friends holds a different opinion. Moreover, opinions can propagate through a social network, generating a diffusion process. This phenomenon of opinion diffusion has been intensely investigated from many different perspectives, from sociology to economics. In recent years, there has been a growing interest on the relationship between social networks and political campaigning. Political campaigns nowadays use online social networks to lead elections in their favor; for example, they can target specific voters with fake news [Allcott and Gentzkow, 2017]. A real-life example of political intervention in this context occurred in the US Congressional elections in 2010, where a set of users were encouraged to vote with a message on Facebook. These messages directly influenced the real-world voting behavior of millions of people [Bond et al., 2012]. Another example is that of French elections in 2017, where automated accounts in Twitter spread a considerable portion of political content trying to influence the outcome [Ferrara, 2017].

∗Contact Author

There exist an extensive literature on manipulating elections without considering the underlying social network structure of the voters, e.g., swap bribery [Elkind et al., 2009], shift bribery [Bredereck et al., 2016]; we point the reader to a recent survey [Faliszewski et al., 2016]. Nevertheless, there are only few studies that exploit opinion diffusion in social networks to change the outcome of elections. The Independent Cascade Model [Kempe et al., 2015] has been considered as diffusion process to guarantee that a target candidate wins/loses [Bartholdi et al., 1992; Hemaspaandra et al., 2007]. The constructive (destructive) election control problem has been introduced in [Wilder and Vorobeychik, 2018a] and consists in changing voters' opinions with the aim of maximizing (minimizing) the margin and probability of victory of a specific target candidate. A variant of the Linear Threshold Model [Kempe et al., 2015] with weights on the vertices has been considered on a graph in which each node is a cluster of voters with a specific list of candidates and there is an edge between two nodes if they differ by the ordering of a single pair of adjacent candidates [Faliszewski et al., 2018]. Moreover, it has been studied how to manipulate the network in order to have control on the majority opinion, e.g., bribing or adding/deleting edges, on a simple Linear Threshold Model where each node holds a binary opinion, each edge has a fixed weight, and all vertices have a threshold fixed to 1/2 [Bredereck and Elkind, 2017]. The study of opinion diffusion modeled as a majority dynamics has attracted much attention in recent literature [Auletta et al., 2015; Brill et al., 2016; Botan et al., 2017]. In these models each agent has an initial preference list and at each time step a subset of agents updates their opinions according to some majority -based rule that depends on their neighbors in the network.

In this work we focus on the election control through social influence problem [Wilder and Vorobeychik, 2018a]: Given a social network of voters, we want to select a subset of voters such that their influence will change the opinion about a target candidate, maximizing its chances to win or lose (we remark that we are in the specific scenario in which only the opinions about a target candidate can be changed). In previous work, the only voting system studied is the plurality rule. Moreover, in the diffusion model considered in the literature, an influenced voter changes the position of the target candidate in its ranking by shifting it up or down by one position, regardless of the amount of influence received [Wilder and Vorobeychik, 2018a]. Here we study the election control problem in any scoring rule voting system and in a different diffusion model, that takes into account the degree of influence that voters exercise on the others and is able to describe the scenario in which a high influence on someone can radically change its opinion.

Original Contribution

• We introduce the Linear Threshold Ranking, a natural and powerful extension of the Linear Threshold Model for the election scenario that takes into account the degree of influence of the voters on each other.
• We show that maximizing the score of a target candidate is monotone and submodular for arbitrary scoring function (including popular voting systems, e.g., plurality rule or borda count), with any number of candidates. This implies that a greedy hill-climbing algorithm achieves a 1-1/e factor approximation for the problem of maximizing the score.
• Exploiting the previous result, we achieve a 13 (1 - 1/e) factor to the problem of maximizing the Margin of Victory of a target candidate in arbitrary scoring rule voting systems with any number of candidates.
• We give a simple reduction that maps destructive control problems to constructive control ones and allows us to achieve a 12 (1-1/e)-approximation.

Due to space constraints, some of the proofs are omitted or only sketched. Full proofs, along with an experimental study, can be found in the full version. 1

2 Background

In this section we present some notions and concepts about voting systems and influence maximization on social networks that will be used in the design and analysis of the algorithm.

Voting Systems

Voting systems are sets of rules that regulate all aspects of elections and that determine their outcome. Herein we consider two single-winner voting systems: (i) Plurality rule: Each voter can only express a single preference among the candidates; the winner is the candidate with the highest number of voter, i.e., the plurality. (ii) Scoring rule: Each voter expresses his preference as a ranking; each candidate is then assigned a score, computed as a function of the positions he was ranked. The former is arguably the simplest voting rule and one of the most commonly used. The latter is a general definition that include several popular election methods by choosing an adequate scoring function: (i) plurality rule: 1 point to the first candidate and 0 to all the others; (ii) tapproval: 1 point to the first t candidates and 0 to the others (each voter approves t candidates); (iii) t-veto or antiplurality: 1 point to the first m- t candidates and 0 to the remaining t, with m the number of candidates; (iv) borda count: m- l points to candidate in position l.

1 https://arxiv.org/abs/1902.07454

Influence Maximization

Influence maximization is the problem of finding the subset of nodes of a graph that maximizes the spread of information. Linear Threshold Model (LTM) is one of the most used models to study influence diffusion in social networks [Kempe et al., 2015]. Given a graph G = (V,E), in LTM each node v ∈ V has a threshold tv ∈ [0, 1] sampled uniformly at random and independently and each edge (u, v) ∈ E has a weight buv ∈ [0, 1] such that, for each v ∈ V , the sum of the weights of the incoming edges is less than or equal to 1, i.e., ∑(u,v)∈E buv ≤ 1. Let At ⊆ V be the set of active nodes at time t, where A0 is the set of nodes that are active at the beginning of the process. In LTM a node v becomes active if the sum of the weights of the edges coming from active nodes is greater than or equal to its threshold tv, i.e., v ∈ At if and only if v ∈ At-1 or ∑u∈At-1:(u,v)∈E buv ≥ tv. The process has quiesced at the first time ˜ t in which the set of active nodes does not change anymore, i.e., time ˜ t is such that A˜ t = A˜ t+1 . We define the eventual set of active nodes as A := A˜ t .

The most central result in LTM is the following [Kempe et al., 2015]: Starting from any set A0, the distribution of A is equivalent to the distribution of reachable nodes in the set of random graphs called live-edge graphs [Kempe et al., 2015]. In live-edge graphs, subgraphs where each node has at most one incoming edge, the problem of selecting the initial set of nodes to maximize the diffusion is monotone and submodular; 2 hence, it can be approximated to a factor of 1 - 1/e using a simple greedy hill-climbing algorithm [Nemhauser et al., 1978]. While it is #P-hard to compute the expected number of active nodes, there exists a simulation-based approach in which the spread of influence can be evaluated by sampling a polynomial number of live-edges [Kempe et al., 2015, Proposition 4.1].

3 Linear Threshold Ranking

We consider the scenario in which a set of candidates are running for the elections and a social network of voters will decide the winner. Some attacker could be interested in changing the outcome of the elections by sending ads and/or (possibly fake) news about a specific candidate to a subset of voters, that could share the news and influence their friends. Is it possible for the attacker to select a subset of voters to control the election, i.e., to change voters' opinions about a target candidate, maximizing his chances to win/lose the elections?

More formally, let G = (V,E) be a directed graph representing the underlying social network. For each node v ∈ V

2 For a set N, a function z : 2N→R is submodular if ∀S, T ⊆N s.t. S ⊆T , ∀e∈N\T holds z(S ∪ {e})-z(S)≥z(T ∪ {e})-z(T ).

we call Nv the set of incoming neighbors of v. Let C = {c1, . . . , cm} be a set of m candidates nominated for the elections; we refer to our target candidate, i.e., the one that we want to make win/lose the elections, as c⋆. Each v ∈ V has a permutation πv of C, i.e., its list of preferences for the elections; we denote the position of candidate ci in the preference list of node v as πv(ci).

Let B ∈ N be the initial budget, i.e., the maximum size of the set of active nodes A0 from which the LTM process starts. After the LTM process has quiesced, the position of c⋆ in the preference list of each node changes according to a function of its incoming active neighbors. The threshold tv of each node v ∈ V models its strength in retaining its original opinion about candidate c⋆: The higher is the threshold the lower is the probability that v is influenced by its neighbors. The weight on an edge buv measures the influence that node u has on node v. Taking into account the role of such parameters, we define the number of positions that c⋆ goes up in πv as

where α : {1, . . . ,m} → [0, 1] is a function that depends on the position of c⋆ in πv and models the rate at which c⋆ shifts up. Note that α can be set arbitrarily to model different scenarios, e.g., shifting up of one position from the bottom of the list could be easier than moving from the second to the first position. Note that π↑ v (c⋆) can be any integer value in {0, . . . , πv(c⋆) - 1}: The floor function guarantees a positive integer value and the minimum between such value and πv(c⋆) - 1 guarantees that the final position of c⋆ is at least 1. We call this process the Linear Threshold Ranking (LTR).

After LTR, the candidates might have a new position in the preference list of each node v ∈ V , that we denote as ˜πv. In particular, the new position of c⋆ will be ˜πv(c⋆) := πv (c⋆) - π↑ v (c⋆); the candidates that are overtaken by c⋆ will shift one position down.

In the problem of election control we want to maximize the chances of the target candidate to win the elections under LTR. To achieve that, we maximize its expected Margin of Victory (MOV) w.r.t. the most voted opponent, akin to that defined in [Wilder and Vorobeychik, 2018a]. 3 Let us consider the general case of the scoring rule, where a non-increasing scoring function f : {1, . . . ,m} → N assigns a score to each position. Let c and ˜ c be the candidates, different from c⋆, with the highest score before and after LTR, respectively. Let

be the margin (i.e., difference in score) between the most voted opponent and c⋆ before and after LTR, respectively. Thus, the election control problem is formalized as that of finding a set of nodes A0 such that

3 We study the change in the margin, and not just the margin, to have well defined approximation ratios when the margin is negative.

namely to find an initial set of seed nodes of at most size B that maximizes the expected MOV, i.e., change in margin. 4

To solve the problem we focus on the score of the target candidate. Let us define

as the total expected score obtained by candidate c⋆ before and after LTR, respectively. In Sections 4 and 5 we prove that the score of the target candidate is a monotone submodular function w.r.t. the initial set of seed nodes A0 in both the plurality and the scoring rule; this allows us to get a (1 - 1/e)-approximation of the maximum score through the use of a greedy algorithm that iteratively selects the node that maximizes the increment in score [Nemhauser et al., 1978]; we denote this algorithm as GREEDY. Note that maximizing the score of the target candidate is a NP-hard problem: Consider the case in which there are only two candidates, α(1) = α(2) = 1, all nodes have c⋆ as second preference, and the scoring function is that of the plurality rule; maximizing the score is equal to maximizing the number of active nodes in LTM because when a node becomes active the target candidate shifts of at least one position up (in this case, in first position); thus the two problems are equivalent. Influence maximization in LTM is NP-hard [Kempe et al., 2015] and maximizing the score in LTR is also NP-hard because it generalizes it. Moreover, in this instance, the maximum value of MOV is equal to twice the maximum score; then maximizing MOV is also NP-hard.

Although maximizing the score is not equivalent to maximizing MOV, in Section 6 we show that we can use GREEDY to obtain a constant factor approximation to MOV. Finally, in Section 7, we consider the problem of destructive control, in which we want the target candidate to lose the elections and prove a constant factor approximation also in this scenario.

4 Maximizing the Score: Plurality Rule

As a warm-up, in this section we focus on the plurality rule. We give an algorithm to select an initial set of seed nodes to maximize the expected number of nodes that will change their opinion and have c⋆ as first preference at the end of LTR.

Let A0 be the initial set of seed nodes and A the set of active nodes at the end of the process. An active node v with πv(c⋆) > 1 will have c⋆ as first preference if π↑ v (c⋆) = πv(c⋆) - 1, that is if and only if α(πv(c⋆)) tv ∑u∈A∩Nv buv ≥ πv(c⋆) - 1 or, equivalently, tv ≤ α(πv(c⋆)) πv(c⋆)-1 ∑u∈A∩Nv buv.

As in influence maximization problems, we define an alternative random process based on live-edge graphs, since in live-edge graph process we don't know the value of tv and we cannot compute which nodes satisfy the above formula.

Definition 1. Live-edge Coin Flip process (LCF):

1. Each node v ∈ V selects at most one of its incoming edges with probability proportional to the weight of that edge, i.e., edge (u, v) is selected with probability buv, and no edge is selected with probability 1- ∑u∈Nv buv.

4 MOV is positive since the scoring function f is nonincreasing.

1. Each node v with πv(c⋆) > 1 that is reachable from A0 in the live-edge graph flips a biased coin and changes its list according to the outcome. In detail, v picks a random real number sv ∈ [0, 1] and sets the position of c⋆ according to sv: If sv ≤ α(πv(c⋆)) πv(c⋆)-1 , node v sets ˜πv(c⋆) = 1 and shifts all the other candidates down by one position; otherwise, v maintains its original ranking.

We show that the two processes are equivalent, i.e., starting from any initial set A0 each node has the same probability to end up with c⋆ in first position in both processes. This allows us to compute the function F(A0), for a given A0, by simply solving a reachability problem in graphs.

We denote by G the set of all possible live-edge graphs sampled from G. For every G′ = (V, E′ ) ∈ G we denote by P(G′ ) the probability that G′ is sampled, namely

We denote by R(A0) the set of nodes reachable from A0 at the end of the LCF process and by RG′ (A0) the set of nodes reachable fromA0 in G′ and by 1(G′ ,v) the indicator function that is 1 if v ∈ RG′ (A0) and 0 otherwise.

Lemma 1. For any seed set A0 and any node v it holds that

Lemma 1 tells us how to compute the probability that a node v is reachable from A0 at the end of the LCF process by using live-edge graphs or by using the probability of the incoming neighbors of v to be reachable from A0. The next theorem shows the equivalence between LTR and LCF .

Theorem 1. Given a set of initially active nodes A0, let A′LTR and A′LCF be the set of nodes such that ˜πv(c⋆) = 1 at the end of LTR and LCF , respectively, both starting from A0. Then, for each v ∈ V , P (v ∈ A′LTR) = P (v ∈ A′LCF ).

Proof. We exclude from the analysis the nodes v with πv(c⋆) = 1 since they keep their original ranking in both models. Let us start by analyzing the LTR process. Let A be the set of nodes activated in LTR from starting from A0. Given a set U of in-neighbors of v, we can write the probability that v ∈ A′LTR given that U are the only active inneighbors of v (i.e. A∩Nv = U) as

The overall probability P(v ∈ A′LTR) is equal to

Let us now analyze the LCF process. To have v ∈ A′LCF we need that v ∈ R(A0) and that the coin toss has a positive outcome. Thus, P(v ∈ A′LCF ) = α(πv(c⋆)) πv(c⋆)-1 P (v ∈ R(A0)) . Finally, by using Lemma 1 and the equivalence between the live-edge process and LTM [Kempe et al., 2015, Proposition 4.1]) the theorem follows.

We now exploit Theorem 1 to show how to compute the value of F(A0). In the case of plurality rule we have that

Thanks to Lemma 1, we can rewrite the above formula as

where, for a graph G′ ∈ G and an integer r ≤ m, we denoted by V r ci the set of nodes that have candidate ci in position r and RG′ (A0, V r c⋆ ) = {v : v ∈ RG′ (A0) ∧ πv(c⋆) = r}.

It follows that the function F(A0) is a non-negative linear combination of functions |RG′ (A0, V r c⋆ )|. In the next lemma, we show that these functions are monotone and submodular w.r.t. A0 and this implies that also F(A0)-F(∅) is monotone and submodular w.r.t. A0. Therefore, we can use GREEDY to find a set A0 such that F(A0)-F(∅) is at least 1-1/e times the optimum [Nemhauser et al., 1978].

Lemma 2. Given a graph G′ ∈ G and a positive integer r ≤ m , the size of RG′ (A0, V r c⋆ ) in G′ is a monotone submodular function of A0.

5 Maximizing the Score: Scoring Rule

In this section we extend the results of Section 4 to the general case of the scoring rule, in which a scoring function f assigns a score to each candidate according to the positions he was ranked in the voters' lists. The overall approach is similar, but more general: We first define an alternative random process, called Live-edge Dice Roll (LDR), and show its equivalence to LTR; then we use LDR to compute F(A0) and show that it is a monotone submodular function of the initial set of active nodes A0. This latter result allows us to compute a set A0 that has an approximation guarantee of 1 - 1/e on the maximization of the score of the target candidate with GREEDY. Process LDR is defined as follows.

Definition 2. Live-edge Dice Roll process (LDR):

1. Each node v ∈ V selects at most one of its incoming edges with probability proportional to the weight of that edge, i.e., edge (u, v) is selected with probability buv, and no edge is selected with probability 1- ∑u∈Nv buv.
2. Each node v with πv(c⋆) > 1 that is reachable from A0 in the live-edge graph rolls a biased πv(c⋆)-sided dice and changes its list according to the outcome. This is

equivalent to picking a random real number sv in [0, 1] and setting the position of c⋆ according to sv as follows:

If ˜πv(c⋆) ̸= πv(c⋆), all candidates between ˜πv(c⋆) and πv(c⋆) - 1 are shifted down by one position.

We show that LTR and LDR have the same distribution.

Theorem 2. Given a set of initially active nodes A0 and a node v ∈ V , let ˜πLTR v (c⋆) and ˜πLDR v (c⋆) be the position of node v at the end of LTR and LDR, respectively, both starting from A0. Then, P ( ˜πLTR v (c⋆) = ℓ) = P ( ˜πLDR v (c⋆) = ℓ), for each ℓ = 1, . . . , πv(c⋆).

Proof. Let A be the set of active nodes at the end of the LTR process that starts from A0. The probability that an active node moves candidate c⋆ from position r to position ℓ is:

for each r, ℓ ∈ {1, . . . ,m}, ℓ ≤ r. In particular, for a node v, the probability that the second step of LDR yields ˜πv(c⋆) = ℓ, for ℓ = 1, . . . , πv(c⋆), is P(πv(c⋆), ℓ).

We have that P ( ˜πLTR v (c⋆) = ℓ) is equal to

If U is the maximal subset of active neighbors of v (i.e., U = A∩Nv), then we can write the probability that ˜πLTR v (c⋆) = ℓ given U as follows:

Therefore, P ( ˜πLTR v (c⋆) = ℓ) is equal to

Recall that, in LDR, P ( ˜πLDR v (c⋆) = ℓ) is equal toP(v ∈ R(A0)) · P(πv(c⋆), ℓ). By Lemma 1, it follows that

and hence P ( ˜πLDR v (c⋆) = ℓ) is equal to

Finally, using [Kempe et al., 2015, Proposition 4.1], we get that P ((R(A0) ∩ Nv) = U) = P ((A ∩ Nv) = U).

With some algebra, and by applying Lemma 1 and Theorem 2, we get the following formulation of F(A0):

Therefore, F(A0) is a non-negative linear combination of the monotone submodular function |RG′(A0, V r c⋆ )| (see Lemma 2), and hence F(A0) - F(∅) is also monotone and submodular. Thus, we can use GREEDY to find a (1 - 1/e)- approximation to the problem of maximizing the score of the target candidate [Nemhauser et al., 1978].

6 Maximizing the Margin of Victory

In previous sections we have shown that the problem of maximizing the score of the target candidate can be approximated within a factor 1-1/e by using GREEDY. In the following we show how to achieve a constant factor approximation to the original problem of maximizing the MOV by only maximizing the score of the target candidate. Given the equivalence of LCF and LDR with LTR, we can formulate our objective function as the average MOVG′ computed on a sampled liveedge graph G′ , namely E[MOV(A0)] = E[MOVG′(A0)], where MOVG′(A0) = µG′(∅) - µG′(A0), and µG′ is the change in margin on a fixed G′ .

We formulate the margin on the live-edge graphs in a way that is akin to that of [Wilder and Vorobeychik, 2018a]: We can exploit such formulation to prove our constant factor approximation with the same proof structure since also in our case the objective function is monotone and submodular (Lemma 2). For the plurality rule we have that

where: the first term is the number of points gained by c⋆ after LTR; the second term (the first inside the minimum) is the number of points of the most voted opponent before LTR; the third one is the total number of points that the most voted opponent after LTR had before the process; the fourth term is the number of points that the most voted opponent after LTR lost because of the shifting of c⋆. Similarly, for the general case of arbitrary scoring rule we have

where the meaning of the terms is similar to above. This latter formulation is just a generalization of the plurality case whenever we choose f such that f(1) = 1 and f(r) = 0, for each r ∈ {2, . . . ,m}. In this way we would have that the gain in score would be just 1 and that α(r) r-1 = P(r, 1).

In the following Theorem we prove that, up to the loss of a constant-factor in the approximation ratio, it suffices to concentrate only on the score of the target candidate c⋆ and not on the margin w.r.t. the most voted opponent.

Theorem 3. GREEDY is a 13 (1 - 1/e)-approximation algorithm for the problem of election control in arbitrary scoring rule voting systems.

Roughly speaking, the factor 1 3 appears because we lower bound three terms in the MOV formulation to reconstruct the optimum in the approximation.

7 Destructive Election Control

In this section we focus on the destructive election control problem. Here we define, for each node v ∈ V , the number of positions of which c⋆ shifts down after LTR process as

The final position of c⋆ in v will be ˜πv(c⋆) := πv(c⋆)+π↓ v (c⋆) and the overall score that c⋆ gets is

The problem can be defined as that of finding an initial set of seed nodes A0 that maximizes the expected MOVD:

Similarly to the constructive case we are able to achieve a constant factor approximation, to do that we provide a reduction from the destructive to the constructive case. Given an instance of destructive control, we build an instance of constructive control in which we simply reverse the rankings of each node and complement the scoring function to its maximum value. Roughly speaking, this reduction maintains invariant the absolute value of the change in margin of the score of any candidate between the two cases. Formally, for each v ∈ V , the new instance has a preference list defined as π′v (c) := m- πv(c) + 1 for each candidate c ∈ C, and, for each position r ∈ {1, . . . ,m}, has a scoring function defined as f ′ (r) := fmax - f(m- r + 1), where fmax := maxr∈{1,...,m} f(r). For each v ∈ V , the ranking of c⋆ in the new instance is π′v (c⋆) := m- πv(c⋆) + 1.

For each solution A0 found in the new instance, i.e., a constructive one, the overall score of c⋆ after the process is F ′ (A0) := E [∑v∈V f ′ (π′v (c⋆) -π′↑ v (c⋆))] .

The reduction allows us to maximize the score of the target candidate in the constructive case and then to map it back to destructive case. Differently from the constructive scenario, we get a factor 12 because we can reconstruct the optimum in the approximation by only lower bounding two terms.

Theorem 4. GREEDY is a 12 (1 - 1/e)-approximation algorithm for the problem of destructive election control in arbitrary scoring rule voting systems.

8 Conclusions and FutureWork

We introduced Linear Threshold Ranking, which describes the change of opinions taking into account the amount of exercised influence. We provided a constant factor approximation algorithm to the problems of constructive and destructive election control in arbitrary scoring rule voting systems. We simulated our model on real-world networks using synthetic election data, i.e., random degrees of influences and random preference lists. We used several combinations of parameters (B, |C|, α, πv) on 4 networks exhibiting heterogeneous topologies. We observed that GREEDY can find a solution that makes the target candidate win the elections between 50% and 88% of the times, depending on the scenario.

Nowadays social media are are significant sources of information for voters and the massive usage of these channels for political campaigning is a turning point. Potential attackers can manipulate the outcome of elections through the spread of targeted ads and/or fake news. Being able to control the information spread can have a great impact, but it is not easy to achieve since traditional media sources are relatively transparent: It is essential to protect the integrity of electoral processes to ensure the proper operation of democratic institutions. Our results indicate that social influence is a salient threat to election integrity: We provide an approximation algorithm to maximize the MOV of a target candidate, that could be used to control election results and is of fundamental importance to protect their fairness.

Compared to the only other work on election control via social influence [Wilder and Vorobeychik, 2018a], we consider general scoring functions and a more realistic model (LTM instead of ICM) that takes into account the amount of influence exercised on voters. We believe that our algorithm could be used in real-life scenarios to predict election results and to understand what degree of control has been exercised. Our results assume the knowledge of information that is not available, but can be estimated. Recent studies analyze the robustness of greedy w.r.t. inaccurate estimations of the degrees of influence. Nevertheless, experiments on greedy algorithm for Influence Maximization show that the worst case hardness theoretical results do not necessarily translate into bad performance on real-world datasets [He and Kempe, 2018].

As future research directions we would like to study our model in a scenarios which are not currently captured, including multi-winner and proportional representation systems. It is also worth to analyze approaches that mix constructive and destructive control. Moreover, we would like to extend our model in order to consider a more uncertain scenario, in which the preferences of voters are not known. Finally, it would be interesting to study how to prevent election control for the integrity of voting processes, e.g., through the placement of monitors in the network [Zhang et al., 2015; Amoruso et al., 2017] or by considering strategic settings [Yin et al., 2018; Wilder and Vorobeychik, 2018b].

Acknowledgments

This work has been partially supported by the Italian MIUR PRIN 2017 Project ALGADIMAR "Algorithms, Games, and Digital Markets".