Manipulating an election in social networks through link addition

Abstract

We investigate the effects of the social influence in determining the behavior of agents in a social network in the context of an election. In particular, we concentrate our attention on how the structure of a social network can be manipulated in order to determine the outcome of an election. We consider an election with m candidates and n voters, each one with her own ranking on the candidates. Voters are part of a social network and the information that each voter has about the election is limited to what her friends are voting. We consider an iterative elective process where, at each round, each voter decides her vote strategically, based on what her neighbors voted in the previous round and her ranking. Thus, a voter may decide to vote for a candidate different from her favorite to avoid the election of a candidate she dislikes. Following Sina et al. (Adapting the social network to affect elections. In: Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, pp 705–713, 2015) we investigate how a central organization that knows rankings of all the voters and can manipulate the structure of the social network can determine the outcome of the election by creating new connections among voters. Our main result is an algorithm that, under mild conditions on the social network topology and on the voters’ rankings, is able to compute a limited number of links to be added to the social network in order to make our designed candidate the winner of the election. Our results can be seen as another indication that who controls social media can have a great influence on our lives by strategically determining what information we are exposed to.

1 Introduction

In last years the influence that social media have on our choices and our everyday life is getting more and more relevant (Tambini 2018). For example, it is quite common to choose restaurants, hotels or holiday destinations by looking how other users rate these places on social sites as Yelp, TripAdvisor, or also Facebook. The spirit of these services is that you can take advantage of the experience of the community in taking your decisions. However, our choices will be strictly intertwined not only to what our friends did or thought, but also on which data the social media decided to show or conceal. By carefully selecting the information to present to the agents, an agency controlling the social media can innescate information cascades that can significantly change the decisions of the agents.

In this work we address the problem of the social media manipulability from a social choice theory point of view. We consider a setting where n voters (the members of a social network) have to elect a winner among m candidates. Voters are arranged in a graph, describing the social relationships existing among them. Voters are then involved in an iterative voting session (Meir 2017), in which at each time step they vote for their preferred candidate, depending on what others voted in the previous step. Clearly, at each time step they have the chance to revise their decision and vote for a different candidate, depending on the results of the previous steps.

Specifically, in this work, in order to understand to which extent the social media can influence our choices by deciding which information voters are exposed to, we consider the setting proposed in Sina et al. (2015), in which each voter has her personal ranking on the candidates, and she is exposed to limited information about the election, consisting only of the choices made by her neighbors in the network (and, possibly, a poll). Voters are then assumed to behave strategically, in the sense that at each step they decide their vote in response to what their neighbors voted in the previous step in order to optimize their personal welfare. Thus, a voter may decide to vote for a candidate that is not her favourite, as long as her vote can lead, according to her limited view of the election (restricted to her neighborhood and the poll), to an outcome that she would prefer to the current outcome.

Sina et al. (2015) investigated to what extent a central entity that has global knowledge on the voters’ rankings and the control of the social network (e.g., the social media owner or manager) may influence the outcome of the election process, by manipulating the view of the voters through the addition/deletion of links in the social network. In particular, they focus only on the addition case, since this operation is less invasive and can be realized without arising suspects in the voters. We remark that this scenario is very relevant and realistic, since current technology would already allow the social media managers to implement this kind of manipulation (e.g., Facebook’s friend suggestions).

Unfortunately, the results in Sina et al. (2015) address the issue only partially. Indeed, they design a polynomial time algorithm that, given the social network, the voters’ rankings and a designated candidate w, compute a set of links that a central designer may add to the network in order to have that w will be voted by the majority of voters. This interesting result has the drawback that the number of added links is extremely large and this makes the algorithm infeasible in real settings. However, computing the minimum number of links to add in order to make the desired candidate to win, is a computationally hard problem, even in simpler settings (Bredereck and Elkind 2017).

To address these issues, Sina et al. (2015) proposed an alternative heuristic that works in two phases: first, it influences a subset of voters, by adding links to the social network in order to modify their view so that they “autonomously” decide to vote for our designated winner w, and then, it stabilizes the neighbors of the voters influenced in the previous phase and have them voting for their favorite candidates. Clearly, the heuristics may fail if it does not find enough nodes to influence and stabilize in order to have w the winner of the election.

Sina et al. (2015) proved experimentally that their heuristic adds only a limited number of links. However, it tends to have a quite large failure rate. The main problem is given by the fact that the heuristic does not stabilize neighbors of stabilized nodes: thus, due to the added links, they may become unstable, and this can activate cascading behaviors with severe effects on the outcome of the election (The problem has been acknowledged also in Sina et al. (2015), and a fix is proposed that significantly increases the number of added links).

1.1 Our contributions

In this work we present a novel algorithm to compute the set of links to be added to the social network in order to have the designated candidate w win the election. Our algorithm works under mild conditions on the network structure and on the voters’ rankings. Moreover, it adds a limited number of links (comparable to the heuristics in Sina et al. (2015)).

As the heuristic in Sina et al. (2015), our algorithm works in two phases. In the influence phase we look for a voter u that may be influenced to vote for the designated candidate w, and we add links between u and nodes that are voting for w or for a candidate that u dislikes. These nodes are chosen among the ones that have not been influenced yet. This phase is repeated until w obtains the majority of the votes. Thus, if all the non-influenced voters vote for their favorite candidates (we take care of this hypothesis in the stabilization phase), then w will win the election. Notice that, since we are following the same approach proposed in Sina et al. (2015), in this phase we are adding no more links than their heuristic does.

The stabilization phase aims to guarantee that all the non-influenced nodes continue to vote for their favorite candidates and it is the crux of our algorithm. We partition the nodes to stabilize in three sets: the superseeds, the seeds, and the remaining nodes. Our algorithm adds only 4 links per node to stabilize a superseed node and at most 2 links per node to stabilize all the remaining nodes. We prove that this is the minimum number of links that have to be added to stabilize all these nodes.

Our algorithm works under a set of mild conditions: the main requirement is that there are sufficiently many voters that do not rank w as the worst candidate (since these voters can be never induced to vote for w), and they have a limited neighborhood (otherwise the available links may be not sufficient to change their minds). There are also other technical requirements, but they concern only a limited number of nodes and they can be easily satisfied whenever the number of voters is large enough. We notice that our algorithm’s working conditions are more restrictive than the ones of the algorithm in Sina et al. (2015), but it adds a much smaller number of links.

Finally, in Sect. 5 we present results of extensive experiments that we run to validate our algorithm and compare it to the heuristic presented in Sina et al. (2015). Our experiments show that our algorithm adds a number of links that is slightly greater than their heuristic but it never fails, while the heuristic failed in about the 25% of our simulations.

1.2 Related works

There is a large literature on iterative voting, that allows agents to update several times their vote during the election process (Meir et al. 2010; Lev and Rosenschein 2012; Grandi et al. 2013; Meir et al. 2014). All these works focus on conditions necessary to guarantee that strategic voters converge to an equilibirum in an iterative election process: specifically, they consider the issue under different votes’ aggregation rules, such as Plurality and Borda rules, or by restricting the set of voters’ initial rankings. However, these works do not consider the effect that social influence could have on voters’ actions, i.e., in these works every voter has complete knowledge of votes of every other agents.

In the last years there is an increasing literature focusing on the election manipulation problem, i.e., on how social media can be used as a powerful tool for subverting the result of an election. One of the first works along this research line analyzed the resistance to bribery of a special aggregation rule based on cp-nets (Maran et al. 2013). Moreover, Auletta et al. (2017) showed that in an election setting with only two candidates where voters are influenced by a (weighted) majority of their neighbors, it is always possible for a manipulator to lead a minority (if it is large enough) to become a majority, regardless of the topology of the underlying social relationships. Similarly, in Auletta et al. (2018) it has been proved that in a similar setting, a manipulator can be able to lead a bare majority to consensus. Interestingly, these results cannot be easily extended to more than two candidates (Auletta et al. 2019b). Other forms of manipulation are considered in (Bredereck and Elkind 2017; Ferraioli and Ventre 2017; Grandi and Turrini 2016): in particular, Bredereck and Elkind (2017) considered the case that a manipulator may add edges in the relationship network, just as we do in this paper. Finally, in (Wilder and Vorobeychik 2018), a more complex voting setting is considered, similar to the one considered in this work, with more than two candidates and a plurality aggregation rule. Note however that in all these works players are not strategic and they may change their rankings as effect of their neighbors’ influence; in our work, instead, the rankings cannot change, but the expressed votes may be adapted because of a strategic voting behavior.

More in general, there is an intense research on how to model the effects that social pressure can have on people’s choices: original models derive from sociological and economical studies (Bindel et al. 2015; Alon et al. 2012; Hassanzadeh et al. 2013); on top of these, many other models have been proposed (Bhawalkar et al. 2013; Simon and Apt 2015; Auletta et al. 2016a, 2019a; Bilò et al. 2018; Acar et al. 2017), trying to consider more complex aspects, such as the co-evolution of choices and relationships, the presence of both positive and negative influences, and the evolution of the relationships. Some of these models also inspired the one considered in Sina et al. (2015) and in this work. However, we stress that no of these papers investigate on whether and how social influence can be used in order to manipulate an election.

2 Model and definitions

We consider an election with a set of candidates of size m and a set of voters of size n. Voters lie on nodes of a social network $G=(V, E)$. In this paper we assume that the social network is directed but it can be easily seen that our algorithm works also on undirected networks.

