---
title: "Unweighted Coalitional Manipulation under the Borda Rule Is NP-Hard"
authors:
  - "Nadja Betzler"
  - "Rolf Niedermeier"
  - "Gerhard J. Woeginger"
doi: "10.5591/978-1-57735-516-8/IJCAI11-021"
url: "https://ijcai.org/proceedings/2011/21"
pdf: "https://ijcai.org/proceedings/2011/0021.pdf"
venue: "Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence"
year: 2011
pages: "55-59"
track: ""
keywords:
---

# Unweighted Coalitional Manipulation under the Borda Rule Is NP-Hard

Nadja Betzler, Rolf Niedermeier, Gerhard J. Woeginger

*Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence*, pages 55-59. DOI: [10.5591/978-1-57735-516-8/IJCAI11-021](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.