Speaker: Toby Walsh
Affiliation: UNSW and NICTA (Australia)
Title: Where are the really hard manipulation problems?
Date: Wednesday, 18 Mar 2009
Time: 4:00 pm
Location: Building 303, Room 279 (CS seminar room)

Voting is a simple mechanism to aggregate the preferences of agents. Many voting rules have been shown to be NP-hard to manipulate. However, a number of recent theoretical results have suggested that this is only a worst-case complexity, and manipulation may be easy in practice. In this talk, I show that empirical studies are useful in improving our understanding of this issue. I demonstrate that there is a smooth transition in the probability that a coalition can manipulate the result and elect a desired candidate as the size of the manipulating coalition is varied. I argue that for many independent and identically distributed votes, manipulation will be computationally easy even when the coalition of manipulators is critical in size.