Unweighted Coalitional Manipulation Under the Borda Rule Is NP-Hard
Abstract
The Borda voting rule is a positional scoring rule where, for m candidates, for every vote the first candidate receives m-1 points, the second m-2 points and so on. A Borda winner is a candidate with highest total score. It has been a prominent open problem to determine the computational complexity of Unweighted Coalitional Manipulation under Borda: Can one add a certain number of additional votes (called manipulators) to an election such that a distinguished candidate becomes a winner? We settle this open problem by showing NP-hardness even for two manipulators and three input votes. Moreover, we discuss extensions and limitations of this hardness result.
Cite
Text
Betzler et al. "Unweighted Coalitional Manipulation Under the Borda Rule Is NP-Hard." International Joint Conference on Artificial Intelligence, 2011. doi:10.5591/978-1-57735-516-8/IJCAI11-021Markdown
[Betzler et al. "Unweighted Coalitional Manipulation Under the Borda Rule Is NP-Hard." International Joint Conference on Artificial Intelligence, 2011.](https://mlanthology.org/ijcai/2011/betzler2011ijcai-unweighted/) doi:10.5591/978-1-57735-516-8/IJCAI11-021BibTeX
@inproceedings{betzler2011ijcai-unweighted,
title = {{Unweighted Coalitional Manipulation Under the Borda Rule Is NP-Hard}},
author = {Betzler, Nadja and Niedermeier, Rolf and Woeginger, Gerhard J.},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2011},
pages = {55-60},
doi = {10.5591/978-1-57735-516-8/IJCAI11-021},
url = {https://mlanthology.org/ijcai/2011/betzler2011ijcai-unweighted/}
}