Complexity Results in Optimistic/Pessimistic Preference Reasoning - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2016

Complexity Results in Optimistic/Pessimistic Preference Reasoning


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.


Logic [math.LO]
Fichier principal
Vignette du fichier
ictai16.pdf (264.95 Ko) Télécharger le fichier
SlidesIctai.pdf (2.61 Mo) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-01987872 , version 1 (21-01-2019)



Christian Bessiere, 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⟩
125 View
147 Download



Gmail Mastodon Facebook X LinkedIn More