Unweighted coalitional manipulation under the Borda rule is NP-hard

N. Betzler, R. Niedermeier, G.J. Woeginger

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

58 Citations (Scopus)
2 Downloads (Pure)

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 languageEnglish
Title of host publicationProceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI 2011, Barcelona, Catalonia, Spain, July 16-22, 2011)
EditorsT. Walsh
Place of PublicationMenlo Park CA
PublisherAAI Press
Pages55-60
ISBN (Print)978-1-57735-516-8
DOIs
Publication statusPublished - 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