Recognizing Top-Monotonic Preference Profiles in Polynomial Time
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.
Cite
Text
Magiera and Faliszewski. "Recognizing Top-Monotonic Preference Profiles in Polynomial Time." International Joint Conference on Artificial Intelligence, 2017. doi:10.24963/IJCAI.2017/46Markdown
[Magiera and Faliszewski. "Recognizing Top-Monotonic Preference Profiles in Polynomial Time." International Joint Conference on Artificial Intelligence, 2017.](https://mlanthology.org/ijcai/2017/magiera2017ijcai-recognizing/) doi:10.24963/IJCAI.2017/46BibTeX
@inproceedings{magiera2017ijcai-recognizing,
title = {{Recognizing Top-Monotonic Preference Profiles in Polynomial Time}},
author = {Magiera, Krzysztof and Faliszewski, Piotr},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2017},
pages = {324-330},
doi = {10.24963/IJCAI.2017/46},
url = {https://mlanthology.org/ijcai/2017/magiera2017ijcai-recognizing/}
}