Llull's Thirteenth-Century Election System Computationally Resists Bribery and Control
Lane Hemaspaandra
University of Rochester
April 24, 2008 (lunch time)
12:45-1:45
Abstract

Can computational complexity theory be used as a shield to prevent bribery and control of elections? We show that an election system developed by the 13th-century Catalan mystic Ramon Llull and the closely related Copeland election system are both resistant to all standard types of (constructive) electoral control. This is the most comprehensive resistance to control yet achieved by any natural election system whose winner problem is in polynomial time. In addition, we show that Llull and Copeland voting are broadly resistant to bribery attacks, we show how network flows can be used to find bribery attacks in certain settings, and we integrate the potential irrationality of voter preferences into many of our results.

Joint work with Piotr Faliszewski, Edith Hemaspaandra, and Joerg Rothe.

Pizza will be served before the talk.

This is the first of two talks: At 4pm Edith Hemaspaandra will give a second talk on the topic of voting.