The Complexity of Safe Manipulation under Scoring Rules

Ianovski, Egor; Yu, Lan; Elkind, Edith; Wilson, Mark C.

doi:10.5591/978-1-57735-516-8/IJCAI11-052

The Complexity of Safe Manipulation under Scoring Rules

Egor Ianovski, Lan Yu, Edith Elkind, Mark C. Wilson

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 246-250.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-052

Abstract

Slinko and White, (2008) have recently introduced a new model of coalitional manipulation of voting rules under limited communication, which they call safe strategic voting. The computational aspects of this model were first studied by Hazon and Elkind, (2010), who provide polynomial-time algorithms for finding a safe strategic vote under k-approval and the Bucklin rule. In this paper, we answer an open question of Hazon and Elkind, (2010) by presenting a polynomial-time algorithm for finding a safe strategic vote under the Borda rule. Our results for Borda generalize to several interesting classes of scoring rules.

Egor Ianovski, Lan Yu, Edith Elkind, and Mark C. Wilson. 2011. The Complexity of Safe Manipulation under Scoring Rules. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 246–250. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-052

@inproceedings{ijcai2011p52,
  title     = {The Complexity of Safe Manipulation under Scoring Rules},
  author    = {Ianovski, Egor and Yu, Lan and Elkind, Edith and Wilson, Mark C.},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {246--250},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-052},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-052},
}

TY  - CPAPER
TI  - The Complexity of Safe Manipulation under Scoring Rules
AU  - Ianovski, Egor
AU  - Yu, Lan
AU  - Elkind, Edith
AU  - Wilson, Mark C.
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 246
EP  - 250
DO  - 10.5591/978-1-57735-516-8/IJCAI11-052
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-052
ER  -