Anyone but him: the complexity of precluding an alternative

DOI10.1016/J.ARTINT.2007.01.005MaRDI QIDQ1028907zbMATH OpenOpenAlexFDO

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

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 complexityplurality votingmultiagent systemspreference aggregationCondorcet votingapproval votingelection systemscomputational resistancedestructive controlvote suppression

Mathematics Subject Classification ID

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

Recommendations

• Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
• When are elections with few candidates hard to manipulate?
• Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control
• The computational difficulty of manipulating an election
• The shield that never was: societies with single-peaked preferences are more open to manipulation and control

Cites work

• scientific article; zbMATH DE number 3148878 (Why is no real title available?)
• scientific article; zbMATH DE number 3854738 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2080215 (Why is no real title available?)
• scientific article; zbMATH DE number 1759396 (Why is no real title available?)
• scientific article; zbMATH DE number 2182815 (Why is no real title available?)
• A Richer Understanding of the Complexity of Election Systems
• A comparison of polynomial time reducibilities
• Anyone but him: the complexity of precluding an alternative
• Complexity of strategic behavior in multi-winner elections
• Dichotomy for voting systems
• Exact analysis of Dodgson elections
• Exact complexity of the winner problem for Young elections
• Handbook of social choice and welfare. Vol. 1.
• How hard is bribery in elections?
• How hard is it to control an election?
• Hybrid Elections Broaden Complexity-Theoretic Resistance to Control
• Single transferable vote resists strategic voting
• The complexity of Kemeny elections
• The computational difficulty of manipulating an election
• When are elections with few candidates hard to manipulate?

Cited in

(60)

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

This page was built for publication: Anyone but him: the complexity of precluding an alternative

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1028907)