Attacking and defending popular election systems
Lane A. Hemaspaandra, Curtis Menton · 2013
The thesis of this dissertation is that complexity and algorithms, used appropriately, are important factors in assessing the value and uses of election systems. The chapter on search versus decision points out the importance of that appropriately; it proves that unless integer factoring is easy, the standard definitions of manipulability do not capture what they were designed to capture. Other chapters use complexity and algorithms to analyze the complexity of various types of manipulative attacks on elections, as a way of understanding how computationally vulnerable election systems are. Among the contributions of those chapters are: showing that a type of range voting is the most control-attack resistant among all currently analyzed natural election systems; exploring for the first time the detailed control complexity of Schulze elections; and exploring the parameterized complexity of manipulative actions in Schulze and ranked-pairs elections. Such results will better allow choosers of election methods to match the protections of the systems they choose with the types of attack that are of greatest concern.