A Richer Understanding of the Complexity of Election Systems

2006/09/19 by Faliszewski, Piotr, Hemaspaandra, Edith, Hemaspaandra, Lane A. +1
#Computational Complexity (cs.CC) #Computer Science and Game Theory (cs.GT) #F.1.3 #F.2.2 #FOS: Computer and information sciences #I.2.11 #Multiagent Systems (cs.MA)

paper · doi:10.48550/arxiv.cs/0609112

Abstract

We provide an overview of some recent progress on the complexity of election systems. The issues studied include the complexity of the winner, manipulation, bribery, and control problems.

Related

• How Hard Is Bribery in Elections?
• The Complexity of Online Bribery in Sequential Elections
• Manipulation Can Be Hard in Tractable Voting Systems Even for Constant-Sized Coalitions
• The Complexity of Manipulating k-Approval Elections
• Search versus Decision for Election Manipulation Problems