Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):
M. Lackner:
"Incomplete Preferences in Single-Peaked Electorates";
Vortrag: Twenty-Eighth AAAI Conference on Aritifical Intelligence (AAAI 2014),
Québec City, Québec, Canada;
27.07.2014
- 31.07.2014; in: "Proceedings of the Twenty-Eighth AAAI Conference on Aritifical Intelligence",
C. Brodley, P. Stone (Hrg.);
(2014),
ISBN: 978-1-57735-661-5;
S. 742
- 748.
Kurzfassung englisch:
Incomplete preferences are likely to arise in real-world preference aggregation and voting systems. This paper deals with determining whether an incomplete preference profile is single-peaked. This is essential information since many intractable voting problems become tractable for single-peaked profiles. We prove that for incomplete profiles the problem of determining single-peakedness is NP-complete. Despite this computational hardness result, we find four polynomial-time algorithms for reasonably restricted settings.
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.