Kemeny Elections with Bounded Single-Peaked or Single-Crossing Width

Cornaz, Denis; Galand, Lucie; Spanjaard, Olivier

Kemeny Elections with Bounded Single-Peaked or Single-Crossing Width

Denis Cornaz, Lucie Galand, Olivier Spanjaard

Download BibTeX Cite

Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 76-81.

Abstract

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.

Denis Cornaz, Lucie Galand, and Olivier Spanjaard. 2013. Kemeny Elections with Bounded Single-Peaked or Single-Crossing Width. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13. IJCAI, 76–81. https://ijcai.org/proceedings/2013/23

@inproceedings{ijcai2013p23,
  title     = {Kemeny Elections with Bounded Single-Peaked or Single-Crossing Width},
  author    = {Cornaz, Denis and Galand, Lucie and Spanjaard, Olivier},
  booktitle = {Proceedings of the Twenty-Third International Joint Conference on
               Artificial Intelligence, {IJCAI-13}},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  editor    = {Francesca Rossi},
  pages     = {76--81},
  year      = {2013},
  month     = {8},
  url       = {https://ijcai.org/proceedings/2013/23},
}

TY  - CPAPER
TI  - Kemeny Elections with Bounded Single-Peaked or Single-Crossing Width
AU  - Cornaz, Denis
AU  - Galand, Lucie
AU  - Spanjaard, Olivier
T2  - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13
PB  - AAAI Press / International Joint Conferences on Artificial Intelligence
PY  - 2013
SP  - 76
EP  - 81
UR  - https://ijcai.org/proceedings/2013/23
ER  -