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

DOI10.1016/j.artint.2014.07.005zbMath1408.91065OpenAlexW2052020474MaRDI QIDQ464615

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

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

zbMATH Keywords

social choicemanipulationvoting methodsBaldwin's voting ruleBorda votingNanson's voting rule

Mathematics Subject Classification ID

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

Related Items (13)

A Borda count for collective sentiment analysis ⋮ Studies in Computational Aspects of Voting ⋮ Byzantine preferential voting ⋮ Strategic voting in the context of stable-matching of teams ⋮ Bounded incentives in manipulating the probabilistic serial rule ⋮ Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey ⋮ 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 ⋮ Is computational complexity a barrier to manipulation? ⋮ Distance restricted manipulation in voting ⋮ 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 ⋮ Complexity of shift bribery for iterative voting rules

Uses Software

• Gecode

Cites Work

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

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