We say that the neighborhood of a node u represents the u’s view of the election. Each voter u has a preference order, or ranking, $\succ _u$ over the candidates such that, for any two candidates $c,c'$, we say that $c \succ _u c'$ if u prefers c to $c'$. Moreover, voter u is said to be a supporter of the candidate c if u prefers c to every other candidate. For every candidate c, we denote by ${\mathsf {Supp}}[c]$ the set of supporters of c. Sometimes we assume that a poll exists, reporting to all the voters the number of supporters for each candidate within a random sample of voters.

The election process. The election process works in rounds. At round 0 each voter announces to all its neighbors the candidate she supports (i.e., the first candidate in her preference list). At round $i \ge 1$ each voter considers the votes announced by her neighbors in round $i-1$ and the poll, strategically chooses the candidate to vote and announce it to all her neighbours. Observe that a voter u can decide to vote for a candidate c different from the candidate that she supports (see below for details about how this choice is done).

The winner of the election at round i is the candidate that received the majority of votes in that round. If multiple candidates received the same number of votes, a tie-breaking rule is adopted. Given two candidates $c, c'$, we say that $c > c'$ if c would win the tie-break against $c'$. The process is repeated until an equilibrium is reached, i.e., a round of the election in which no voter changes the vote that she expressed in the previous round. Note that that this dynamics is known to converge only under opportune conditions (Meir et al. 2017). However, we prove that for all the networks in which our manipulation algorithm returns an outcome, the dynamics above will surely converges to an equilibrium.

We are now ready to describe how the voters choose who vote at each round. We assume that voters are strategic and at each round they declare the vote that best-responds to the votes expressed by their neighbors in the previous round with respect to their ranking. Thus, a voter changes her vote only if, according to her view, her vote is crucial to determine the election of a candidate she likes more of the current winner. The following definition describes formally when a node u has an incentive to change her vote.

Definition 1

A node u is $(c_1, c_2)$-crucial in round i if $c_1$ is the candidate that is voted by the majority of neighbors of u at round $i-1$ (in case of ties, the one that wins the tie-break), and $c_2$ is a candidate with $c_2 \succ _u c_1$, and one of the following two conditions hold: (i) $c_1$ and $c_2$ received the same number of votes among the neighbors of u; (ii) $c_2$ received one vote less than $c_1$ and $c_2 > c_1$ (i.e., $c_2$ wins a tie-break against $c_1$).

Clearly, if node u is $(c_1, c_2)$-crucial in round i, then she will decide to vote for $c_2$ to support an outcome she prefers to the current one. If, instead, u is not crucial, i.e., she cannot influence the outcome of the election in her neighborhood, then she confirms the vote expressed in the previous round.

3 The manipulation algorithm

In this section we present our manipulation algorithm. The algorithm takes in input the social network $G =(V,E)$, the list of candidates M, the preference lists of all the voters $\{\succ _u\}_{u \in V}$, and the designated winner w and returns a set of edges to add to the social network in order to guarantee that w will be the winner of the election. Following the approach presented in Sina et al. (2015), our algorithm works in two phases.

Influence phase. We start by running the first two rounds (rounds 0 and 1) of the election on the graph G. Let ${\mathsf {Aff}}$ be the set of nodes that voted for w in the round 1, but they are not supporters of w. Observe that these nodes voted for w since this was the best response to what their neighbors announced in round 0. That is, they were (c, w)-crucial in round 1, where c is a candidate that they like less than w.

Even if we assume that all supporters of w will always vote for this candidate, and that voters in ${\mathsf {Aff}}$ never change their minds after round 1, there may still be insufficient votes to guarantee that w will win the election. If this is the case, then we have to induce other nodes to vote for w. To this aim we follow the same approach as in Sina et al. (2015), and we implement the following algorithm.¹

An affectable node as searched by the above algorithm consists of a node $u\notin {\mathsf {Aff}}$ such that:

• u does not support w;

• there is a candidate c such that $w \succ _u c$;

