Election Control by Manipulating Issue Significance

Andrew Estornell, Sanmay Das, Edith Elkind, Yevgeniy Vorobeychik
Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI), PMLR 124:340-349, 2020.

Abstract

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 Rothe [2016].One means of election control that has been proposed, pertinent to the spatial voting model, 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 becomes 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 behavior enables tractable manipulation.

Cite this Paper

BibTeX
@InProceedings{pmlr-v124-estornell20a, title = {Election Control by Manipulating Issue Significance}, author = {Estornell, Andrew and Das, Sanmay and Elkind, Edith and Vorobeychik, Yevgeniy}, booktitle = {Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)}, pages = {340--349}, year = {2020}, editor = {Peters, Jonas and Sontag, David}, volume = {124}, series = {Proceedings of Machine Learning Research}, month = {03--06 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v124/estornell20a/estornell20a.pdf}, url = {https://proceedings.mlr.press/v124/estornell20a.html}, abstract = {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 Rothe [2016].One means of election control that has been proposed, pertinent to the spatial voting model, 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 becomes 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 behavior enables tractable manipulation.} }
Endnote
%0 Conference Paper %T Election Control by Manipulating Issue Significance %A Andrew Estornell %A Sanmay Das %A Edith Elkind %A Yevgeniy Vorobeychik %B Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI) %C Proceedings of Machine Learning Research %D 2020 %E Jonas Peters %E David Sontag %F pmlr-v124-estornell20a %I PMLR %P 340--349 %U https://proceedings.mlr.press/v124/estornell20a.html %V 124 %X 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 Rothe [2016].One means of election control that has been proposed, pertinent to the spatial voting model, 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 becomes 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 behavior enables tractable manipulation.
APA
Estornell, A., Das, S., Elkind, E. & Vorobeychik, Y.. (2020). Election Control by Manipulating Issue Significance. Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI), in Proceedings of Machine Learning Research 124:340-349 Available from https://proceedings.mlr.press/v124/estornell20a.html.

Related Material