Recognizing Top-Monotonic Preference Profiles in Polynomial Time

Krzysztof Magiera, Piotr Faliszewski

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...

Figure