• there is a set $M_w$ of w’s supporters and a set $M_c$ of unaffected c’s supporters that are not adjacent to u and such that if we add links from u to all the nodes in $M_w \cup M_c$ then u in round 1 will be (c, w)-crucial, but not $(c, c')$-crucial for every $c' \succ _u w$.

If such a node is found, we add new links to the social network between u and the nodes in $M_w \cup M_c$. Let $G'$ be the resulting graph. By running again the first two rounds of the election on graph $G'$, we have that, by hypothesis, node u will vote for w. We then add u to ${\mathsf {Aff}}$ and iterate the procedure until we added sufficiently many nodes to ${\mathsf {Aff}}$ so that w would be the winner of the election with the votes by her supporters and by voters in ${\mathsf {Aff}}$.

Let A be the set of links added by Algorithm 1 and let $G'=(V, E\cup A)$ be the resulting graph. We will next formally prove that, when running the election process on $G'$, every node $u \in {\mathsf {Aff}}$ will vote for w at round 1 and it will confirm her vote in all the successive rounds, as long as all the non-affected notes vote for the candidates they support. Then the following lemma holds.

Lemma 1

Assume we run the election process on the social network $G' =(V, E \cup A)$ returned by the Influence Phase. If we suppose that at each round of the election all the nodes $v \in V {\setminus } {\mathsf {Aff}}$ vote for their favorite candidates, then every node $u \in {\mathsf {Aff}}$ votes for w at every round of the election.

Proof

It is easy to see that, by construction of $G'$, each node $u\in {\mathsf {Aff}}$ votes for w at round 1 of the election.

Thus, we have only to prove that they will confirm this vote in all the following rounds.

Observe that, by hypothesis, every non-affected node $v \in V {\setminus } {\mathsf {Aff}}$ votes for her own favorite candidate (i.e., the same candidate she announced in the preliminary phase) in all the rounds of the election and w is the unique candidate that can increase the votes received by the neighbors of u in round $i \ge 1$. Hence, either u is still (c, w)-crucial, or w is the current winner and u’s vote cannot change the outcome of the election. In the first case, we have that u will vote for w at round $i+1$. In the second case, since u cannot influence the result of the election, she will confirm her vote for w at round $i+1$. $\square$

This lemma assumes that non-affected nodes permanently vote for the candidates they support. However, these nodes could decide to change their votes to react to changes in their own view, and this could have destructive cascading effects with respect to our manipulation aim. Consider for example the network in Fig. 1, and assume that node p, q, r, s have preference $d \succ _p w \succ _p d$, $w \succ _q d \succ _q d$, $c \succ _r w \succ _r d$ and $d \succ _s c \succ _s w$, respectively, whereas nodes $x_i$ and $z_i$ support candidate d and w, respectively. Moreover, assume that the tie-breaking rule is $c> d > w$.

Fig. 1

An instance on which manipulation fails without the stabilization phase

It is then immediate to see that votes by q, r, s oscillate at each round by passing from, respectively, w, c, d to, respectively, d, w, c.

Thus, we have to run a Stabilization Phase in which we add other links to the social network to stabilize non-affected nodes and have them voting for the candidates they support.

In the rest of the paper we assume that a non-affected node is stable in round i if she votes for her favorite candidate in this round and she is unstable otherwise.

Stabilization phase. We partition the set of non-affected nodes in three sets, $B$, ${\mathsf {Seed}}$ and ${\mathsf {SSeed}}$, defined as follows. ${\mathsf {Seed}}$ is a set of 3m non-affected nodes such that, for each candidate c, there are three nodes in ${\mathsf {Seed}}$ supporting c satisfying the following property: if u and v are supporters of the same candidate c in ${\mathsf {Seed}}$, and w is a neighbor of both u and v, then $w \in {\mathsf {Aff}}\cup {\mathsf {Seed}}$, i.e., either w is a node that has been affected in the influence phase, or it is one of the 3m nodes selected as seeds.

${\mathsf {SSeed}}$, instead, is a set of 2m non-affected nodes that is disjoint from ${\mathsf {Seed}}$ and such that for each candidate c there are two nodes in ${\mathsf {SSeed}}$ supporting c and they are not adjacent to nodes in ${\mathsf {Seed}}\cup {\mathsf {Aff}}$.

$B$ is the set of all remaining non-affected nodes.

The Stabilization Phase works in three rounds: we first stabilize the nodes in ${\mathsf {SSeed}}$, then we stabilize the nodes in $B$, and in the last round we stabilize the nodes in ${\mathsf {Seed}}$.

To stabilize a node $u \in {\mathsf {SSeed}}$ we connect this node to four supporters of the candidate c that is supported by the majority of the neighbors of u (in case of tie, we consider the one that wins the tie-break). These four supporters must be chosen among the nodes in $B$. To stabilize a node $u \in B$ we connect this node to at most two seeds. The selection of these seeds will be done through the Node Stabilization procedure that will be described in the next section. To stabilize a node $u \in {\mathsf {Seed}}$ we connect this node to at most two nodes in ${\mathsf {SSeed}}$, selected through the Node Stabilization procedure.

Let $\Sigma$ be the set of links added in the Stabilization phase and let $G''=(V, E\cup A \cup \Sigma )$ be the graph obtained after both Influence and Stabilization Phase have been correctly executed. Then we have the following lemma.

Lemma 2

If we run en election on the social network $G'' =(V, E \cup A \cup \Sigma )$, at each round every node $u \notin {\mathsf {Aff}}$ is stable.

We defer the proof of this lemma to the next section, after we described the node Stabilization procedure.

Observe that Lemmas 1 and 2 prove that whenever our manipulation algorithm is correctly executed, then it returns a set of links to add to the social network that guarantee that the designated candidate will win the election. However, it may be the case that either in the influence phase or in the stabilization phase, we are unable to choose vertices with the desired properties. The following theorem describes the conditions under which this would not happen.

Theorem 1

Our manipulation algorithm returns a network $G''$ such that the designated candidate w is the winner of the election in $G''$ and the process stops in 2 rounds, as long as we can partition the nodes in G in two sets (L, R) such that:

• L contains $\min \left\{ \max _c\{{\mathsf {Supp}}[c]\}, \frac{n}{2}\right\} + 1 - {\mathsf {Supp}}[w]$ nodes that do not support w;

• for every $u \in L$, there are $\max _c \mathtt {Vote}_0[c]-\mathtt {Vote}_0[w]+2 \le d_u +2$ supporters of w that are not in L and not in the neighborhood of u, and $\max _c \mathtt {Vote}_0[c]-\mathtt {Vote}_0[{\hat{c}}]+2 \le d_u +2$ supporters of ${\hat{c}}$ that are not in the neighborhood of u, for some ${\hat{c}}$ such that $w \succ _u {\hat{c}}$, where, for every c, $\mathtt {Vote}_i[c]$ is the number of neighbors of u that voted for c at round i;

• for every candidate c there are in R three distinct subsets $S_c, T_c, U_c$ such that: (i) $S_c$ contains 3 supporters of c with disjoint neighborhood; (ii) $T_c$ contains 2 supporters of c with no neighbors in $S \cup L$; (iii) $U_c$ contains 4 supporters of c with no neighbors in T; where $S = \bigcup _c S_c$ and $T = \bigcup _c T_c$.

We notice that the number of links added by our manipulation algorithm cannot be larger than the one used by the heuristic proposed in Sina et al. (2015). Indeed, the two influence phases are equivalent (in particular, we can adopt in our algorithm the optimizations introduced in Sina et al. (2015)), but our stabilization procedure, as we will prove in Lemma 9, uses the minimum possible number of links.

4 Node stabilization

The Node stabilization procedure is the core of our stabilization process. It takes in input a node $u \notin {\mathsf {Aff}}$ and a subset of nodes S containing supporters of all the candidates, and returns at most two nodes in S such that if u is connected to these nodes then u will be stable in each round of the election.

Let us briefly describe the idea behind our approach. Let t be the candidate that u supports and let $c_i^*$ be the candidate that is voted by the majority of neighbors of u in round i (in case of ties, $c_i^*$ is the one that wins the tie-break). As an example, consider how we can have u to vote for t in round 1. This clearly occurs when u, according to her view, cannot influence the outcome of the election or when u is crucial to make t the winner. Suppose, instead, that there is a candidate $c \ne c^*_0, t$ such that u is $(c_0^*, c)$-crucial. In this case, u would vote for c instead of t. To avoid this situation, it is sufficient to add a link between u and a supporter of $c_0^*$ in S. Actually, as we will show later, there could be several candidates c, distinct from $c_i^*$, such that the addition of a link between u and a supporter of c causes u to vote for her favorite candidate at round i. We will call these candidates stabilizers for u in round i and we will denote by ${\mathsf {St}}_i$ the set of these stabilizers.

Thus, by adding a link between u and a node in S that is a supporter of a stabilizer in ${\mathsf {St}}_0$ we have stabilized u for round 1. However, since in round 1 the affected nodes changed their vote to w, it may be the case that u, if adjacent to some affected nodes, becomes $(c_1^*,c)$-crucial in round 2, for some $c \ne t$. In this case, u would change her vote in round 2 and vote for c. Thus, we have to stabilize also nodes that could change their votes in round 2. We could use the same approach as above, i.e., to add a link between u and a supporter of $c_1^*$ in S. However, this approach may not work since this new link can make u again unstable in round 1. Indeed, suppose that u is $(c_0^*, c)$-crucial in round 1 and $(c_1^*, c')$-crucial in round 2. If $c^*_1 = c$ and we add a link between u and supporters of both $c^*_0$ and $c^*_1$, then u is still $(c^*_0, c)$-crucial in round 1 and she will remain unstable in this round. However, it is easy to see that we could stabilize u both in round 1 and 2 by simply adding links between u and two supporters of $c_1^*$.

In general, we call blocker for u a candidate whose supporters cannot be used to stabilize u in round 2 because they would make the node unstable in round 1. We distinguish two cases: if u is not stable at round 1, then we will denote her set of blockers as ${\mathsf {Bl}}_0$; otherwise we will denote it as ${\mathsf {Bl}}_1$. A formal definition of blockers is given later. We also prove that, whereas the addition of a single link between u and a supporter of a candidate $c \in {\mathsf {Bl}}_i$ is harmful, it is possible to stabilize u both at round 1 and 2 by simply adding links between u and two supporters of a candidate $c \in {\mathsf {Bl}}_i$.

Thus, our Node Stabilization procedure works as described by Algorithm 2.

Roughly speaking, it first considers that u is not stable in round 1 (i.e., she does not vote for her favorite candidate t). In this case, if there is a candidate $c \in {\mathsf {St}}_0$ such that the addition of a link between u and a supporter of c does not make u unstable in round 2, then we add this link. If such a candidate does not exist consider the candidate $c^*_1$ that would win the round 2 of the election in the u’s view: if $c_1^* \notin {\mathsf {Bl}}_0$ we add links between u and both a supporter of $c^*_0$ and a supporter of $c^*_1$; if $c_1^* \in {\mathsf {Bl}}_0$ we add links between u and two supporters of $c_1^*$.

Next, Algorithm 2 considers that u is stable in round 1 (i.e., she votes for her favorite candidate t). In this case, if there is $c \in {\mathsf {St}}_1 {\setminus } {\mathsf {Bl}}_1$, then we add a link between u and a supporter of c; otherwise we add links between u and two supporters of $c^*_1$.

In the rest of this section we give formal definitions of stabilizer and blocker sets, and we prove that the Node Stabilization procedure correctly stabilizes node u adding the minimum number of links.

The set ${\mathsf {St}}_i$of stabilizers for u in round i. Let us recall that, given a node u, we denote as $c^*_i$ the candidate that is voted by the majority of the neighbors of u at round i (in case of ties, $c_i^*$ is the one that wins the tie-break). For every candidate c, let $\mathtt {Vote}_i[c]$ be the number of neighbors of u that voted for c at round i. The set ${\mathsf {St}}_i$ of stabilizers for u in round i is defined as follows:

Definition 2

The set ${\mathsf {St}}_i$, for $i \in \{0,1\}$, contains all candidates c satisfying at least one of the following properties:

• $c=c^*_i$;

• $\mathtt {Vote}_i[c] = \mathtt {Vote}_i[c^*_i]$ and for each $c'$ with $\mathtt {Vote}_i[c'] = \mathtt {Vote}_i[c^*_i]$ it occurs that either $c > c'$ or $c \succ _u c'$;

• $\mathtt {Vote}_i[c] = \mathtt {Vote}_i[c^*_i]-1$ and for each $c'$ with $\mathtt {Vote}_i[c'] = \mathtt {Vote}_i[c^*_i]$ it occurs that $c > c'$ and $c \succ _u c'$, whereas for each $c'$ with $\mathtt {Vote}_i[c'] = \mathtt {Vote}_i[c^*_i]-1$ it occurs that either $c > c'$ or $c \succ _u c'$.

We now prove that if u is unstable in round $i+1$ and there exists a candidate $c \in {\mathsf {St}}_i$ we can stabilize u for this round by simply adding a link between u and a supporter of c.

Let us first make the following observation.

Observation 1

If ${\mathsf {St}}_i = \{c^*_i\}$ or $t \in {\mathsf {St}}_i$, and u is stable at round i, then u is stable in round $i+1$.

Lemma 3

For $i \in \{0,1\}$, let $u \notin {\mathsf {Aff}}$ be stable in round i. If we add a link between u and at least one supporter of a candidate $c \in {\mathsf {St}}_i$, then u will be stable also in round $i+1$.

The claim holds even if a link between u and a supporter of a candidate $d \ne c$ is removed.

Proof

By Observation 1, the Lemma holds if $t \in {\mathsf {St}}_i$ or ${\mathsf {St}}_i = \{c^*_i\}$. Suppose, instead, that there is $c \in {\mathsf {St}}_i$ distinct from $c^*_i$ and $t \notin {\mathsf {St}}_i$. Let $v = \mathtt {Vote}_i[c_i^*]$. Since $c^*_i$ is the winner of the election at round i, other candidates received no more than v votes. Let ${\hat{G}}$ be the graph before the link addition, and let ${\tilde{G}}$ be the graph obtained from ${\hat{G}}$ by adding the links between u and the selected stabilizers. We distinguish three cases, depending on the type of stabilizer we use.

Consider first the case in which we add links between u and at least one supporter of $c^*_i$. If we run the election on ${\tilde{G}}$ the number of votes received by $c^*_i$ in the neighborhood of u will be at least $v+1$, while all the other candidates do not increase their votes. Thus, $c^*_i$ is still the winner of the election according to u’s view and there is no tie with other candidates. On the other hand, if there exists a candidate c with v votes, then it would be $c^*_i > c$, otherwise c would have won the election in ${\hat{G}}$. Hence, u cannot be crucial for the victory of any candidate $c \ne c^*_i$, and thus she will confirm the vote expressed in the previous round. Since, by hypothesis u was stable in round i, she is stable even in round $i+1$.

