Complexity of and algorithms for the manipulation of Borda, Nanson's and Baldwin's voting rules

DOI10.1016/J.ARTINT.2014.07.005zbMATH Open1408.91065OpenAlexW2052020474MaRDI QIDQ464615FDOQ464615

Authors: George Katsirelos, Nina Narodytska, Lirong Xia, Toby Walsh, Jessica Davies 

Publication date: 27 October 2014

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.artint.2014.07.005

Recommendations

• Where are the hard manipulation problems?
• When are elections with few candidates hard to manipulate?
• The computational difficulty of manipulating an election
• Is computational complexity a barrier to manipulation?
• Algorithms for the coalitional manipulation problem

zbMATH Keywords

manipulationsocial choicevoting methodsBaldwin's voting ruleBorda votingNanson's voting rule

Mathematics Subject Classification ID

Social choice (91B14) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Voting theory (91B12)

Cites Work

• Minimizing makespan in a two-machine flow shop with delays and unit-time operations is NP-hard
• A Richer Understanding of the Complexity of Election Systems
• On the reconstruction of binary and permutation matrices under (binary) tomographic constraints
• On Representatives of Subsets
• Strategy-proofness and Arrow's conditions: existence and correspondence theorems for voting procedures and social welfare functions
• Some further results on the manipulability of social choice rules
• Manipulation of Voting Schemes: A General Result
• Analysis of Several Task-Scheduling Algorithms for a Model of Multiprogramming Computer Systems
• Towards a dichotomy for the possible winner problem in elections based on scoring rules
• When are elections with few candidates hard to manipulate?
• Independence of clones as a criterion for voting rules
• Single transferable vote resists strategic voting
• How hard is it to control an election?
• The computational difficulty of manipulating an election
• Where are the hard manipulation problems?
• How hard is bribery in elections?
• Algorithms and Computation
• Incompleteness and incomparability in preference aggregation: complexity results
• Algorithms for the coalitional manipulation problem

Cited In (21)

• Studies in Computational Aspects of Voting
• Bounded incentives in manipulating the probabilistic serial rule
• Control complexity in Borda elections: solving all open cases of offline control and some cases of online control
• Exact algorithms for weighted and unweighted Borda manipulation problems
• Title not available (Why is that?)
• Complexity of shift bribery for iterative voting rules
• A Borda count for collective sentiment analysis
• New candidates welcome! Possible winners with respect to the addition of new candidates
• Manipulation can be hard in tractable voting systems even for constant-sized coalitions
• Algorithms for the coalitional manipulation problem
• Title not available (Why is that?)
• Is computational complexity a barrier to manipulation?
• Possible and necessary winner problems in iterative elections with multiple rules
• Combining voting rules together
• Distance restricted manipulation in voting
• Where are the hard manipulation problems?
• The nonmanipulative vote-deficits of voting rules
• Strategic voting in the context of stable-matching of teams
• Byzantine preferential voting
• Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey
• Complexity of conformant election manipulation

Uses Software

• Gecode

This page was built for publication: Complexity of and algorithms for the manipulation of Borda, Nanson's and Baldwin's voting rules

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