More Like this

1. Election Control by Manipulating Issue Significance

   Estornell, Andrew ; Das, Sanmay ; Elkind, Edith ; Vorobeychik, Yevgeniy ( January 2020 , Conference on Uncertainty in Artificial Intelligence (UAI))

   Integrity of elections is vital to democratic systems, but it is frequently threatened by malicious actors. The study of algorithmic complexity of the problem of manipulating election outcomes by changing its structural features is known as election control. One means of election control that has been proposed is to select a subset of issues that determine voter preferences over candidates. We study a variation of this model in which voters have judgments about relative importance of issues, and a malicious actor can manipulate these judgments. We show that computing effective manipulations in this model is NP-hard even with two candidates or binary issues. However, we demonstrate that the problem is tractable with a constant number of voters or issues. Additionally, while it remains intractable when voters can vote stochastically, we exhibit an important special case in which stochastic voting enables tractable manipulation.
2. Manipulating Elections by Selecting Issues

   Lu, Jasper ; Zhang, David ; Rabinovich, Zinovi ; Obraztsova, Svetlana ; Vorobeychik, Yevgeniy ( January 2019 , International Conference on Autonomous Agents and Multiagent Systems)

   Constructive election control considers the problem of an adversary who seeks to sway the outcome of an electoral process in order to ensure that their favored candidate wins. We consider the computational problem of constructive election control via issue selection. In this problem, a party decides which political issues to focus on to ensure victory for the favored candidate. We also consider a variation in which the goal is to maximize the number of voters supporting the favored candidate. We present strong negative results, showing, for example, that the latter problem is inapproximable for any constant factor. On the positive side, we show that when issues are binary, the problem becomes tractable in several cases, and admits a 2-approximation in the two-candidate case. Finally, we develop integer programming and heuristic methods for these problems.
3. UnclearBallot: Automated Ballot Image Manipulation

   Matthew Bernhard, Kartikeya Kandula ( October 2021 , Proc. 4th International Joint Conference on Electronic Voting (E-Vote-ID ’19))

   As paper ballots and post-election audits gain increased adoption in the United States, election technology vendors are offering products that allow jurisdictions to review ballot images—digital scans produced by optical-scan voting machines—in their post-election audit procedures. Jurisdictions including the state of Maryland rely on such image audits as an alternative to inspecting the physical paper ballots. We show that image audits can be reliably defeated by an attacker who can run malicious code on the voting machines or election management system. Using computer vision techniques, we develop an algorithm that automatically and seamlessly manipulates ballot images, moving voters’ marks so that they appear to be votes for the attacker’s preferred candidate. Our implementation is compatible with many widely used ballot styles, and we show that it is effective using a large corpus of ballot images from a real election. We also show that the attack can be delivered in the form of a malicious Windows scanner driver, which we test with a scanner that has been certified for use in vote tabulation by the U.S. Election Assistance Commission. These results demonstrate that post-election audits must inspect physical ballots, not merely ballot images, if they are to strongly defend against computer-basedmore »attacks on widely used voting systems.« less
4. Most Expected Winner: An Interpretation of Winners over Uncertain Voter Preferences

   Haoyue Ping and Julia Stoyanovich ( June 2023 , Proceedings of the '23 International Conference on the Management of Data (ACM SIGMOD 2023))

   It remains an open question how to determine the winner of an election given incomplete or uncertain voter preferences. One solution is to assume some probability space for the voting profile and declare that the candidates having the best chance of winning are the (co-)winners. We refer to this interpretation as the Most Probable Winner (MPW). In this paper, we focus on elections that use positional scoring rules, and propose an alternative winner interpretation, the Most Expected Winner (MEW), according to the expected performance of the candidates. We separate the uncertainty in voter preferences into the generation step and the observation step, which gives rise to a unified voting profile combining both incomplete and probabilistic voting profiles. We use this framework to establish the theoretical hardness of MEW over incomplete voter preferences, and then identify a collection of tractable cases for a variety of voting profiles, including those based on the popular Repeated Insertion Model (RIM) and its special case, the Mallows model. We develop solvers customized for various voter preference types to quantify the candidate performance for the individual voters, and propose a pruning strategy that optimizes computation. The performance of the proposed solvers and pruning strategy is evaluatedmore »extensively on real and synthetic benchmarks, showing that our methods are practical.« less
5. Controlling Elections through Social Influence

   Wilder, Bryan ; Vorobeychik, Yevgeniy ( January 2018 , International Conference on Autonomous Agents and Multiagent Systems)

   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 approxima- tion 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. Ex- perimental results show that our approximation algorithms often find near-optimal control strategies, indicating that election controlmore »through social influence is a salient threat to election integrity.« less