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 metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01987872
Contributor : Isabelle Gouat <>
Submitted on : Monday, January 21, 2019 - 1:19:03 PM
Last modification on : Thursday, May 14, 2020 - 6:58:06 PM

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

97

Files downloads

87