Is It (Computationally) Hard to Steal an Election?

The integrity of elections is central to democratic systems. However, a myriad of malicious actors aspire to influence election outcomes for financial or political benefit.  The issue of election vulnerability to malicious manipulation has been studied in the computational social choice literature from a computational complexity perspective.  However, the traditional study of election control models voter preferences as rankings over candidates. This provides no natural way to reason about manipulations by attackers of specific issues that influence such preferences. Spatial theory of voting offers a social choice model that explicitly captures voter and candidate positions on issues, with voter preferences over candidates determined by their relative distance in issues space.  We study the problem of election manipulation within the framework of spatial voting theory, by considering three models of malicious manipulation: 1) changing which issues are salient to voters (issue selection control, or ISC), 2) changing the relative importance of issues (issue significance manipulation, or ISM), and 3) changing how voters perceive where a particular candidate stands on issues (issue perception control, or IPC).  All three models capture different aspects of the impact that political advertising or even misinformation can have on voter behavior.  In all cases, the manipulation problem is NP-hard in general, even when there are only 2 candidates.  ISC remains hard even when we have a single voter if issues are real-valued, and even with 3 or more voters if issues are binary.  ISM and IPC, however, have considerably more interesting structure.  In particular, we find that one crucial element is opinion diversity: if voter views are highly diverse, election control is hard, whereas when diversity is limited, with only a constant number of groups of voters with essentially identical views, control becomes tractable.  Finally, we consider the problem of election manipulation by spreading misinformation over social networks, and close with a discussion of potential mitigations.