文章基本信息

标题：Recognizing Top-Monotonic Preference Profiles in Polynomial Time
本地全文：下载
作者：Krzysztof Magiera ; Piotr Faliszewski
期刊名称：Journal of Artificial Intelligence Research
印刷版ISSN：1076-9757
出版年度：2019
卷号：66
页码：57-84
出版社：American Association of Artificial
其他摘要：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.
关键词：preferences;game theory;mathematical foundations
其他关键词：preferences;game theory;mathematical foundations