Title:  "The Shield that Never Was: Societies with Single-Peaked Preferences
are More Open to Manipulation and Control"

Speaker: Edith Hemaspaandra, Rochester Institute of Technology
Date: Wednesday, 24 June 2009
Time: 3pm
Place: Ross 201

Abstract:

Much work has been devoted, during the past twenty years, to using
complexity to protect elections from manipulation and control.  Many
results have been obtained showing NP-hardness shields, and recently
there has been much focus on whether such worst-case hardness
protections can be bypassed by frequently correct heuristics or by
approximations.  Our work takes a very different approach: We argue
that when electorates follow the canonical political science model of
societal preferences the complexity shield never existed in the first
place.  In particular, we show that for electorates having
single-peaked preferences, many existing NP-hardness results on
manipulation and control evaporate.

Joint work with Piotr Faliszewski, Lane A. Hemaspaandra, and Joerg Rothe