The Complexity of Online Bribery in Sequential Elections

Lane A. Hemaspaandra

University of Rochester

No prior knowledge of computational social choice or computational complexity will be required to understand this talk. The talk will start with an overview of and illustrations of election systems and some approaches to attacking them.

One central type of electoral attack is bribery. Prior work on the complexity of bribery assumes that the bribery happens simultaneously, and that the briber has full knowledge of all votes. However, in many real-world settings votes come in sequentially, and the briber may have a use-it-or-lose-it moment to decide whether to alter a given vote, and when making that decision the briber may not know what votes the remaining voters will cast.

We introduce a model for, and initiate the study of, bribery in such an online, sequential setting. We show that even for election systems whose winner-determination problem is easily (in the jargon, "polynomial-time") computable, an online, sequential setting may vastly increase the complexity of bribery, jumping the problem up to being levels that are thought to be extremely difficult (in the jargon, completeness for high levels of the polynomial hierarchy and even PSPACE). But we also show that for some natural, important election systems, such a dramatic complexity increase does not occur, and we pinpoint the complexity of their bribery problems.

This is joint work with Edith Hemaspaandra and Joerg Rothe.