Parameterized computational complexity of control problems in voting systems

DOI10.1016/j.tcs.2009.04.004zbMath1164.91004OpenAlexW1990416099MaRDI QIDQ1029347

Junfeng Luan, Haodi Feng, Daming Zhu, Hong Liu

Publication date: 10 July 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.04.004

zbMATH Keywords

parameterized complexityCondorcet votingapproval votingplurality votingvoting systemsdestructive controlconstructive control

Mathematics Subject Classification ID

Voting theory (91B12)

Related Items (20)

Algorithms for gerrymandering over graphs ⋮ Resolute control: forbidding candidates from winning an election is hard ⋮ The complexity of priced control in elections ⋮ Studies in Computational Aspects of Voting ⋮ Optimal defense against election control by deleting voter groups ⋮ On the robust stability of active disturbance rejection control for SISO systems ⋮ The control complexity of \(r\)-Approval: from the single-peaked case to the general case ⋮ Normalized range voting broadly resists control ⋮ Parameterized complexity of control by voter selection in Maximin, Copeland, Borda, Bucklin, and Approval election systems ⋮ Constraint-based electoral districting using a new compactness measure: an application to Portugal ⋮ Tuning of sampled-data ADRC for nonlinear uncertain systems ⋮ Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey ⋮ On the Computational Complexity of Variants of Combinatorial Voter Control in Elections ⋮ Parameterized complexity of control problems in Maximin election ⋮ Multivariate complexity analysis of Swap Bribery ⋮ Control complexity in Bucklin and fallback voting: a theoretical analysis ⋮ Multivariate Complexity Analysis of Swap Bribery ⋮ A parameterized perspective on protecting elections ⋮ Parameterized complexity of voter control in multi-peaked elections ⋮ Combinatorial voter control in elections

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Anyone but him: the complexity of precluding an alternative
• How hard is it to control an election?
• Perfect Code is \(W[1\)-complete]
• The computational difficulty of manipulating an election
• Handbook of social choice and welfare. Vol. 1.
• Parametrized complexity theory.
• Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control
• Copeland Voting Fully Resists Constructive Control
• When are elections with few candidates hard to manipulate?
• Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
• How Hard Is Bribery in Elections?
• Parameterized Complexity of Candidate Control in Elections and Related Digraph Problems

This page was built for publication: Parameterized computational complexity of control problems in voting systems