Is It (Computationally) Hard to Steal an Election?


Yevgeniy Vorobeychik

Event Details
Thursday, November 4, 2021
Talk:
3:30 p.m., Zoom

Reception:
N/A, N/A

Yevgeniy Vorobeychik, Ph.D.

Associate Professor, Washington University in Saint Louis

Abstract

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.

Speaker Bio

Yevgeniy Vorobeychik is an Associate Professor of Computer Science & Engineering at Washington University in Saint Louis. Previously, he was an Assistant Professor of Computer Science at Vanderbilt University. Between 2008 and 2010 he was a post-doctoral research associate at the University of Pennsylvania Computer and Information Science department. He received Ph.D. (2008) and M.S.E. (2004) degrees in Computer Science and Engineering from the University of Michigan, and a B.S. degree in Computer Engineering from Northwestern University. His work focuses on game theoretic modeling of security and privacy, adversarial machine learning, algorithmic and behavioral game theory and incentive design, optimization, agent-based modeling, complex systems, network science, and epidemic control. Dr. Vorobeychik received an NSF CAREER award in 2017, and was invited to give an IJCAI-16 early career spotlight talk. He also received several Best Paper awards, including one of 2017 Best Papers in Health Informatics. He was nominated for the 2008 ACM Doctoral Dissertation Award and received honorable mention for the 2008 IFAAMAS Distinguished Dissertation Award.