This paper will appear in Proceedings of IJCAI ’11 and be presented at the conference in Barcelona in July.

Abstract: Slinko and White have recently introduced a new model of coalitional
manipulation of voting rules under limited communication, which they
call {em safe strategic voting}. The computational aspects of this
model were first studied by Hazon and Elkind, 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 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.