Consider now the case in which we add links between u and at least one supporter of a candidate $c \in {\mathsf {St}}_i$ with $\mathtt {Vote}_i[c] = \mathtt {Vote}_i[c^*_i]$. In this case the number of votes received by c in the neighborhood of u in ${\tilde{G}}$ will be at least $v+1$. Since no other candidate increases her votes, c will get the majority of the votes in the neighborhood of v with no ties. Clearly, u is not crucial for all the candidates that received at most $v-1$ votes. Moreover, if there is a candidate $c'$ with $\mathtt {Vote}_i[c'] = v$, then, according to Definition 2, either $c > c'$ or $c \succ _u c'$. Hence, u is not $(c, c')$-crucial. Since u cannot influence the outcome of the election, she will confirm the vote for t and thus she will be stable in round i.

Finally, consider the case in which we add links between u and at least one supporter of a candidate $c \in {\mathsf {St}}_i$ with $\mathtt {Vote}_i[c] = \mathtt {Vote}_i[c^*_i]-1$. In this case the number of votes received by c in the neighborhood of u in ${\tilde{G}}$ will be at least v. Notice that all other candidates received at most v votes and, by Definition 2, for any candidate $c'$ with $\mathtt {Vote}_i[c'] = v$ it holds that $c > c'$. Thus, c will be the winner of the election in u’s view. Consider now a candidate $c' \ne c$. If $\mathtt {Vote}_i[c'] = v$ in ${\hat{G}}$, then this candidate still has v votes in ${\tilde{G}}$ and, by Definition 2, $c \succ _u c'$. If $\mathtt {Vote}_i[c'] = v-1$ in ${\hat{G}}$, instead, then this candidate still has $v-1$ votes in ${\tilde{G}}$ and, by Definition 2, either $c > c'$ or $c \succ c'$. Finally, if $\mathtt {Vote}_i[c'] < v-1$ then $c'$ has no possibility to win the election. Hence, u has no incentive in voting for $c'$ and thus she will confirm the vote for t.

The second part of the claim holds since in all the previous cases c would be the winner of the election even if a link between u and a candidate $d \ne c$ is removed. $\square$

Next lemma proves that candidates in ${\mathsf {St}}_i$ are the only nodes whose supporters can “stabilize” u with a single link. This will be a fundamental insight to prove that our approach to node stabilization is optimal.

Lemma 4

For $i \in \{0,1\}$, let $u \notin {\mathsf {Aff}}$ be unstable in round $i+1$. If we add a link between u and a supporter of a candidate $c \notin {\mathsf {St}}_i$, then u will be still unstable in round $i+1$.

Proof

Let $v = \mathtt {Vote}_i[c_0^*]$, i.e., the number of votes that $c^*$ takes at round i in the neighborhood of u in the original graph G.

Let us consider first the graph $G'$ achieved from G by adding a link between u and at a supporter of $c \notin {\mathsf {St}}_i$ such that $\mathtt {Vote}_i[c]=\mathtt {Vote}_i[c^*_i]$. The number of votes of c in the neighborhood of u in $G'$ becomes $v+1$. Since every other candidate does not increase her votes, c is the winner according to u. However, according to Definition 2, there is $c'$ such that $\mathtt {Vote}_i[c']=\mathtt {Vote}_i[c^*_i]$ and both $c' > c$ and $c' \succ _u c$. Hence, if u votes for $c'$, then $c'$ will have the same number of votes as c and will beat c at the tie-break, resulting in this way a winner that u prefers with respect to the actual winner c. That is, u has an incentive for voting $c'$ in place of the candidate voted at round i. The claim then follows since $c' \ne t$. Indeed, since ${\mathsf {St}}_i$ is not empty, then $t \ne c^*_i$. Moreover, since $t \notin {\mathsf {St}}_i$ and, by definition, $t \succ _u c^*_i$, then it must be the case that $\mathtt {Vote}_i[t]<\mathtt {Vote}_i[c^*_i]$.

Let us now consider the graph $G'$ achieved from G by adding a link between u and at a supporter of $c \notin {\mathsf {St}}_i$ such that $\mathtt {Vote}_i[c]=\mathtt {Vote}_i[c^*_i]-1$. The number of votes of c in the neighborhood of u in $G'$ becomes v. According to Definition 2, either there is $c'$ such that $\mathtt {Vote}_i[c']=\mathtt {Vote}_i[c^*_i]$ and $c' > c$, or there is $c'$ such that $\mathtt {Vote}_i[c']=\mathtt {Vote}_i[c^*_i]$ and $c' \succ _u c$, or there is $c'$ such that $\mathtt {Vote}_i[c']=\mathtt {Vote}_i[c^*_i]-1$ and $c' > c$ and $c' \succ _u c$. In the first case, we have that $c^*_i$ wins the election even in $G'$. Moreover, since ${\mathsf {St}}_i$ is not empty, then, according Observation 1 there is a candidate $d\ne t$ such that u has an incentive to vote for d in G, in order to make d the winner of the election in place of $c^*_i$. However, since the number of votes of d and of $c^*_i$ does not change in $G'$, then this should be true even in this new graph.

Suppose instead that c wins the tie-break against every candidate with exactly $\mathtt {Vote}_i[c^*_i]$ votes. Then c is the winner according to u. If there is $c'$ such that $\mathtt {Vote}_i[c']=\mathtt {Vote}_i[c^*_i]$ and $c' \succ _u c$, then, by voting for $c'$, u makes $c'$ as the only candidate to have $v+1$ votes, that is, a winner that u prefers with respect to the actual winner c. That is, u has an incentive for voting $c'$ in place of the candidate voted at round i. Moreover, as above, we have that $c' \ne t$.

Suppose instead that $c'$ is favorite by u with respect to every candidate that take exactly v votes. Then it follows that there is $c'$ such that $\mathtt {Vote}_i[c']=\mathtt {Vote}_i[c^*_i]-1$ and $c' > c$ and $c' \succ _u c$. By voting for $c'$, u makes $c'$ to have the same votes as c but to beat c (and thus everybody else) at the tie-break. Thus, u can make $c'$ a winner that she prefers with respect to the actual winner c. That is, u has an incentive for voting $c'$ in place of the candidate voted at round i. It is only left to prove that $c' \ne t$. Indeed, if $\mathtt {Vote}_i[t] = v-1$, then, since t is favorite over every other candidate and $t \notin {\mathsf {St}}_i$, it must be the case that $t< c^* < c$, where the last inequality follows from our hypothesis.

Finally, we consider the case that $G'$ achieved from G by adding a link between u and at a supporter of $c \notin {\mathsf {St}}_i$ such that $\mathtt {Vote}_i[c]<\mathtt {Vote}_i[c^*_i]-1$. Hence, the number of votes that c takes in the neighborhood of u at most $v-1$. Since the other candidates take exactly the same votes as in G, then $c^*_i$ wins the election even in $G'$. Moreover, since ${\mathsf {St}}_i$ is not empty, according Observation 1 there is a candidate $d\ne t$ such that u has an incentive to vote for d in G, in order to make d the winner of the election in place of $c^*_i$. However, since the number of votes of d and of $c^*_i$ does not change in $G'$, then this should be true even in this new graph. $\square$

The set ${\mathsf {Bl}}_0$ of blockers for a node u unstable in round 1.

Definition 3

Let u be a node unstable in round 1. Candidate c belongs to ${\mathsf {Bl}}_0$ iff $c \ne c^*_0$ and one of the following properties holds:

• $\mathtt {Vote}_0[c] = \mathtt {Vote}_0[c^*_0]$ and $c \succ _u c^*_0$;

• $\mathtt {Vote}_0[c] = \mathtt {Vote}_0[c^*_0]-1$ and both $c > c^*_0$ and $c \succ _u c^*_0$.

It immediately follows from the definition above that the addition of links between u and a supporter of $c^*_0$ and a supporter of $c \in {\mathsf {Bl}}_0$, makes u $(c^*_0,c)$-crucial in round 0, and consequently u will vote for c in round 1, and not for the candidate that she supports. However, the addition of a link between u and a supporter of both $c^*_0$ and $c \notin {\mathsf {Bl}}_0$ guarantees, by definition of blockers, that u is stable in round 1. That is we have the following lemma.

Lemma 5

Let $|{\mathsf {St}}_0| > 1$ and $t \notin {\mathsf {St}}_0$. If two links are added between u and supporters of $c^*_0$ and c, respectively, then u will be stable in round 1 if and only if $c \notin {\mathsf {Bl}}_0$.

Interestingly, to stabilize node u in round 1 we can also add links between u and two supporters of the same candidate $c \in {\mathsf {Bl}}_0$.

Lemma 6

If links are added between u and two supporters of $c \in {\mathsf {Bl}}_0$, then u is stable in round 1.

Proof

Let $\mathtt {Vote}_0[c^*_0] = v$, let ${\hat{G}}$ be the graph before the link addition, and let ${\tilde{G}}$ be the graph obtained from ${\hat{G}}$ by adding links between u and two supporters of c. Since $c \in {\mathsf {Bl}}_0$, c received in ${\hat{G}}$ either v or $v-1$ votes among the neighbors of u.

Consider first the case in which $\mathtt {Vote}_0[c] = v$. The number of votes received by c in the neighborhood of u in ${\tilde{G}}$ becomes $v+2$, while all the other candidates receive the same votes as in ${\hat{G}}$. Thus, c will be the winner in ${\tilde{G}}$ and she receives at least two votes more than any other candidate. Since her victory is indisputable, then u will vote for her favorite candidate.

Consider now the case in which $\mathtt {Vote}_0[c] = v - 1$. Since $c \in {\mathsf {Bl}}_0$, it must be that $c > c^*_0$. The number of votes received by c in the neighborhood of u in ${\tilde{G}}$ becomes $v+1$, while all the other candidates receive the same votes as in ${\hat{G}}$. Hence, c is the winner of round 1 in ${\tilde{G}}$. Moreover, the outcome of the election cannot change regardless of the candidate $c'$ voted by u, since either $\mathtt {Vote}_0[c'] < v+1$ or $\mathtt {Vote}_0[c'] = v+1$ and $c > c^*_0 \ge c'$. Hence, u will vote for her favorite candidate. $\square$

The set ${\mathsf {Bl}}_1$ of blockers for a node u stable in round 1.

Definition 4

Let u be stable in round 1. Candidate c belongs to ${\mathsf {Bl}}_1$ iff $c \ne c^*_0$ and one of the following properties holds:

• $\mathtt {Vote}_0[c] = \mathtt {Vote}_0[t] = \mathtt {Vote}_0[c^*_0]$, with $c^*_0 \ne t$ and $c > t$, and there is a candidate $c'$ with $\mathtt {Vote}_0[c'] = \mathtt {Vote}_0[c^*_0]$, $c' > c$, and $c' \succ _u c$;

