Parameterized complexity of control problems in Maximin election

DOI10.1016/J.IPL.2010.03.006MaRDI QIDQ656582zbMATH OpenOpenAlexFDO

Authors Hong Liu, Daming Zhu

Publication date 18 January 2012

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2010.03.006

zbMATH Keywords

\(W[1\)-hard]\(W[2\)-hard]computational complexitycontrolfixed parameter tractabilityMaximin election

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Social choice (91B14)

Recommendations

• Parameterized complexity of control by voter selection in Maximin, Copeland, Borda, Bucklin, and Approval election systems
• Elections with few voters: candidate control can be easy
• Parameterized Complexity of Candidate Control in Elections and Related Digraph Problems
• Parameterized computational complexity of control problems in voting systems
• The Last Voting Rule Is Home: Complexity of Control by Partition of Candidates or Voters in Maximin Elections

Cites work

• Anyone but him: the complexity of precluding an alternative
• Complexity of strategic behavior in multi-winner elections
• Copeland Voting Fully Resists Constructive Control
• How hard is bribery in elections?
• How hard is it to control an election?
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
• Multimode control attacks on elections
• On complexity of lobbying in multiple referenda
• Parameterized complexity of candidate control in elections and related digraph problems
• Parameterized computational complexity of control problems in voting systems
• Parametrized complexity theory.
• Perfect Code is \(W[1]\)-complete
• Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control
• The Complexity of Probabilistic Lobbying
• The computational difficulty of manipulating an election
• When are elections with few candidates hard to manipulate?

Cited in

(21)

• Parameterized computational complexity of control problems in voting systems
• Optimal defense against election control by deleting voter groups
• A parameterized perspective on protecting elections
• Resolute control: forbidding candidates from winning an election is hard
• Control complexity in Bucklin and fallback voting: a theoretical analysis
• On the parameterized complexity of party nominations
• Parameterized complexity of voter control in multi-peaked elections
• Combinatorial voter control in elections
• Parameterized complexity of control and bribery for \(d\)-approval elections
• The control complexity of \(r\)-Approval: from the single-peaked case to the general case
• Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey
• Parameterized complexity of control and bribery for \(d\)-approval elections
• Studies in Computational Aspects of Voting
• On the computational complexity of variants of combinatorial voter control in elections
• Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control
• The complexity of priced control in elections
• Normalized range voting broadly resists control
• Parameterized complexity of control by voter selection in Maximin, Copeland, Borda, Bucklin, and Approval election systems
• Elections with few voters: candidate control can be easy
• The Last Voting Rule Is Home: Complexity of Control by Partition of Candidates or Voters in Maximin Elections
• Parameterized Complexity of Candidate Control in Elections and Related Digraph Problems

This page was built for publication: Parameterized complexity of control problems in Maximin election

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