Monday, September 17, 2007
11:00 AM
Computer Science Bldg. Room 209
Prof. Joerg Rothe
Heinrich-Heine-Universitaet Duesseldorf
On Hybrid Elections and Approximating Optimal Weighted Lobbying
Two issues related to computational aspects of voting are presented. The first part of the talk is concerned with electoral control, which refers to attempts by an election's organizer ("the chair") to influence the outcome by adding/deleting/partitioning voters or candidates. Bartholdi, Tovey, and Trick proposed computational complexity as a means of resisting control attempts: Look for election systems where the chair's task in seeking control is itself computationally infeasible. In the talk, a method of combining two or more election systems is presented such that the combined (or "hybrid") system possesses all the resistances to control possessed by any of its constituents: It combines their strengths. This and new resistance constructions have yielded the first election system that is resistant to all twenty standard types of electoral control. The second part of the talk is concerned with the Optimal Weighted Lobbying Problem. In particular, an efficient greedy algorithm is presented that achieves a logarithmic approximation ratio for this hard problem.

Joint work with Edith Hemaspaandra, Lane Hemaspaandra, Gabor Erdelyi, and Holger Spakowski. Results presented at IJCAI-2007 and FCT-2007.