Paper Info
Title
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.
Year
DOI
Venue
2017
10.1613/jair.1.11331
JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH
Field
DocType
Volume
Monotonic function,Discrete mathematics,Computer science,Time complexity
Conference
66
Issue
ISSN
Citations 
1
1076-9757
1
PageRank 
References 
Authors
0.35
0
2
Name
Order
Citations
PageRank
Krzysztof Magiera171.56
Piotr Faliszewski2139594.15