• $\mathtt {Vote}_0[t] = \mathtt {Vote}_0[c^*_0]-1$, with $t > c^*_0$ and c satisfies one of the following conditions:

  • $\mathtt {Vote}_0[c] = \mathtt {Vote}_0[c_0^*]$, and there exists $c'$ s.t. $\mathtt {Vote}_0[c'] = \mathtt {Vote}_0[c_0^*]$, $c' > c$, and $c' \succ _u c$;

  • $\mathtt {Vote}_0[c] = \mathtt {Vote}_0[c_0^*]-1$, $c > t$, and there is $c'$ s.t. $\mathtt {Vote}_0[c'] = \mathtt {Vote}_0[c_0^*]$ and $c' \succ _u c$;

  • $\mathtt {Vote}_0[c] = \mathtt {Vote}_0[c_0^*]-1$, $c > t$, and there is $c'$ s.t. $\mathtt {Vote}_0[c'] = \mathtt {Vote}_0[c_0^*]-1$, $c' > c$ and $c' \succ _u c$;

• ${\mathsf {St}}_0$ contains only $c^*_0$ and c satisfies one of the following conditions:

  • $c \ne c^*$ and $\mathtt {Vote}_0[c]=\mathtt {Vote}_0[c_0^*]$;

  • $\mathtt {Vote}_0[c]=\mathtt {Vote}_0[c_0^*]-1$, $c > c^*_0$ and $c^*_0 \succ _u c$;

  • $c\ne t$, $\mathtt {Vote}_0[c]=\mathtt {Vote}_0[c_0^*]-1$, $c^*_0 > c$ and $c \succ _u c^*_0$;

  • $c\ne t$, $\mathtt {Vote}_0[c]=\mathtt {Vote}_0[c_0^*]-2$, $c > c^*_0$ and $c \succ _u c^*_0$.

Next lemma proves that the addition of a link between u and a supporter of $c \in {\mathsf {Bl}}_1$ can be harmful, whereas the addition of a link with a supporter of $c \notin {\mathsf {Bl}}_1$ is not.

Lemma 7

Assume that ${\mathsf {St}}_0 = \{c^*_0\}$ or $t \in {\mathsf {St}}_0$. If a link is added between u and a supporter of a candidate c. Then u will be stable in round 1 if and only if $c\notin {\mathsf {Bl}}_1$.

Proof

Let us start with the “only if” direction. That is, assume that a link is added between u and a supporter of a candidate $c \in {\mathsf {Bl}}_1$. Let $\mathtt {Vote}_0[c^*_0] = v$. First note that, since ${\mathsf {Bl}}_1$ is not empty, then it must be the case that $c^*_0 \ne t$. We distinguish two cases baded on ${\mathsf {St}}_0$ being empty or not.

If ${\mathsf {St}}_0$ is not empty, then it must be the case that $t \in {\mathsf {St}}_0$, and thus either $\mathtt {Vote}_0[t] = v$ or $\mathtt {Vote}_0[t] = v-1$ and $t > c^*_0$. Let us consider these cases separately.

If $\mathtt {Vote}_0[t] = v$, then, by definition of ${\mathsf {Bl}}_1$, $\mathtt {Vote}_0[c] = v$, $c > t$, and there is $c'$ such that $\mathtt {Vote}_0[c']=v$, $c'>c$, and $c' \succ _u c$. Consider the graph $G'$ achieved from G by adding a link between u and a supporter of c. The number of votes of c in the neighborhood of u in $G'$ becomes $v+1$, whereas it does not change for every other candidate. Hence, c is the winner in $G'$. However, if u votes for $c'$, then $c'$ will receive the same number of votes as c, and, since $c' > c$, it will be a winner that is preferred with respect to the actual winner c. Then, u has an incentive for voting $c'$ in place of the candidate voted at step 0. The claim follows since $c' \ne t$, because $c'> c > t$ by hypothesis.

