Szczegóły publikacji
Opis bibliograficzny
Recognizing top-monotonic preference profiles in polynomial time / Krzysztof MAGIERA, Piotr FALISZEWSKI // W: IJCAI-17 [Dokument elektroniczny] : proceedings of the twenty-sixth International Joint Conference on Artificial Intelligence : Melbourne, Australia 19–25 August 2017 / ed. Carles Sierra. — Wersja do Windows. — Dane tekstowe. — [Melbourne] : International Joint Conferences on Artificial Intelligence, cop. 2017. — e-ISBN: 978-0-9992411-0-3. — S. 324–330. — Wymagania systemowe: Adobe Reader. — Tryb dostępu: https://www.ijcai.org/proceedings/2017/0046.pdf [2017-09-28]. — Bibliogr. s. 329–330, Abstr.
Autorzy (2)
Dane bibliometryczne
| ID BaDAP | 109088 |
|---|---|
| Data dodania do BaDAP | 2017-10-13 |
| Rok publikacji | 2017 |
| Typ publikacji | materiały konferencyjne (aut.) |
| Otwarty dostęp |  |
| Konferencja | International Joint Conference on Artificial Intelligence 2017 |
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 Barber`a 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.
