Speaker: Piotr Faliszewski
Affiliation: AGH University of Science and Technology, Krakow
Title: The Complexity of Campaign Management: Swap Bribery
Date: 6 May 2010
Location: MLT3 (Building 303)
Abstract: In voting theory, bribery is a form of manipulative behavior in which an external actor (the briber) offers to pay the voters to change their votes in order to get her preferred candidate elected. While bribery is typically associated with cheating in elections, its mathematical model can also be interpreted in terms of campaign management. In this work we study a model of bribery which is particularly well-suited for this campaign-management interpretation. Namely, we consider a model where the price of each vote depends on the amount of change that the voter is asked to implement and we focus on situations where the only allowed action is to shift the briber’s (campaign manager’s) preferred candidate forward on voters’ preference lists. We provide hardness results and polynomial time (approximate) algorithms for this type of bribery in many prominent voting rules.