Monday, April 08, 2013
12:00 PM
CBS Room 703
Curtis Menton
University of Rochester
Attacking and Defending Popular Election Systems
The theme of this talk, and dissertation, is that complexity and algorithms,
used appropriately, are important factors in assessing the value and
uses of election systems. This thesis's work on search versus decision
points out the importance of that "appropriately" by proving that
unless integer factoring is easy, the standard definitions of
manipulability do not capture what they were designed to capture.
Other work in this thesis uses 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 that other work 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.