Title:  "The Complexity of Llull's Thirteenth-Century Election System"

Speaker: Lane Hemaspaandra, Department of Computer Science
University of Rochester
Date: Wednesday, 17 June 2009
Time: 3pm
Place: Ross 201

Abstract:

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 (loosely, NP-hard with respect to) the
"standard" types of (constructive) electoral control.  This is the
most comprehensive resistance to control yet achieved by any natural,
preference-order-based 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, Joerg Rothe,
and (transitively ;-) ) Henning Schnoor.