Recognizing Top-Monotonic Preference Profiles in Polynomial Time
Lists
Only you see this
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.
BibTeX
@inproceedings{magiera2017recognizing,
author = {Krzysztof Magiera and Piotr Faliszewski},
title = {{Recognizing Top-Monotonic Preference Profiles in Polynomial Time}},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2017},
doi = {10.24963/ijcai.2017/46},
}Loading related content...