The Complexity of Safe Manipulation under Scoring Rules

摘要

[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.