21 June 2010, Computational Social Choice Seminar, Edith Elkind

Abstract

We investigate the computational aspects of safe manipulation, a new model of coalitional manipulation that was recently put forward by Slinko and White. In this model, a potential manipulator V announces how he intends to vote, and some of the other voters whose preferences coincide with those of V may follow suit. Depending on the number of followers, the outcome could be better or worse for V than the outcome of truthful voting. A manipulative vote is called safe if for some number of followers it improves the outcome from V's perspective, and can never lead to a worse outcome. We will discuss the complexity of finding a safe manipulative vote for a number of common voting rules, including Plurality, Borda, k-approval, and Bucklin. We provide both algorithms and hardness results, demonstrating that the complexity of our problem depends both on the voters' weights and the structural properties of the tie-breaking rule. We also investigate the possibility of extending the notion of safe manipulation to the setting where the followers' preferences may differ from those of the leader, and study the computational properties of the resulting extensions.

Based on joint work with Noam Hazon.

For more information, see http://www.illc.uva.nl/~ulle/seminar/ or contact Ulle Endriss (ulle.endriss at uva.nl).