Hybrid Elections Broaden Complexity-Theoretic Resistance to Control

✍ Scribed by Edith Hemaspaandra; Lane A. Hemaspaandra; Jörg Rothe

• Publisher: John Wiley and Sons
• Year: 2009
• Tongue: English
• Weight: 248 KB
• Volume: 55
• Category: Article
• ISSN: 0044-3050
• DOI: 10.1002/malq.200810019

✦ Synopsis

Abstract

Electoral control refers to attempts by an election's organizer (“the chair”) to influence the outcome by adding/deleting/partitioning voters or candidates. The important paper of Bartholdi, Tovey, and Trick [1] that introduces (constructive) control proposes 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.

We introduce and study a method of combining two or more candidate‐anonymous election schemes in such a way that the combined scheme possesses all the resistances to control (i.e., all the NP‐hardnesses of control) possessed by any of its constituents: It combines their strengths. From this and new resistance constructions, we prove for the first time that there exists a neutral, anonymous election scheme (whose winner problem is computable in polynomial time) that is resistant to all twenty standard types of electoral control (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)