资源论文Unweighted Coalitional Manipulation Under the Borda Rule Is NP-Hard Nadja Betzler Rolf Niedermeier Gerhard J. Woeginger

Unweighted Coalitional Manipulation Under the Borda Rule Is NP-Hard Nadja Betzler Rolf Niedermeier Gerhard J. Woeginger

2019-11-12 | |  62 |   39 |   0
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.

上一篇:Coalitional Voting Manipulation: A Game-Theoretic Perspective Yoram Bachrach Edith Elkind Piotr Faliszewski

下一篇:Approximately Strategy-Proof Voting Eleanor Birrell? and Rafael Pass†

用户评价
全部评价

热门资源

  • The Variational S...

    Unlike traditional images which do not offer in...

  • Learning to Predi...

    Much of model-based reinforcement learning invo...

  • Stratified Strate...

    In this paper we introduce Stratified Strategy ...

  • A Mathematical Mo...

    Direct democracy, where each voter casts one vo...

  • Rating-Boosted La...

    The performance of a recommendation system reli...