ML Anthology

Recognizing Top-Monotonic Preference Profiles in Polynomial Time

Krzysztof Magiera, Piotr Faliszewski
JAIR 2019 pp. 57-84
doi:10.1613/JAIR.1.11331 /jair/2019/magiera2019jair-recognizing/

Abstract

We provide the first polynomial-time algorithm for recognizing if a profile of (possibly weak) preference orders is top-monotonic. Top-monotonicity is a generalization of the notions of single-peakedness and single-crossingness, defined by Barbera and Moreno. Top-monotonic profiles always have weak Condorcet winners and satisfy a variant of the median voter theorem. Our algorithm proceeds by reducing the recognition problem to the SAT-2CNF problem.

PDF JAIR Semantic Scholar

Cite

Text

Magiera and Faliszewski. "Recognizing Top-Monotonic Preference Profiles in Polynomial Time." Journal of Artificial Intelligence Research, 2019. doi:10.1613/JAIR.1.11331

Markdown

[Magiera and Faliszewski. "Recognizing Top-Monotonic Preference Profiles in Polynomial Time." Journal of Artificial Intelligence Research, 2019.](https://mlanthology.org/jair/2019/magiera2019jair-recognizing/) doi:10.1613/JAIR.1.11331

BibTeX

@article{magiera2019jair-recognizing,
  title     = {{Recognizing Top-Monotonic Preference Profiles in Polynomial Time}},
  author    = {Magiera, Krzysztof and Faliszewski, Piotr},
  journal   = {Journal of Artificial Intelligence Research},
  year      = {2019},
  pages     = {57-84},
  doi       = {10.1613/JAIR.1.11331},
  volume    = {66},
  url       = {https://mlanthology.org/jair/2019/magiera2019jair-recognizing/}
}