Szczegóły publikacji
Opis bibliograficzny
Recognizing top-monotonic preference profiles in polynomial time / Krzysztof MAGIERA, Piotr FALISZEWSKI // Journal of Artificial Intelligence Research ; ISSN 1076-9757. — 2019 — vol. 66, s. 57–84. — Bibliogr. s. 82–84, Abstr. — Publikacja dostępna online od: 2019-09-04
Autorzy (2)
Dane bibliometryczne
| ID BaDAP | 126467 |
|---|---|
| Data dodania do BaDAP | 2020-01-15 |
| Tekst źródłowy | URL |
| DOI | 10.1613/jair.1.11331 |
| Rok publikacji | 2019 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Creative Commons | |
| Czasopismo/seria | Journal of Artificial Intelligence Research |
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.
