Election Control in Social Networks via Edge Addition or Removal

Authors

  • Matteo Castiglioni Politecnico di Milano
  • Diodato Ferraioli Università degli Studi di Salerno
  • Nicola Gatti Politecnico di Milano

DOI:

https://doi.org/10.1609/aaai.v34i02.5556

Abstract

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).

Downloads

Published

2020-04-03

How to Cite

Castiglioni, M., Ferraioli, D., & Gatti, N. (2020). Election Control in Social Networks via Edge Addition or Removal. Proceedings of the AAAI Conference on Artificial Intelligence, 34(02), 1878-1885. https://doi.org/10.1609/aaai.v34i02.5556

Issue

Section

AAAI Technical Track: Game Theory and Economic Paradigms