text: 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.
  @cite_18: 
  @cite_31: We consider elections where the chair replaces either candidates or votes, with the goal of making a specific candidate win (constructive control) or lose (destructive control). We call this replacement control'' and study its computational complexity for several scoring rules (plurality, veto, Borda, k-approval), as well as for approval voting.
  @cite_7: Multi-winner elections model scenarios where voters must select a fixed-size group of candidates based on their individual preferences. In such scenarios, it is often the case that voters are incentivized to manipulate, i.e. misreport their preferences in order to obtain a better outcome. In this paper, we study the complexity of manipulating multi-winner elections under scoring rules, with a particular focus on the role of tie-breaking rules. We consider both lexicographic tie-breaking rules, which break ties according to a fixed ordering of the candidates, and a natural randomized tie-breaking rule. We describe polynomial-time manipulation algorithms for several special cases of our problem. Specifically, we show that finding a successful manipulation is easy if the underlying voting rule is k-Approval or the number of candidates to be elected is bounded by a constant (for both types of tie-breaking rules), as well as if the manipulator's utility function only takes values in 0, 1 and the ties are broken in the manipulator's favor.
  @cite_8: 
  @cite_41: 
  @cite_28: 
  @cite_9: 
  @cite_36: Complexity of voting manipulation is a prominent research topic in computational social choice. The voting manipulation literature usually assumes that the manipulator is only concerned with improving the outcome of the election from her perspective. However, in practice, the manipulator may also be reluctant to lie, i.e., she may have a preference for submitting a vote that does not deviate too much from her true ranking of the candidates. In this paper, we study the complexity of finding a manipulative vote that achieves the manipulator's goal yet is as close as possible to her true preference order. We analyze this problem for three natural notions of closeness, namely, swap distance, footrule distance, and maximum displacement distance, and a variety of voting rules, such as scoring rules, Bucklin, Copeland, and Maximin. For all three distances, we obtain polynomial-time algorithms for all scoring rules and Bucklin and hardness results for Copeland and Maximin.
  @cite_32: 
  @cite_16: 
  @cite_0: 
  @cite_27: 
  @cite_40: 
  @cite_15: 
  @cite_34: We study the complexity of the bribery problem with distance restrictions. In particular, in the bribery problem, we are given an election and a distinguished candidate p, and are asked whether we can make p win not win the election by bribing at most k voters to recast their votes. In the bribery problem with distance restrictions, we require that the votes recast by the bribed voters are close to their original votes. To measure the closeness between two votes, we adopt the prevalent Kendall-Tau distance and the Hamming distance. We achieve a wide range of complexity results for this problem under a variety of voting correspondences, including the Borda, Condorcet, Copelandα for every 0 ≤ e ≤ 1 and Maximin.
  @cite_25: 
  @cite_20: We study the computational complexity of candidate control in elections with few voters (that is, we take the number of voters as a parameter). We consider both the standard scenario of adding and deleting candidates, where one asks if a given candidate can become a winner (or, in the destructive case, can be precluded from winning) by adding deleting some candidates, and a combinatorial scenario where adding deleting a candidate automatically means adding deleting a whole group of candidates. Our results show that the parameterized complexity of candidate control (with the number of voters as the parameter) is much more varied than in the setting with many voters.
summary: Our work is closely related to two research areas: election control and influence maximization. These bodies of work are separate: to our knowledge there is no previous work which considers election control social influence. The computational study of election control was started by @cite_0 , who considered constructive control. The destructive control setting was introduced by @cite_25 . A large body of work has studied election control under different settings and voting rules @cite_41 @cite_18 including bribing voters @cite_27 @cite_9 @cite_28 @cite_15 @cite_34 , adding or deleting voters @cite_32 @cite_31 @cite_8 @cite_40 , and adding or deleting candidates @cite_20 @cite_8 @cite_40 . Another topic is strategic behavior on the part of the voters themselves @cite_16 @cite_36 @cite_7 . The main difference between our work and previous work on election control is that we introduce and analyze social influence as a novel mechanism for both constructive and destructive control.