Unweighted Coalitional Manipulation Under the Borda Rule Is NP-Hard Nadja Betzler Rolf Niedermeier Gerhard J. Woeginger
Abstract
The Borda voting rule is a positional scoring rule where, for m candidates, for every vote the ?rst 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 U NWEIGHTED C OALITIONAL M ANIP ULATION UNDER B ORDA : 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.