The Complexity of Manipulative Attacks in Nearly Single-Peaked Electorates (Extended Abstract)
Abstract
Many electoral control and manipulation problems — which we will refer to in general as manipulative actions problems — are NP-hard in the general case. Many of these problems fall into polynomial time if the electorate is single-peaked, i.e., is polarized along some axis/issue. However, real-world electorates are not truly single-peaked — for example, there may be some maverick voters — and to take this into account, we study the complexity of manipulative-action algorithms for the case of nearly single-peaked electorates.
Cite
Text
Faliszewski et al. "The Complexity of Manipulative Attacks in Nearly Single-Peaked Electorates (Extended Abstract)." International Joint Conference on Artificial Intelligence, 2015.Markdown
[Faliszewski et al. "The Complexity of Manipulative Attacks in Nearly Single-Peaked Electorates (Extended Abstract)." International Joint Conference on Artificial Intelligence, 2015.](https://mlanthology.org/ijcai/2015/faliszewski2015ijcai-complexity/)BibTeX
@inproceedings{faliszewski2015ijcai-complexity,
title = {{The Complexity of Manipulative Attacks in Nearly Single-Peaked Electorates (Extended Abstract)}},
author = {Faliszewski, Piotr and Hemaspaandra, Edith and Hemaspaandra, Lane A.},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2015},
pages = {4178-4182},
url = {https://mlanthology.org/ijcai/2015/faliszewski2015ijcai-complexity/}
}