Typical-Case Challenges to Complexity Shields That Are Supposed to Protect Elections Against Manipulation and Control: A Survey.
Jörg Rothe, Lena Schend · ISAIM · 2012
In the context of voting, manipulation and control refer to attempts to influence the outcome of elections by either setting some of the votes strategically (i.e., by reporting untruthful preferences) or by altering the structure of elections via adding, deleting, or partitioning either candidates or voters. Since by the celebrated Gibbard–Satterthwaite theorem (and other results expanding its scope) all reasonable voting systems are manipulable in principle and since many voting systems are in principle susceptible to many control types modeling natural control scenarios, much work has been done to use computational complexity as a shield to protect elections against manipulation and control. However, most of this work has yielded NP-hardness results, showing that certain voting systems resist certain types of manipulation or control only in the worst case. The typical case, where votes are given according to some natural distribution, poses a serious challenge to such worst-case complexity results and is frequently open to successful manipulation or control attempts, despite the NP-hardness of the corresponding problems. We survey some recent results on typical-case challenges to worst-case complexity results for manipulation and control.