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.
| Original language | English |
|---|---|
| Title of host publication | Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI 2011, Barcelona, Catalonia, Spain, July 16-22, 2011) |
| Editors | T. Walsh |
| Place of Publication | Menlo Park CA |
| Publisher | AAI Press |
| Pages | 55-60 |
| ISBN (Print) | 978-1-57735-516-8 |
| DOIs | |
| Publication status | Published - 2011 |
Fingerprint
Dive into the research topics of 'Unweighted coalitional manipulation under the Borda rule is NP-hard'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver