On the parameterized complexity of controlling amendment and successive winners

DOI10.1007/S00453-025-01304-0MaRDI QIDQ6979991zbMATH OpenFDO

Authors Yongjie Yang

Publication date 23 May 2025

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S00453-025-01304-0

zbMATH Keywords

amendment procedureelection controlFPTNP-hardnesssuccessive procedureW[1-hardness]W[2-hardness]

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27) Voting theory (91B12) History, political science (91F10)

Cites work

• A foundation for strategic agenda voting
• A threshold of ln n for approximating set cover
• Agendas in legislative decision-making
• An application of simultaneous diophantine approximation in combinatorial optimization
• Analytical approach to parallel repetition
• Anyone but him: the complexity of precluding an alternative
• Bounded single-peaked width and proportional representation
• Bypassing combinatorial protections: polynomial-time algorithms for single-peaked electorates
• Classes of directed graphs
• Complexity of control in judgment aggregation for uniform premise-based quota rules
• Complexity of strategic behavior in multi-winner elections
• Control and bribery in voting
• Control complexity in Borda elections: solving all open cases of offline control and some cases of online control
• Control in judgment aggregation
• Economics and computation. An introduction to algorithmic game theory, computational social choice, and fair division
• Elections with few voters: candidate control can be easy
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Fundamentals of parameterized complexity
• Graph-Theoretic Concepts in Computer Science
• How hard is it to control an election?
• scientific article; zbMATH DE number 3148878 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1341905 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Integer Programming with a Fixed Number of Variables
• Kernel Bounds for Disjoint Cycles and Disjoint Paths
• Kernelization lower bounds through colors and IDs
• Margin of victory for tournament solutions
• Minkowski's Convex Body Theorem and Integer Programming
• More natural models of electoral control by partition
• On the complexity of constructive control under nearly single-peaked preferences
• Parameterized algorithms
• Parameterized complexity of control by voter selection in Maximin, Copeland, Borda, Bucklin, and Approval election systems
• Parameterized computational complexity of control problems in voting systems
• Parliamentary voting procedures: agenda control, manipulation, and uncertainty
• Perfect Code is \(W[1]\)-complete
• Sequential voting and agenda manipulation
• Strong computational lower bounds via parameterized complexity
• The parameterized complexity of k-biclique

This page was built for publication: On the parameterized complexity of controlling amendment and successive winners

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