Anyone but him: the complexity of precluding an alternative

DOI10.1016/j.artint.2007.01.005zbMath1168.91346OpenAlexW2570387407MaRDI QIDQ1028907

Jörg Rothe, Edith Hemaspaandra, Hemaspaandra, Lane A.

Publication date: 9 July 2009

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.artint.2007.01.005

zbMATH Keywords

computational complexity multiagent systems preference aggregation Condorcet voting approval voting plurality voting election systems computational resistance destructive control vote suppression

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Voting theory (91B12) General topics in artificial intelligence (68T01)

Related Items

Isomorphic Distances Among Elections ⋮ The Complexity of Controlling Condorcet, Fallback, and k-Veto Elections by Replacing Candidates or Voters ⋮ Algorithms for gerrymandering over graphs ⋮ Algorithms for the coalitional manipulation problem ⋮ The learnability of voting rules ⋮ The possible winner problem with uncertain weights revisited ⋮ Resolute control: forbidding candidates from winning an election is hard ⋮ Manipulation complexity of same-system runoff elections ⋮ Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control ⋮ The complexity of priced control in elections ⋮ Studies in Computational Aspects of Voting ⋮ Control of Condorcet voting: complexity and a relation-algebraic approach ⋮ Solving hard control problems in voting systems via integer programming ⋮ Often Harder than in the Constructive Case: Destructive Bribery in CP-nets ⋮ Optimal defense against election control by deleting voter groups ⋮ Prices matter for the parameterized complexity of shift bribery ⋮ The complexity of probabilistic lobbying ⋮ The control complexity of \(r\)-Approval: from the single-peaked case to the general case ⋮ Controlling weighted voting games by deleting or adding players with or without changing the quota ⋮ Normalized range voting broadly resists control ⋮ Parameterized complexity of control by voter selection in Maximin, Copeland, Borda, Bucklin, and Approval election systems ⋮ Comparing multiagent systems research in combinatorial auctions and voting ⋮ Complexity of control in judgment aggregation for uniform premise-based quota rules ⋮ Constraint-based electoral districting using a new compactness measure: an application to Portugal ⋮ Priced gerrymandering ⋮ The possible winner with uncertain weights problem ⋮ The shield that never was: societies with single-peaked preferences are more open to manipulation and control ⋮ Copeland Voting Fully Resists Constructive Control ⋮ Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey ⋮ New candidates welcome! Possible winners with respect to the addition of new candidates ⋮ On the Computational Complexity of Variants of Combinatorial Voter Control in Elections ⋮ Parameterized complexity of control problems in Maximin election ⋮ The complexity of manipulative attacks in nearly single-peaked electorates ⋮ Voting Procedures, Complexity of ⋮ Control complexity in Borda elections: solving all open cases of offline control and some cases of online control ⋮ Campaign management under approval-driven voting rules ⋮ The complexity of controlling candidate-sequential elections ⋮ Control complexity in Bucklin and fallback voting: a theoretical analysis ⋮ Control complexity in Bucklin and fallback voting: an experimental analysis ⋮ Parameterized computational complexity of Dodgson and Young elections ⋮ Sincere-Strategy Preference-Based Approval Voting Broadly Resists Control ⋮ Complexity of control by partitioning veto elections and of control by adding candidates to plurality elections ⋮ Binary linear programming solutions and non-approximability for control problems in voting systems ⋮ Mixed integer programming with convex/concave constraints: fixed-parameter tractability and applications to multicovering and voting ⋮ Hybrid Elections Broaden Complexity-Theoretic Resistance to Control ⋮ Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control ⋮ Computational Aspects of Approval Voting ⋮ Anyone but him: the complexity of precluding an alternative ⋮ Parameterized computational complexity of control problems in voting systems ⋮ Parameterized complexity of voter control in multi-peaked elections ⋮ Parameterized complexity of candidate control in elections and related digraph problems ⋮ Parameterized Complexity of Candidate Control in Elections and Related Digraph Problems ⋮ Complexity of shift bribery for iterative voting rules ⋮ Structural control in weighted voting games ⋮ Parameterized Complexity of Control and Bribery for d-Approval Elections ⋮ Combinatorial voter control in elections ⋮ Exploiting social influence to control elections based on positional scoring rules ⋮ Parameterized complexity of control and bribery for \(d\)-approval elections

Cites Work