Junta distributions and the average-case complexity of manipulating elections

MaRDI QIDQ3624050zbMATH OpenFDO

Authors Ariel D. Procaccia, Jeffrey S. Rosenschein

Publication date 28 April 2009

Mathematics Subject Classification ID

Voting theory (91B12)

Recommendations

• When are elections with few candidates hard to manipulate?
• The computational difficulty of manipulating an election
• Is computational complexity a barrier to manipulation?
• Where are the hard manipulation problems?
• Complexity of manipulation with partial information in voting

Cited in

(26)

• Parameterized complexity of candidate control in elections and related digraph problems
• Manipulative elicitation -- a new attack on elections with incomplete preferences
• The complexity of probabilistic lobbying
• The computational difficulty of manipulating an election
• The opacity of backbones
• Control complexity in Bucklin and fallback voting: a theoretical analysis
• Control complexity in Bucklin and fallback voting: an experimental analysis
• On the complexity of achieving proportional representation
• Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey
• Hybrid Elections Broaden Complexity-Theoretic Resistance to Control
• Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control
• A quantitative Gobbard-Satterthwaite theorem without neutrality
• Normalized range voting broadly resists control
• Manipulation can be hard in tractable voting systems even for constant-sized coalitions
• The complexity of manipulative attacks in nearly single-peaked electorates
• Voting procedures, complexity of
• Comparing multiagent systems research in combinatorial auctions and voting
• The shield that never was: societies with single-peaked preferences are more open to manipulation and control
• Is computational complexity a barrier to manipulation?
• Collective decision making
• Guarantees for the success frequency of an algorithm for finding Dodgson-election winners
• Algorithms for the coalitional manipulation problem
• Generalized juntas and NP-hard sets
• The learnability of voting rules
• Dichotomy for voting systems
• On the complexity of bribery and manipulation in tournaments with uncertain information

This page was built for publication: Junta distributions and the average-case complexity of manipulating elections

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