Algorithms and Elections

The VCLA and WPI hosted a talk by Gábor Erdélyi on June 12, 2014.

ABSTRACT

This talk aims to provide a general overview of the computational aspects of elections. Its main focus will be on the complexity of problems that model various ways of tampering with the outcome of an election, such as manipulation, control, and bribery. Each of these actions are very different in nature: while manipulation concerns the insincere behavior on the part of one or several voters, in control settings the election's chair seeks to change the outcome of an election by making structural changes in the election such as adding/deleting/partitioning either candidates or voters, and finally, bribery is given if an external agent attempts to change one or several voters' votes. These manipulative actions will be examined in the context of several voting systems, with one example being fallback voting, proposed by Brams and Sanver (2006), which - being computationally resistant to 20 of the 22 common types of control - is the system currently known to display the broadest resistance to control among all natural voting systems with an easy winner determination procedure.