Unweighted Coalitional Manipulation under the Borda Rule Is NP-Hard

Betzler, Nadja; Niedermeier, Rolf; Woeginger, Gerhard J.

doi:10.5591/978-1-57735-516-8/IJCAI11-021

Unweighted Coalitional Manipulation under the Borda Rule Is NP-Hard

Nadja Betzler, Rolf Niedermeier, Gerhard J. Woeginger

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 55-59.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-021

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.

Nadja Betzler, Rolf Niedermeier, and Gerhard J. Woeginger. 2011. Unweighted Coalitional Manipulation under the Borda Rule Is NP-Hard. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 55–59. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-021

@inproceedings{ijcai2011p21,
  title     = {Unweighted Coalitional Manipulation under the Borda Rule Is NP-Hard},
  author    = {Betzler, Nadja and Niedermeier, Rolf and Woeginger, Gerhard J.},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {55--59},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-021},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-021},
}

TY  - CPAPER
TI  - Unweighted Coalitional Manipulation under the Borda Rule Is NP-Hard
AU  - Betzler, Nadja
AU  - Niedermeier, Rolf
AU  - Woeginger, Gerhard J.
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 55
EP  - 59
DO  - 10.5591/978-1-57735-516-8/IJCAI11-021
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-021
ER  -