×

Possibilistic sequential decision making. (English) Zbl 1401.91042

Summary: 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,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.

MSC:

91B06 Decision theory
90C39 Dynamic programming
91-04 Software, source code, etc. for problems pertaining to game theory, economics, and finance
PDFBibTeX XMLCite
Full Text: DOI

References:

[2] Dubois, D.; Fargier, H.; Perny, P., Qualitative decision theory with preference relations and comparative uncertainty: An axiomatic approach, Artif. Intell., 148, 1-2, 219-260 (2003) · Zbl 1082.91512
[3] Dubois, D.; Fargier, H.; Prade, H.; Perny, P., Qualitative decision theory: from Savage’s axioms to nonmonotonic reasoning, J. ACM, 49, 455-495 (2002) · Zbl 1326.68290
[4] Dubois, D.; Godo, L.; Prade, H.; Zapico, A., Making decision in a qualitative setting: from decision under uncertainty to case-based decision, (6th International Conference on Principles of Knowledge Representation and Reasoning (KR’1998) (1998)), 594-605
[5] Dubois, D.; Prade, H., Possibility Theory, an Approach to Computerized Processing of Uncertainty (1988), Plenum Press: Plenum Press New York, NY
[6] Dubois, D.; Prade, H., Epistemic entrenchment and possibilistic logic, Artif. Intell., 50, 2, 223-239 (1991) · Zbl 0749.03019
[7] Dubois, D.; Prade, H., Possibility theory as a basis for qualitative decision theory, (International Joint Conference on Artificial Intelligence (IJCAI’95) (1995)), 1924-1930
[8] Fargier, H.; Ben Amor, N.; Guezguez, W., On the complexity of decision making in possibilistic decision trees, (Uncertainty in Artificial Intelligence (UAI’11) (2011)), 203-210
[9] Fargier, H.; Perny, P., Qualitative models for decision under uncertainty without the commensurability assumption, (Uncertainty in Artificial Intelligence (UAI’99) (1999)), 188-195
[10] Garcia, L.; Sabbadin, R., Possibilistic influence diagrams, (European Conference on Artificial Intelligence (ECAI’06) (2006)), 372-376
[11] Giang, P.; Shenoy, P. P., A comparison of axiomatic approaches to qualitative decision making using possibility theory, (Uncertainty in Artificial Intelligence (UAI’01) (2001)), 162-170
[12] Giang, P.; Shenoy, P. P., A qualitative linear utility theory for spohn’s theory of epistemic beliefs, (Uncertainty in Artificial Intelligence (UAI’2000) (2000)), 220-229
[13] Giang, P.; Shenoy, P. P., Two axiomatic approaches to decision making using possibility theory, Eur. J. Oper. Res., 162, 2, 450-467 (2005) · Zbl 1104.91022
[14] Guezguez, W.; Ben Amor, N.; Mellouli, K., Qualitative possibilistic influence diagrams based on qualitative possibilistic utilities, Eur. J. Oper. Res., 195, 1, 223-238 (2009) · Zbl 1159.91345
[15] Jeantet, G.; Spanjaard, O., Rank-dependent probability weighting in sequential decision problems under uncertainty, (International Conference on Automated Planning and Scheduling (ICAPS’08) (2008)), 148-155
[16] Jeantet, G.; Spanjaard, O., Computing rank dependent utility in graphical models for sequential decision problems, Artif. Intell., 175, 7-8, 1366-1389 (2011) · Zbl 1225.68256
[17] Kikuti, D.; Cozman, F. G.; de Campos, C. P., Partially ordered preferences in decision trees: Computing strategies with imprecision in probabilities, (IJCAI’05 Workshop on Advances in Preference Handling. IJCAI’05 Workshop on Advances in Preference Handling, Edinburgh, United Kingdom (2005)), 118-123
[18] Huntley, N.; Troffae, M. C.M., Normal form backward induction for decision trees with coherent lower previsions, Ann. Oper. Res., 195, 1, 111-134 (2012) · Zbl 1259.91039
[19] Neumann, J.; Morgenstern, O., Theory of Games and Economic Behavior (1948), Princeton University Press
[20] Pearl, J., From conditional oughts to qualitative decision theory, (Uncertainty in Artificial Intelligence (UAI’93) (1993)), 12-20
[21] Perny, P.; Spanjaard, O.; Weng, P., Algebraic Markov decision processes, (International Joint Conference on Artificial Intelligence (IJCAI’05) (2005)), 1372-1377
[22] Quiggin, J., A theory of anticipated utility, J. Econ. Behav. Organ., 3, 323-343 (1982)
[23] Raifaa, H., Decision Analysis: Introductory Lectures on Choices under Uncertainty (1968), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0181.21802
[24] Rebille, Y., Decision making over necessity measures through the Choquet integral criterion, Fuzzy Sets Syst., 157, 23, 3025-3039 (2006) · Zbl 1114.91029
[25] Sabbadin, R., A possibilistic model for qualitative sequential decision problems under uncertainty in partially observable environments, (Uncertainty in Artificial Intelligence (UAI’99) (1999)), 567-574
[26] Sabbadin, R.; Fargier, H.; Lang, J., Towards qualitative approaches to multi-stage decision making, Int. J. Approx. Reason., 19, 3-4, 441-471 (1998) · Zbl 0947.68132
[27] Schmeidler, D., Subjective probability and expected utility without additivity, Econometrica, 57, 517-587 (1989) · Zbl 0672.90011
[28] Spohn, W., A general non-probabilistic theory of inductive reasoning, (Uncertainty in Artificial Intelligence (UAI’90) (1990)), 315-322
[29] Wilson, N., An order of magnitude calculus, (Uncertainty in Artificial Intelligence (UAI’95) (1995)), 548-555
[30] Yaari, M., The dual theory of choice under risk, Econometrica, 55, 95-115 (1987) · Zbl 0616.90005
[31] Zadeh, L. A., Fuzzy sets as a basis for a theory of possibility, Fuzzy Sets Syst., 1, 3-28 (1978) · Zbl 0377.04002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.