OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Possibilistic sequential decision making

Ben Amor, Nahla and Fargier, Hélène and Guezguez, Wided Possibilistic sequential decision making. (2014) International Journal of Approximate Reasoning, 55 (5). 1269-1300. ISSN 0888-613X

(Document in English)

PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: http://dx.doi.org/10.1016/j.ijar.2013.11.005


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 the proposition a series of possibilistic criteria, namely: optimistic and pessimistic possibilistic qualitative criteria [7], possibilistic likely dominance [2] and [9], binary possibilistic utility [11] and possibilistic Choquet integrals [24]. This paper focuses on sequential decision making in possibilistic decision trees. It proposes a theoretical study on the complexity of the problem of finding an optimal strategy depending on the monotonicity property of the optimization criteria – when the criterion is transitive, this property indeed allows a polytime solving of the problem by Dynamic Programming. We show that most possibilistic decision criteria, but possibilistic Choquet integrals, satisfy monotonicity and that the corresponding optimization problems can be solved in polynomial time by Dynamic Programming. Concerning the possibilistic likely dominance criteria which is quasi-transitive but not fully transitive, we propose an extended version of Dynamic Programming which remains polynomial in the size of the decision tree. We also show that for the particular case of possibilistic Choquet integrals, the problem of finding an optimal strategy is NP-hard. It can be solved by a Branch and Bound algorithm. Experiments show that even not necessarily optimal, the strategies built by Dynamic Programming are generally very good.

Item Type:Article
Additional Information:Thanks to Elsevier editor. The definitive version is available at http://www.sciencedirect.com The original PDF of the article can be found at Thermochimica Acta website : http://www.sciencedirect.com/science/article/pii/S0888613X13002831
HAL Id:hal-01118468
Audience (journal):International peer-reviewed journal
Uncontrolled Keywords:
Institution:French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UT3 (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Other partners > Université de Carthage (TUNISIA)
Laboratory name:
Deposited On:19 Feb 2015 09:59

Repository Staff Only: item control page