If $\mathtt {Vote}_0[t] = v-1$, then, by definition of ${\mathsf {St}}_0$, we have that $t > c^*_0$. Moreover, by definition of ${\mathsf {Bl}}_1$, either $\mathtt {Vote}_0[c] = v$ or $\mathtt {Vote}_0[c] = v-1$. If $\mathtt {Vote}_0[c] = v$, then it must be the case that there is $c'$ such that $\mathtt {Vote}_0[c']=v$, $c'>c$, and $c' \succ _u c$. Consider the graph $G'$ achieved from G by adding a link between u and a supporter of c. The number of votes of c in the neighborhood of u in $G'$ becomes $v+1$, whereas it does not change for every other candidate. Hence, c is the winner in $G'$. However, if u votes for $c'$, then $c'$ will receive the same number of votes as c, and, since $c' > c$, it will be a winner that is preferred with respect to the actual winner c. Then, u has an incentive for voting $c'$ in place of the candidate voted at step 0. The claim follows since $c' \ne t$, because $\mathtt {Vote}_0[c'] = v > \mathtt {Vote}_0[t]$ by hypothesis. If $\mathtt {Vote}_0[c] = v-1$, then it must be the case that $c > t$, and there is $c'$ such that either $\mathtt {Vote}_0[c']=v$ and $c' \succ _u c$, or $\mathtt {Vote}_0[c']=v$, $c'>c$, and $c' \succ _u c$. Let us first assume that the former conditions on $c'$ hold. Consider the graph $G'$ achieved from G by adding a link between u and a supporter of c. The number of votes of c in the neighborhood of u in $G'$ becomes v, whereas it does not change for every other candidate. Hence, since $c> t > c^*_0$, then c is the winner in $G'$. However, if u votes for $c'$, then $c'$ will receive more votes than c, and it will be a winner that is preferred with respect to the actual winner c. Then, u has an incentive for voting $c'$ in place of the candidate voted at step 0. The claim follows since $c' \ne t$, because $c'> c > t$ by hypothesis.

Assume now that $\mathtt {Vote}_0[c']=v$, $c'>c$, and $c' \succ _u c$. Consider the graph $G'$ achieved from G by adding a link between u and a supporter of c. The number of votes of c in the neighborhood of u in $G'$ becomes v, whereas it does not change for every other candidate. Hence, since $c> t > c^*_0$, then c is the winner in $G'$. However, if u votes for $c'$, then $c'$ will receive the same number of votes as c, and, since $c' > c$, it will be a winner that is preferred with respect to the actual winner c. Then, u has an incentive for voting $c'$ in place of the candidate voted at step 0. The claim follows since $c' \ne t$, because $c'> c > t$ by hypothesis.

Consider now the case that ${\mathsf {St}}_0$ is empty. In this case, $\mathtt {Vote}_0[c] \in \{v, v-1, v-2\}$. If $\mathtt {Vote}_0[c] = v$, then $c \ne c^*_0$. Moreover, since $c^*_0$ win the election, $c^*_0 > c$, and, since $P'_0$ is empty, then $c^*_0 \succ _u c$. Consider the graph $G'$ achieved from G by adding a link between u and a supporter of c. The number of votes of c in the neighborhood of u in $G'$ becomes $v+1$, whereas it does not change for every other candidate. Hence, c is the winner in $G'$. However, if u votes for $c^*_0$, then $c^*_0$ will receive the same number of votes as c, and, since $c^*_0 > c$, it will be a winner that is preferred with respect to the actual winner c. Then, u has an incentive for voting $c^*_0$ in place of the candidate voted at step 0. The claim follows since $c^*_0 \ne t$, as showed above.

If $\mathtt {Vote}_0[c] = v-1$, then we distinguish two cases depending on who wins the tie-break between c and $c^*_0$. If $c > c^*_0$, then, by definition of ${\mathsf {Bl}}_1$, it must be the case that $c^*_0 \succ _u c$. Consider the graph $G'$ achieved from G by adding a link between u and a supporter of c. The number of votes of c in the neighborhood of u in $G'$ becomes v, whereas it does not change for every other candidate. Hence, since $c > c^*_0$, then c is the winner in $G'$. However, if u votes for $c^*_0$, then $c^*_0$ will receive more votes than every other candidate, and thus it will be a winner that is preferred with respect to the actual winner c. Then, u has an incentive for voting $c^*_0$ in place of the candidate voted at step 0. The claim follows since $c^*_0 \ne t$, as showed above.

If If $c > c^*_0$, then, by definition of ${\mathsf {Bl}}_1$, it must be the case that $c \ne t$ and $c \succ _u c^*_0$. Consider the graph $G'$ achieved from G by adding a link between u and a supporter of c. The number of votes of c in the neighborhood of u in $G'$ becomes v, whereas it does not change for every other candidate. However, since $c^*_0 > c$, then $c^*_0$ is the winner in $G'$. However, if u votes for c, then c will receive the same number of votes as $c^*_0$, and, since $c > c^*_0$, it will be a winner that is preferred with respect to the actual winner $c^*_0$. Then, u has an incentive for voting $c \ne t$ in place of the candidate voted at step 0.

Finally, if $\mathtt {Vote}_0[c] = v-2$, then, by definition of ${\mathsf {Bl}}_1$, it must be the case that $c \ne t$, $c < c^*_0$ and $c \succ _u c^*_0$. Consider the graph $G'$ achieved from G by adding a link between u and a supporter of c. The number of votes of c in the neighborhood of u in $G'$ becomes $v-1$, whereas it does not change for every other candidate. Since the set of candidates that takes most votes is not changed, then $c^*_0$ is the winner in $G'$. However, if u votes for c, then c will receive the same number of votes as $c^*_0$, and, since $c > c^*_0$, it will be a winner that is preferred with respect to the actual winner $c^*_0$. Then, u has an incentive for voting $c \ne t$ in place of the candidate voted at step 0.

Consider now the “if” part. That is, assume that a link has been added between u and a supporter of a candidate $c \notin {\mathsf {Bl}}_1$. If $c = c^*_0$, then the claim follows from Lemma 3. Otherwise let $\mathtt {Vote}_0[c^*_0] = v$. Consider first the case that $c \ne c^*_0 = t$. Consider the graph $G'$ achieved from G by adding a link between u and a supporter of c. We distinguish three cases. If $\mathtt {Vote}_0[c] = v$, then the number of votes of c in the neighborhood of u in $G'$ becomes $v+1$, whereas it does not change for every other candidate. Hence, c is the winner in $G'$. However, if u votes for t, then t will receive the same number of votes as c, and, since $t = c^*_0 > c$, it will be a winner that is preferred with respect to the actual winner c. Then, u has an incentive for voting t.

If $\mathtt {Vote}_0[c] = v-1$ and $c > t$, then the number of votes of c in the neighborhood of u in $G'$ becomes v, whereas it does not change for every other candidate. Hence, since $c > t = c^*_0$, then c is the winner in $G'$. However, if u votes for t, then t will receive more votes than c, and, it will be a winner that is preferred with respect to the actual winner c. Then, u has an incentive for voting t.

If $\mathtt {Vote}_0[c] < v-1$ or $\mathtt {Vote}_0[c] = v-1$ and $t > c$, then the number of votes of c in the neighborhood of u in $G'$ becomes at most v, whereas it does not change for every other candidate. Then, either the set of candidates that take more votes does not change, or still $c^*_0 = t$ win the tie-break against all of them. Since there is no possible winner that u would like more than $c^*_0$ and voting for the candidate voted at step 0 does not affect the outcome of the election, u will continue to vote for t.

Suppose now that $t \ne c^*_0$, but $\mathtt {Vote}_0[t] = v$. We consider first the case that $\mathtt {Vote}_0[c] < v$. Let $G'$ be the graph achieved from G by adding a link between u and a supporter of c. The number of votes of c in the neighborhood of u in $G'$ becomes at most v, whereas it does not change for every other candidate. Hence, the winner of the election will be either $c^*_0$ (if $\mathtt {Vote}_0[c]<v-1$ or $c^*_0 > c$) or c. However, if u votes for t, then t will receive more votes than both $c^*_0$ and c, and, it will be a winner that is preferred with respect to the actual winner. Then, u has an incentive for voting t.

Suppose, instead, that $\mathtt {Vote}_0[c] = v$. Let $G'$ be the graph achieved from G by adding a link between u and a supporter of c. The number of votes of c in the neighborhood of u in $G'$ becomes $v+1$, whereas it does not change for every other candidate. Hence, c is the winner in $G'$. We distinguish two cases based on who wins the tie-break between c and t. If $t > c$ and u votes for t, then t will receive the same votes as c, and thus it will be a winner that is preferred with respect to the actual winner c. Then, u has an incentive for voting t.

If, instead, $c > t$, then by definition of ${\mathsf {Bl}}_1$ it must be the case that for every $c'$ either $\mathtt {Vote}_0[c'] < v$ or $\mathtt {Vote}_0[c'] = v$ and either $c > c'$ or $c \succ _u c'$. Thus, if u votes for t or some other candidate $c'$ such that either $\mathtt {Vote}_0[c']<v$, or $\mathtt {Vote}_0[c']=v$ and $c > c'$, then the winner of the election does not change. If instead u votes for a candidate $c'$ such that $\mathtt {Vote}_0[c']=v$ and $c' > c$, then $c'$ becomes a winner, which is, since $c \succ _u c'$, less preferred than the actual winner. Thus, u cannot change the winner of the election in $G'$ in one that she prefers more than the actual winner, and thus she will vote at step 1 for the same candidate as the one voted at step 0, that is her preferred candidate t.

Consider now the case that $\mathtt {Vote}_0[t] = v-1$. If $t \in {\mathsf {St}}_0$, then it must be the case that $t > c^*_0$. We consider first the case that $\mathtt {Vote}_0[c] < v-1$. Let $G'$ be the graph achieved from G by adding a link between u and a supporter of c. The number of votes of c in the neighborhood of u in $G'$ becomes at most $v-1$, whereas it does not change for every other candidate. Hence, the winner of the election will be $c^*_0$. However, if u votes for t, then t will receive the same number of votes as $c^*_0$, and, since $t > c^*_0$, it will be a winner that is preferred with respect to the actual winner. Then, u has an incentive for voting t.

Suppose, instead, that $\mathtt {Vote}_0[c] = v-1$. Let $G'$ be the graph achieved from G by adding a link between u and a supporter of c. The number of votes of c in the neighborhood of u in $G'$ becomes v, whereas it does not change for every other candidate. Hence, the winner of the election will be either $c^*_0$ (if $c^*_0 > c$) or c. We distinguish two cases based on who wins the tie-break between c and t. If $t > c$ and u votes for t, then t will receive the same votes as both c and $c^*_0$, and thus, since both $t > c^*_0$ and $t > c$, it will be a winner that is preferred with respect to the actual winner. Then, u has an incentive for voting t.

If, instead, $c > t$, then by definition of ${\mathsf {Bl}}_1$ it must be the case that for every $c'$ either $\mathtt {Vote}_0[c'] < v-1$, or $\mathtt {Vote}_0[c'] = v-1$ and either $c > c'$ or $c \succ _u c'$, or $\mathtt {Vote}_0[c'] = v$ and $c \succ _u c'$ Thus, if u votes for t or some other candidate $c'$ such that either $\mathtt {Vote}_0[c']<v-1$, or $\mathtt {Vote}_0[c']=v-1$ and $c > c'$, then the winner of the election does not change. If instead u votes for a candidate $c'$ such that $\mathtt {Vote}_0[c']=v$, or $\mathtt {Vote}_0[c']=v-1$ and $c' > c$, then $c'$ becomes a winner, which is, since $c \succ _u c'$, less preferred than the actual winner. Thus, u cannot change the winner of the election in $G'$ in one that she prefers more than the actual winner, and thus she will vote at step 1 for the same candidate as the one voted at step 0, that is her preferred candidate t.

Finally, we consider the case that $\mathtt {Vote}_0[c] = v$. By definition of ${\mathsf {Bl}}_1$ it must be that for every $c'$ either $\mathtt {Vote}_0[c'] < v$ or $\mathtt {Vote}_0[c'] = v$ and either $c > c'$ or $c \succ _u c'$. Thus, if u votes for some candidate $c'$ such that either $\mathtt {Vote}_0[c']<v$, or $\mathtt {Vote}_0[c']=v$ and $c > c'$, then the winner of the election does not change. If instead u votes for a candidate $c'$ such that $\mathtt {Vote}_0[c']=v$ and $c' > c$, then $c'$ becomes a winner, which is, since $c \succ _u c'$, less preferred than the actual winner. Thus, u cannot change the winner of the election in $G'$ in one that she prefers more than the actual winner, and thus she will vote at step 1 for the same candidate as the one voted at step 0, that is her preferred candidate t.

Suppose now that $t \notin \{c^*_0\} \cup {\mathsf {St}}_0$. Note that this implies that ${\mathsf {St}}_0$ is empty, i.e., there is no candidate such that, if u votes for her, then it becomes a candidate preferred to $c^*_0$. Specifically, we have that for every $c'$ such that $\mathtt {Vote}_0[c'] = v$, we have that $c^*_0 \succ _u c$, whereas for every $c'$ such that $\mathtt {Vote}_0[c'] = v-1$ we have that either $c^*_0 > c$ or $c^*_0 \succ _u c$. Moreover, in this case we have, by definition of ${\mathsf {Bl}}_1$, that $\mathtt {Vote}_0[c] < v$. We consider first the case that $\mathtt {Vote}_0[c] < v-2$. Let $G'$ be the graph achieved from G by adding a link between u and a supporter of c. The number of votes of c in the neighborhood of u in $G'$ becomes at most $v-2$, whereas it does not change for every other candidate. Hence, the winner of the election will be $c^*_0$. Moreover, since the set of candidates with v or $v-1$ votes does not change and ${\mathsf {St}}_0$ is empty, then u cannot change the winner of the election in $G'$ in one that she prefers more than the actual winner, and thus she will vote at step 1 for the same candidate as the one voted at step 0, that is her preferred candidate t.

Suppose instead that $\mathtt {Vote}_0[c] \ge v-2$ and $c=t$. Observe that, since we are assuming that ${\mathsf {St}}_0$ is empty, then in this case either $\mathtt {Vote}_0[c]=v-2$ or $\mathtt {Vote}_0[c] = v-1$ and $c^*_0 > c$. Let $G'$ be the graph achieved from G by adding a link between u and a supporter of c. If $\mathtt {Vote}_0[c]=v-2$, then the number of votes of c in the neighborhood of u in $G'$ becomes $v-1$, whereas it does not change for every other candidate. Hence, the winner of the election will be $c^*_0$. If u votes for c, then c will have the same number of votes as $c^*_0$. If $c > c^*_0$, then $c=t$ become a winner that is preferred by u to the actual winner $c^*_0$. Then u has an incentive to vote $c = t$.

If $c < c^*_0$, then the winner of the election does not change. Moreover, since the votes taken by candidates different from c is the same as in G and ${\mathsf {St}}_0$ is empty, then u cannot change the winner of the election in $G'$ in one that she prefers more than the actual winner by voting one of these candidates, and thus she will vote at step 1 for the same candidate as the one voted at step 0, that is her preferred candidate t.

If $\mathtt {Vote}_0[c]=v-1$, then the number of votes of c in the neighborhood of u in $G'$ becomes v, whereas it does not change for every other candidate. However, since $c^*_0 > c$, the winner of the election will be $c^*_0$. If u votes for c, then c will have more votes than $c^*_0$, and, thus $c=t$ become a winner that is preferred by u to the actual winner $c^*_0$. Then u has an incentive to vote $c = t$.

Consider now the case that $\mathtt {Vote}_0[c] \ge v-2$ and $c\ne t$. Let us first assume that $\mathtt {Vote}_0[c] = v-2$. Then it must be that, by definition of ${\mathsf {Bl}}_1$, either $c^*_0>c$ or $c^*_0 \succ _u c$. Let $G'$ be the graph achieved from G by adding a link between u and a supporter of c. Then the number of votes of c in the neighborhood of u in $G'$ becomes $v-1$, whereas it does not change for every other candidate. Hence, the winner of the election will still be $c^*_0$. If u votes for c, then c will have the same number of votes as $c^*_0$. If $c > c^*_0$, then c becomes a winner that, since $c^*_0 > \succ _u c$, u likes less than the actual winner $c^*_0$. If $c < c^*_0$, then $c^*_0$ still remains the winner of the election. Moreover, since the votes taken by candidates different from c is the same as in G and ${\mathsf {St}}_0$ is empty, then u cannot change the winner of the election in $G'$ in one that she prefers more than the actual winner by voting one of these candidates, and thus she will vote at step 1 for the same candidate as the one voted at step 0, that is her preferred candidate t.

Finally, we assume that $\mathtt {Vote}_0[c] = v-1$. Let $G'$ be the graph achieved from G by adding a link between u and a supporter of c. Then the number of votes of c in the neighborhood of u in $G'$ becomes v, whereas it does not change for every other candidate. We distinguish two cases based on who win the tie-break between c and $c^*_0$. If $c^*_0 > c$, then, $c^*_0$ is the winner of the election in $G'$, and, by definition of ${\mathsf {Bl}}_1$, it must be that $c^*_0 \succ _u c$. If u votes for c, then c will have more votes than $c^*_0$, and thus it becomes a winner that u likes less than the actual winner $c^*_0$. Moreover, since the votes taken by candidates different from c is the same as in G and ${\mathsf {St}}_0$ is empty, then u cannot change the winner of the election in $G'$ in one that she prefers more than the actual winner by voting one of these candidates, and thus she will vote at step 1 for the same candidate as the one voted at step 0, that is her preferred candidate t.

If $c > c^*_0$, then, c is the winner of the election in $G'$, and, by definition of ${\mathsf {Bl}}_1$, it must be that $c \succ _u c^*_0$. It then follows that, since ${\mathsf {St}}_0$ is empty, $c \succ _u c'$ for every $c'$ such that $\mathtt {Vote}_0[c'] =v$, and either $c \succ _u c'$ or $c > c'$ for every $c'$ such that $\mathtt {Vote}_0[c'] =v-1$. If u votes for c or for a different candidate $c'$ such that either $\mathtt {Vote}_0[c'] < v-1$ or $\mathtt {Vote}_0[c'] = v-1$ and $c > c'$, then the outcome of the election does not change. If u instead votes for a candidate $c'$ such that either $\mathtt {Vote}_0[c'] = v$ or $\mathtt {Vote}_0[c'] = v-1$ and $c' > c$, then $c'$ becomes a winner that, since $c \succ _u c'$, u prefers less than the actual winner c. Therefore u cannot change the winner of the election in $G'$ in one that she prefers more than the actual winner by voting one of these candidates, and thus she will vote at step 1 for the same candidate as the one voted at step 0, that is her preferred candidate t. $\square$

Finally, we prove that, as for the case of ${\mathsf {Bl}}_0$, the addition of links between u and two supporters of $c \in {\mathsf {Bl}}_1$ is harmless.

Lemma 8

If ${\mathsf {St}}_0 = \{c^*_0\}$ or $t \in {\mathsf {St}}_0$, and links are added between u and two supporters of a candidate $c \in {\mathsf {Bl}}_1$, then u is stable in round 1.

Proof

Let $\mathtt {Vote}_0[c^*_0] = v$, let ${\hat{G}}$ be the graph before the link addition, and let ${\tilde{G}}$ be the graph obtained from ${\hat{G}}$ by adding links between u and two supporters of c. Since $c \in {\mathsf {Bl}}_1$, she received v, $v-1$ or $v-2$ votes among the neighbors of u.

The case in which $\mathtt {Vote}_0[c] = v$ is equal to the corresponding case in Lemma 6. Assume now that $\mathtt {Vote}_0[c] = v-1$. In this case c will be the winner of the election in ${\tilde{G}}$ since she receives $v+1$ votes while all the other candidates receive the same votes as in ${\hat{G}}$ (at most v). We distinguish two cases depending on whether $t \in {\mathsf {St}}_0$ or ${\mathsf {St}}_0 = \{c^*_0\}$.

If $t \in {\mathsf {St}}_0$, by Definition 4, for every candidate $c'$ with $\mathtt {Vote}_0[c'] = v$ it holds that $c> t> c^*_0 > c'$. Hence, u is not $(c, c')$-crucial and she will confirm the vote for t.

