|
|
|
|
On the Complexity of Decision Making in Possibilistic Decision Trees
Helene Fargier, Nahla Ben Amor, Wided Guezguez
Abstract:
When the information about uncertainty cannot be quantified in a simple, probabilistic way, the topic of possibilistic decision theory is often a natural one to consider. The development of possibilistic decision theory has lead to a series of possibilistic criteria, e.g pessimistic possibilistic qualitative utility, possibilistic likely dominance , binary possibilistic utility and possibilistic Choquet integrals. This paper focuses on sequential decision making in possibilistic decision trees. It proposes a complexity study of the problem of finding an optimal strategy depending on the monotonicity property of the optimization criteria which allows the application of dynamic programming that offers a polytime reduction of the decision problem. It also shows that possibilistic Choquet integrals do not satisfy this property, and that in this case the optimization problem is NP − hard.
Keywords:
Pages: 203-210
PS Link:
PDF Link: /papers/11/p203-fargier.pdf
BibTex:
@INPROCEEDINGS{Fargier11,
AUTHOR = "Helene Fargier
and Nahla Ben Amor and Wided Guezguez",
TITLE = "On the Complexity of Decision Making in Possibilistic Decision Trees",
BOOKTITLE = "Proceedings of the Twenty-Seventh Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-11)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2011",
PAGES = "203--210"
}
|
|
