Institute for Logic, Language and Computation

21 June 2010, Computational Social Choice Seminar, Edith Elkind

Speaker: Edith Elkind
Title: Complexity of Safe Strategic Voting
Date: Monday 21 June 2010
Time: 12:00
Location: Room A1.04, Science Park 904, Amsterdam


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 diff er 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 or contact Ulle Endriss ().

The websites of the UvA make use of cookiesThis site uses cookies More informationMore info Hide this message XHide X