If ${\mathsf {St}}_0 = \{c^*_0\}$ and $c > c^*_0$, then $c> c^*_0 > c'$ for every $c'$ with $\mathtt {Vote}_0[c'] = v$. As above, u cannot influence the outcome of the election, and she will confirm her vote for t.

If ${\mathsf {St}}_0 = \{c^*_0\}$ and $c^*_0 > c$, by Definition 4, $c \succ _u c^*_0$. Moreover, since ${\mathsf {St}}_0 = \{c^*_0\}$, it must be the case that $c \succ _u c^*_0 \succ _u c'$ for every $c'$ with $\mathtt {Vote}_0[c'] = v$. Thus, if u would vote for a candidate $c'$ such that either $\mathtt {Vote}_0[c']<v$ or $\mathtt {Vote}_0[c']=v$ and $c > c'$, then her vote will not change the outcome of the election. Moreover, she would not vote for a candidate $c'$ such that $\mathtt {Vote}_0[c']=v$ and $c' > c$, since $c \succ _u c'$. Thus, also in this case, u will confirm her vote for t.

Finally, suppose that $\mathtt {Vote}_0[c] = v-2$. In this case it must be ${\mathsf {St}}_0 = \{c^*_0\}$. Thus, for every candidate $c'$ such that $\mathtt {Vote}_0[c'] = v$ we have that $c> c^*_0 > c'$ and $c \succ _u c^*_0 \succ _u c'$, and for every candidate $c'$ such that $\mathtt {Vote}_0[c'] = v-1$ we have that either $c> c^*_0 > c'$ or $c \succ _u c^*_0 \succ _u c'$. The number of votes received by c in the neighborhood of u in ${\tilde{G}}$ becomes v, while the other candidates receive the same votes as in ${\hat{G}}$ (at most v). Thus, since $c > c^*_0$, c is the winner in ${\tilde{G}}$. Moreover, for each candidate $c'$ such that u is $(c, c')$-crucial we have that $c \succ _u c'$. Thus, u will confirm her vote for t. $\square$

Proof of correctness. We are now ready to prove that our Node Stabilization procedure correctly stabilizes node u.

Lemma 9

Let ${\tilde{G}}$ be the graph obtained when running the Node Stabilization procedure on node $u \notin {\mathsf {Aff}}$. If we run the election on ${\tilde{G}}$, u will be stable both in rounds 1 and 2.

Moreover, no algorithm achieves this goal by adding less links to the social network.

Proof

The proof that u will be stable in rounds 1 and 2 of the election in ${\tilde{G}}$ follows from Lemmas 3, 5, 6, 7, and 8. In the following we prove that our algorithm uses the minimum number of links to stabilize u.

Note that, whenever $|{\mathsf {St}}_i| > 1$ and $t \notin {\mathsf {St}}_i$ for some $i \in \{0,1\}$, by Observation 1 we need to add at least one link to stabilize u. Since our algorithm adds at most two links, we have only to prove that whenever we add two links, no other algorithm could stabilize u adding only one link.

