  Election control considers the problem of an adversary who attempts to tamper
with a voting process, in order to either ensure that their favored candidate
wins (constructive control) or another candidate loses (destructive control).
As online social networks have become significant sources of information for
potential voters, a new tool in an attacker's arsenal is to effect control by
harnessing social influence, for example, by spreading fake news and other
forms of misinformation through online social media.
  We consider the computational problem of election control via social
influence, studying the conditions under which finding good adversarial
strategies is computationally feasible. We consider two objectives for the
adversary in both the constructive and destructive control settings:
probability and margin of victory (POV and MOV, respectively). We present
several strong negative results, showing, for example, that the problem of
maximizing POV is inapproximable for any constant factor. On the other hand, we
present approximation algorithms which provide somewhat weaker approximation
guarantees, such as bicriteria approximations for the POV objective and
constant-factor approximations for MOV. Finally, we present mixed integer
programming formulations for these problems. Experimental results show that our
approximation algorithms often find near-optimal control strategies, indicating
that election control through social influence is a salient threat to election
integrity.
