×

zbMATH — the first resource for mathematics

Normal form backward induction for decision trees with coherent lower previsions. (English) Zbl 1259.91039
Summary: We examine normal form solutions of decision trees under typical choice functions induced by lower previsions. For large trees, finding such solutions is hard as very many strategies must be considered. In an earlier paper, we extended backward induction to arbitrary choice functions, yielding far more efficient solutions, and we identified simple necessary and sufficient conditions for this to work. In this paper, we show that backward induction works for maximality and E-admissibility, but not for interval dominance and \(\Gamma\)-maximin. We also show that, in some situations, a computationally cheap approximation of a choice function can be used, even if the approximation violates the conditions for backward induction; for instance, interval dominance with backward induction will yield at least all maximal normal form solutions.

MSC:
91B06 Decision theory
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Augustin, T. (2001). On decision making under ambiguous prior and sampling information. In G. de Cooman, T. Fine, S. Moral, T. Seidenfeld (eds.), ISIPTA01: proceedings of the second international symposium on imprecise probabilities.
[2] Boole, G. (1854). An investigation of the laws of thought on which are founded the mathematical theories of logic and probabilities. London: Walton and Maberly. · Zbl 1205.03003
[3] Clemen, R. T., & Reilly, T. (2001). Making hard decisions. Belmont: Duxbury.
[4] de Condorcet, M. (1785). Essai sur l’Application de l’Analyse à la Probabilité des Décisions Rendues à la Pluralité des Voix. Paris: L’Imprimerie Royale.
[5] De Cooman, G., & Troffaes, M. C. M. (2005). Dynamic programming for deterministic discrete-time systems with uncertain gain. International Journal of Approximate Reasoning, 39(2–3), 257–278. · Zbl 1090.90194
[6] de Finetti, B. (1974–1975). Theory of probability: a critical introductory treatment. New York: Wiley. Two volumes. · Zbl 0328.60002
[7] Gross, J., & Yellen, J. (1999). Graph theory and its applications. London: CRC Press. · Zbl 0920.05001
[8] Hammond, P. (1988). Consequentialist foundations for expected utility. Theory and Decision, 25(1), 25–78. · Zbl 0645.90002
[9] Harmanec, D. (1999). A generalization of the concept of Markov decision process to imprecise probabilities. In 1st international symposium on imprecise probabilities and their applications (pp. 175–182).
[10] Huntley, N., & Troffaes, M. C. M. (2011) Subtree perfectness, backward induction, and normal-extensive form equivalence for single agent sequential decision making under arbitrary choice functions. arXiv: 1109.3607v1 [math.ST]
[11] Huntley, N., & Troffaes, M. C. M. (2008). An efficient normal form solution to decision trees with lower previsions. In D. Dubois, M. A. Lubiano, H. Prade, M. A. Gil, P. Grzegorzewski, O. Hryniewicz (eds.), Soft methods for handling variability and imprecision, advances in soft computing (pp. 419–426). Berlin: Springer.
[12] Huntley, N., & Troffaes, M. C. M. (2009). Characterizing factuality in normal form sequential decision making. In T. Augustin, F. P. A. Coolen, S. Moral, M. C. M. Troffaes (eds.), ISIPTA’09: proceedings of the sixth international symposium on imprecise probability: theories and applications (pp. 239–248).
[13] Jaffray, J. (1999). Rational decision making with imprecise probabilities. In 1st international symposium on imprecise probabilities and their applications (pp. 183–188).
[14] Kikuti, D., Cozman, F., & de Campos, C. (2005). Partially ordered preferences in decision trees: computing strategies with imprecision in probabilities. In R. Brafman, U. Junker (eds.), IJCAI-05 multidisciplinary workshop on advances in preference handling (pp. 118–123).
[15] Kyburg, H. (1983). Rational belief. Behavioral and Brain Sciences, 8(2), 231–273.
[16] LaValle, I., & Wapman, K. (1986). Rolling back decision trees requires the independence axiom! Management Science, 32(3), 382–385.
[17] Levi, I. (1980). The enterprise of knowledge. London: MIT Press.
[18] Lindley, D. V. (1985). Making decisions (2nd ed.). London: Wiley.
[19] Luce, R., & Raiffa, H. (1957). Games and decisions: introduction and critical survey. New York: Wiley. · Zbl 0084.15704
[20] Machina, M. (1989). Dynamic consistency and non-expected utility models of choice under uncertainty. Journal of Economic Literature, 27, 1622–1688.
[21] McClennen, E. F. (1990). Rationality and dynamic choice: foundational explorations. Cambridge: Cambridge University Press.
[22] Miranda, E. (2008). A survey of the theory of coherent lower previsions. International Journal of Approximate Reasoning, 48(2), 628–658. · Zbl 1184.68519
[23] Plott, C. (1973). Path independence rationality, and social choice. Econometrica, 41(6), 1075–1091. · Zbl 0297.90017
[24] Radner, R., & Marschak, J. (1954). Note on some proposed decision criteria. In R. M. Thrall, C. H. Coombs, R. L. Davies (eds.), Decision processes (pp. 61–68). New York: Wiley. · Zbl 0058.13703
[25] Raiffa, H., & Schlaifer, R. (1961). Applied Statistical Decision Theory. Boston: Harvard University Press. · Zbl 0952.62008
[26] Ramsey, F. P. (1931). Truth and probability. In R. B. Braithwaite (ed.), Foundations of mathematics and other logical essays (pp. 156–198). London: Routledge and Kegan Paul (Chap. VII) Published posthumously.
[27] Ray, P. (1973). Independence of irrelevant alternatives. Econometrica, 41(5), 987–991. · Zbl 0286.92007
[28] Ross, S. (2006). A first course in probability (7th ed.). Upper Saddle River: Pearson Prentice Hall.
[29] Seidenfeld, T. (1988). Decision theory without ’independence’ or without ’ordering’: what is the difference? Economics and Philosophy, 4, 267–290.
[30] Seidenfeld, T. (2004). A contrast between two decision rules for use with (convex) sets of probabilities: {\(\Gamma\)}-maximin versus E-admissibility. Synthese, 140, 69–88.
[31] Seidenfeld, T., Schervish, M. J., & Kadane, J. B. (2007). Coherent choice functions under uncertainty. In 5th international symposium on imprecise probability: theories and applications (pp. 385–394). · Zbl 1183.91037
[32] Sen, A. K. (1977). Social choice theory: a re-examination. Econometrica, 45(1), 53–89. · Zbl 0353.90001
[33] Smith, C. A. B. (1961). Consistency in statistical inference and decision. Journal of the Royal Statistical Society B, 23, 1–37. · Zbl 0124.09603
[34] Troffaes, M. C. M. (2007). Decision making under uncertainty using imprecise probabilities. International Journal of Approximate Reasoning, 45, 17–29. · Zbl 1119.91028
[35] Walley, P. (1991). Statistical reasoning with imprecise probabilities. London: Chapman and Hall. · Zbl 0732.62004
[36] Williams, P. M. (1975). Notes on conditional previsions (Tech. rep.). School of Math. and Phys. Sci., Univ. of Sussex.
[37] Williams, P. M. (2007). Notes on conditional previsions. International Journal of Approximate Reasoning, 44(3), 366–383. · Zbl 1114.60005
[38] Zaffalon, M., Wesnes, K., & Petrini, O. (2003). Reliable diagnoses of dementia by the naive credal classifier inferred from incomplete cognitive data. Artificial Intelligence in Medicine, 29(1–2), 61–79. · Zbl 05391206
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.