Hybrid Elections Broaden Complexity‐Theoretic Resistance to Control
- 17 July 2009
- journal article
- research article
- Published by Wiley in Mathematical Logic Quarterly
- Vol. 55 (4) , 397-424
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 controlKeywords
All Related Versions
This publication has 38 references indexed in Scilit:
- Sincere‐Strategy Preference‐Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive ControlMathematical Logic Quarterly, 2009
- When are elections with few candidates hard to manipulate?Journal of the ACM, 2007
- Anyone but him: The complexity of precluding an alternativeArtificial Intelligence, 2007
- The complexity of Kemeny electionsTheoretical Computer Science, 2005
- Two remarks on the power of counting2005
- Boolean operations, joins, and the extended low hierarchyTheoretical Computer Science, 1998
- Exact analysis of Dodgson electionsJournal of the ACM, 1997
- Extending Condorcet's ruleJournal of Economic Theory, 1977
- Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functionsJournal of Economic Theory, 1975
- Manipulation of Voting Schemes: A General ResultEconometrica, 1973