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.