There are two cases in which the Node Stabilization procedure adds two links to the graph. The first case is when in $G'$ (the graph returned by the Influence phase), u is stable in round 1 and not stable in round 2 and ${\mathsf {St}}_1 \subseteq {\mathsf {Bl}}_1$. Suppose that we could have u stable in both the rounds by simply adding a single link between u and a supporter of a candidate c. If $c \notin {\mathsf {St}}_1$, then, by Lemma 4, u will not be stable in 2; if $c \in {\mathsf {St}}_1$, instead, $c \in {\mathsf {Bl}}_1$, and, by Lemma 7, u will be not stable in round 1. Hence, we have proven that in this case at least two links are necessary to stabilize u in both the rounds.

The second case in which the Node Stabilization procedure adds two links to the graph is when u is not stable in round 1 and the condition of Line 2 is not satisfied. As before, suppose that we could have u stable in both the rounds by simply adding a single link between u and a supporter of a candidate c. If $c \notin {\mathsf {St}}_0$, then, by Lemma 4, u is not stable in round 1; if $c \in {\mathsf {St}}_0$, instead, by hypothesis, u will be not stable in round 2. Hence, also in this case we have proven that at least two links are necessary to stabilize u in both the rounds. $\square$

We now are ready to prove Lemma 2.

Proof of Lemma 2

Let $G''$ be the graph returned by the Stabilization phase. In order to prove the Lemma we have only to show that in an election on $G''$ every node $u \notin {\mathsf {Aff}}$ will be stable both in rounds 1 and 2. In fact, by Lemma 1 we know that all the affected nodes vote for the designated candidate w in rounds $i \ge 2$. Hence, in round 3 all the nodes confirm the vote expressed in the previous round and the election stops.

We start considering a node $u \in B$. In this case, the claim follows from Lemma 9, as long as there are sufficiently many nodes in ${\mathsf {Seed}}$ to add the required links. However, the Stabilization phase requires to add at most two links between u and nodes in ${\mathsf {Seed}}$ that are supporters of the same candidate and are not neighbors of u. Since ${\mathsf {Seed}}$ includes three supporters for each candidate with no common neighbors, we can always find the supporters required to stabilize u.

Consider now a node $u \in {\mathsf {Seed}}$. In this case, to stabilize u we have to add at most two links between u and two nodes in ${\mathsf {SSeed}}$ that are supporters of the same candidate c and are not adjacent to u. Since, by construction, ${\mathsf {SSeed}}$ contains two supporters of each candidate that are not adjacent to seeds, we certainly find the supporters required to stabilize u.

Finally, consider a node $u \in {\mathsf {SSeed}}$. Observe that in the Stabilization phase we add only links between u and nodes in ${\mathsf {Seed}}$. Since ${\mathsf {Seed}}$ contains 3 supporters of each candidate, then u will have at most 3 new neighbors in $G''$ voting for each candidate c. Let $c^*_0$ be the candidate that is supported by the majority of neighbors of u. We next show that if we add links from u to 4 supporters of $c^*_0$ node u will be stable in round 1. Since u does not have neighbors in ${\mathsf {Aff}}$, all her neighbors vote in round 1 for their favorite candidate, and thus u does not change her vote in successive rounds.

Consider, indeed, the graph ${\tilde{G}}$ obtained from $G'$ by adding links between u and three supporters of each candidate c. Note that the view of u in ${\tilde{G}}$ is exactly the same as in $G'$. In particular, $c^*_0$ is still the candidate that is supported by the majority of neighbors of u and the best response for u in ${\tilde{G}}$ is the same as in $G'$. Anyway, by Lemma 3 we have that it is sufficient to add a link (the fourth one) between u and a supporter of $c^*_0$, to stabilize u in round 1. Moreover, Lemma 3 also states that this property continues to hold if links between u and supporters of $c \ne c^*_0$ (that is, if less than 3 seed nodes are connected to u during the seed stabilization phase) are removed or if further links are added between u and supporters of $c^*_0$ (that is, if more than zero seed nodes supporting $c^*_0$ are connected to u during the stabilization phase). $\square$

5 Experiments

We compared our algorithm against the heuristic proposed by Sina et al. (2015) on a real dataset. Specifically, we consider the social network dataset “Facebook MHRW” (Gjoka et al. 2010), that contains a sample of the Facebook structure taken over about 900,000 nodes. For our tests, we sampled from this network 10 different graphs over 25,000 nodes, by running a BFS from ten different randomly selected nodes. For each of these graphs we assigned the preferences to its nodes according to three different approaches: (i) each voter is assigned a randomly selected preference list; (ii) each voter is assigned a randomly selected single-peaked preference list; (iii) we used a dataset of real preference lists available from PrefLib, that contains the results of surveys about sushi preferences, and assigned to each voter a random preference list among the ones in the dataset. In particular, for each graph we run 30 simulations with random preference lists, 10 with random single-peaked preference lists, and 10 with real preference lists.

For each combination of graph and preference list we consider a setting with 5 candidates, and we select as the desired candidate w to be the candidate that is ranked as 2nd, 3rd, 4th, and 5th with respect to the number of supporters. Hence, in total we run our simulations on $4 \times 50 \times 10 = 2000$ different settings. For each of these settings we run both our algorithm, and the heuristic provided by Sina et al. (2015).

We observe that our algorithm correctly computes a set of links such that their addition to the original graph, assures that the desired candidate w wins the election. We remark that on the same settings, the heuristic of Sina et al. (2015) fails in about 30% of the runs, by returning a set of links that is insufficient to make w the winner of the election.

Next picture shows that this guarantee comes at a limited cost in term of the number of added links. Indeed, as showed in Fig. 2, the number of links added by our algorithm is in the same order of magnitude as the one added by Sina et al. (2015), even if slightly larger. We remark anyway that our code does not implement any of the optimizations that (Sina et al. 2015) adopts in the influence phase (even if, as stated above, this would be possible to do).

Fig. 2

The number of added links with respect to the four different choice for the desired candidate w

Next we evaluate the performances of our approach with respect to the parameters of the problem, namely the choice of w and the initial distribution of preferences.

We observe indeed that whenever the initial distribution of preferences is essentially random (both for randomly selected preference lists and for randomly selected single-peaked preference lists) the results are more or less the same. The average number of nodes processed during the first phase goes from about 20 when the desired winner is the second most voted candidate in the initial ranking, to about 125 when the desired winner is the less voted candidate in the initial ranking. Similarly, the average number of added links is always below 5000 in all the considered cases and it is less than 2000 when the desired winner is the second most voted candidate.

The scenario is completely different, instead, if one considers real distributions. In fact, these may be very biased towards one candidate, and thus in these cases it could be very difficult to subvert the result of the election. This is exactly what we observed in our experiments: even when the desired winner was the second most voted candidate, it has been necessary to influence in average about 100 nodes and to add in average more than 5000 links. The manipulation becomes almost impossible when the desired candidate has an even worse ranking, since it would be necessary to add in average more the 130,000 links. Figure 3 highlights these observations.

Fig. 3

Number of influenced nodes and added links w.r.t. to different choices of w and preference assignments

6 Conclusions

In this paper we presented an algorithm to compute a set of edges to add to a social network in order to manipulate the outcome of an election and have a sponsored candidate to win. We proved that our algorithm adds the minimum number of edges and it works on mild conditions on the structure of the social network and on the preference lists of the voters.

We also run extensive experiments to validate performances of our algorithm and compare to the algorithm presented in Sina et al. (2015). The experiments show that our algorithm adds a number of edges that is similar to their heuristic but it has a 100% success rate. We plan to run even more extensive experiments in even more realistic settings.

Our results can be seen as another indication that the control of social media is a great threat to our democracy since the controller has an extraordinary power in determining which information we are exposed to and can use this power to control and influence our crucial decisions. This threat was already highlighted by several works in the case that voters are myopic and they are simply influenced by their neighbors (and possibly by their own belief).

In this paper we enforce the message of Sina et al. (2015), by showing that manipulation can be often effective even if voters are instead strategic and they can decide to vote for a candidate different from their favourite. Clearly, we acknowledge that neither of these two extremal behaviors fully represents the real world: usually, people’s decisions depend on both the influence of their social relationships and by strategic considerations based on their limited view. Hence, it would be interesting to evaluate the extent at which these manipulability results extend to this more realistic environment.

Moreover, most of the works on the election manipulability problem (including this one) make a lot of simplifying assumptions: e.g., voters’ knowledge is limited to their own neighborhood; they perfectly know their neighbors’ votes; they have a total order of candidates. In a real world setting, some of these assumptions could not hold: e.g., polls can provide an aggregate information about the rest of the network; voters could have only incomplete information about their neighbors’ votes (i.e., received messages could be blurry or could be lost in the mess of information that one receives nowadays through social media). It would be an interesting direction to verify at which extent the manipulability results hold when some of these assumptions are relaxed and voters are assumed to have limited rationality², where the extent of limited rationality may depend on how much the voters know about the rest of the networks, how confident they are about the signals received by their neighbors, or about their own choices.

The results presented in this paper can be seen a contribution towards the fundamental step of drawing of the boundary of the manipulability of social networks. These results allow not only to establish when an intervention is necessary, but thay also suggest some form of intervention, such as constraining the network to be one robust against manipulation. Nevertheless, we highlight that other forms of intervention can be operated, even when it is not possible to work on the network topology: e.g., quarantining particular nodes (Aspnes et al. 2006), or including in the network special nodes working as monitors (Zhang et al. 2015; Amoruso et al. 2017) are among the most effective proposal of intervention that have been recently suggested in literature.