Separating and Collapsing Electoral Control Types
Open Access
- 11 September 2024
- journal article
- Published by AI Access Foundation in Journal of Artificial Intelligence Research
- Vol. 81, 71-116
Abstract
Electoral control refers to attacking elections by adding, deleting, or partitioning voters or candidates. Hemaspaandra, Hemaspaandra, and Menton recently discovered, for seven pairs (T, T′) of seemingly distinct standard electoral control types, that T and T′ are in practice identical: For each input I and each election system E, I is a “yes” instance of both T and T′ under E, or of neither. Surprisingly, this had previously gone undetected even as the field was score-carding how many standard control types various election systems were resistant to; various “different” cells on such score cards were, unknowingly, duplicate effort on the same issue. This naturally raises the worry that perhaps other pairs of control types are identical, and so work still is being needlessly duplicated. We completely determine, for all standard control types, which pairs are, for elections whose votes are linear orderings of the candidates, always identical. In particular, we prove that no identical control pairs exist beyond the known seven. We also for three central election systems completely determine which control pairs are identical (“collapse”) with respect to those particular election systems, and we also explore containment and incomparability relationships between control pairs. For approval voting, which has a different “type” for its votes, Hemaspaandra, Hemaspaandra, and Menton’s seven collapses still hold (since we observe that their argument applies to all election systems). However, we find 14 additional collapses that hold for approval voting but do not hold for some election systems whose votes are linear orderings of the candidates. We find one new collapse for veto elections and none for plurality. We prove that each of the three election systems mentioned have no collapses other than those inherited from Hemaspaandra, Hemaspaandra, and Menton or added in the present paper. We establish many new containment relationships between separating control pairs, and for each separating pair of standard control types classify its separation in terms of either containment (always, and strict on some inputs) or incomparability. Our work, for the general case and these three important election systems, clarifies the landscape of the 44 standard control types, for each pair collapsing or separating them, and also providing finer-grained information on the separations.Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- Resolute control: Forbidding candidates from winning an election is hardTheoretical Computer Science, 2022
- Complexity of control by partitioning veto elections and of control by adding candidates to plurality electionsAnnals of Mathematics and Artificial Intelligence, 2017
- Control and Bribery in Voting2016
- Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and controlAnnals of Mathematics and Artificial Intelligence, 2015
- Control complexity in Bucklin and fallback voting: A theoretical analysisJournal of Computer and System Sciences, 2015
- Normalized Range Voting Broadly Resists ControlTheory of Computing Systems, 2012
- Computational Aspects of Approval Voting2010
- Hybrid Elections Broaden Complexity‐Theoretic Resistance to ControlMathematical Logic Quarterly, 2009
- Sincere‐Strategy Preference‐Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive ControlMathematical Logic Quarterly, 2009
- Anyone but him: The complexity of precluding an alternativeArtificial Intelligence, 2007