Skip to Main content Skip to Navigation
Conference papers

Complexity Results in Optimistic/Pessimistic Preference Reasoning

Christian Bessière 1 Remi Coletta 1 Gaelle Hisler 2, 1 Anastasia Paparrizou 1
1 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Preference reasoning is a central problem in decision support. There exist various ways to interpret a set of qualitative preferences. Conditional preference logics allow to deal with semantics such as optimistic, pessimistic, strong or not. In this paper, we study the complexity of the main problems in optimistic/pessimistic preference logic: undominated, consistency and dominance. We show that they are all NP-hard in general, with some becoming polynomial under specific semantics. Our second contribution is to show that the dominance problem, which has an online component in its definition, is compilable to polynomial time.
Document type :
Conference papers
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download
Contributor : Isabelle Gouat Connect in order to contact the contributor
Submitted on : Monday, January 21, 2019 - 1:19:03 PM
Last modification on : Wednesday, October 27, 2021 - 10:25:14 AM





Christian Bessière, Remi Coletta, Gaelle Hisler, Anastasia Paparrizou. Complexity Results in Optimistic/Pessimistic Preference Reasoning. ICTAI: International Conference on Tools with Artificial Intelligence, Nov 2016, San Jose, CA, United States. pp.930-937, ⟨10.1109/ICTAI.2016.0144⟩. ⟨lirmm-01987872⟩