Kemeny Elections with Bounded Single-peaked or Single-crossing Width
Cornaz, Denis; Galand, Lucie; Spanjaard, Olivier (2013), Kemeny Elections with Bounded Single-peaked or Single-crossing Width, Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI 2013), AAAI Press / IJCAI, p. 76-82
TypeCommunication / Conférence
Book titleProceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI 2013)
MetadataShow full item record
Abstract (EN)This paper is devoted to complexity results regarding specific measures of proximity to single-peakedness and single-crossingness, called "single-peaked width" [Cornaz et al., 2012] and "single-crossing width". Thanks to the use of the PQ-tree data structure [Booth and Lueker, 1976], we show that both problems are polynomial time solvable in the general case (while it was only known for single-peaked width and in the case of narcissistic preferences). Furthermore, we establish one of the first results (to our knowledge) concerning the effect of nearly single-peaked electorates on the complexity of an NP-hard voting system, namely we show the fixed-parameter tractability of Kemeny elections with respect to the parameters "single-peaked width" and "single-crossing width".
Subjects / KeywordsComputational Social Choice; Kemeny; Single-peaked; Single-crossing; Fixed-parameter Tractability
Showing items related by title and author.
Bidirectional versus Unidirectional Heuristic Search for Multiojective Optimization in State Space Graphs Galand, Lucie; Ismaili, Anisse; Perny, Patrice; Spanjaard, Olivier (2013) Communication / Conférence