Election Control in Social Networks via Edge Addition or Removal

We focus on the scenario in which messages pro and/or against one or multiple candidates are spread through a social network in order to affect the votes of the receivers. Several results are known in the literature when the manipulator can make seeding by buying influencers. In this paper, instead, we assume the set of influencers and their messages to be given, and we ask whether a manipulator ( e.g., the platform) can alter the outcome of the election by adding or removing edges in the social network. We study a wide range of cases distinguishing for the number of candidates or for the kind of messages spread over the network. We provide a positive result, showing that, except for trivial cases, manipulation is not affordable, the optimization problem being hard even if the manipulator has an unlimited budget ( i.e., he can add or remove as many edges as desired). Furthermore, we prove that our hardness results still hold in a reoptimization variant, where the manipulator already knows an optimal solution to the problem and needs to compute a new solution once a local modification occurs ( e.g., in bandit scenarios where estimations related to random variables change over time). Introduction Nowadays, social network media are the most used, if not the unique, sources of information. This indisputable fact turned out to influence most of our daily actions, and also to have severe effects on the political life of our countries. Indeed, in many of the recent political elections around the world, there has been evidence of the impact that false or incomplete news spread through these media influenced the electoral outcome. For example, in the recent US presidential election, Allcott and Gentzkow (2017) and Guess, Nyhan, and Reifler (2018) show that, on average, 92% of Americans remembered pro-Trump false news, while 23% of them remembered the pro-Clinton fake news. As another example, Ferrara (2017) shows that automated accounts in Twitter spread a considerable amount of political news in order to alter the outcome of 2017 French elections. In this scenario, a natural question is to understand at which extent the spread of (mis)information on social network media may alter the result of a political election. This topic has recently received large interest in the community: e.g., Auletta et al. (2015; 2017a; 2017b) show that, in the case of two only candidates, a manipulator may be able to lead the minority to become a majority by influencing the order in which voters change their mind.