Abstract
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 Γ-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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
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.
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.
Clemen, R. T., & Reilly, T. (2001). Making hard decisions. Belmont: Duxbury.
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.
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.
de Finetti, B. (1974–1975). Theory of probability: a critical introductory treatment. New York: Wiley. Two volumes.
Gross, J., & Yellen, J. (1999). Graph theory and its applications. London: CRC Press.
Hammond, P. (1988). Consequentialist foundations for expected utility. Theory and Decision, 25(1), 25–78.
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).
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]
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.
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).
Jaffray, J. (1999). Rational decision making with imprecise probabilities. In 1st international symposium on imprecise probabilities and their applications (pp. 183–188).
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).
Kyburg, H. (1983). Rational belief. Behavioral and Brain Sciences, 8(2), 231–273.
LaValle, I., & Wapman, K. (1986). Rolling back decision trees requires the independence axiom! Management Science, 32(3), 382–385.
Levi, I. (1980). The enterprise of knowledge. London: MIT Press.
Lindley, D. V. (1985). Making decisions (2nd ed.). London: Wiley.
Luce, R., & Raiffa, H. (1957). Games and decisions: introduction and critical survey. New York: Wiley.
Machina, M. (1989). Dynamic consistency and non-expected utility models of choice under uncertainty. Journal of Economic Literature, 27, 1622–1688.
McClennen, E. F. (1990). Rationality and dynamic choice: foundational explorations. Cambridge: Cambridge University Press.
Miranda, E. (2008). A survey of the theory of coherent lower previsions. International Journal of Approximate Reasoning, 48(2), 628–658.
Plott, C. (1973). Path independence rationality, and social choice. Econometrica, 41(6), 1075–1091.
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.
Raiffa, H., & Schlaifer, R. (1961). Applied Statistical Decision Theory. Boston: Harvard University Press.
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.
Ray, P. (1973). Independence of irrelevant alternatives. Econometrica, 41(5), 987–991.
Ross, S. (2006). A first course in probability (7th ed.). Upper Saddle River: Pearson Prentice Hall.
Seidenfeld, T. (1988). Decision theory without ‘independence’ or without ‘ordering’: what is the difference? Economics and Philosophy, 4, 267–290.
Seidenfeld, T. (2004). A contrast between two decision rules for use with (convex) sets of probabilities: Γ-maximin versus E-admissibility. Synthese, 140, 69–88.
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).
Sen, A. K. (1977). Social choice theory: a re-examination. Econometrica, 45(1), 53–89.
Smith, C. A. B. (1961). Consistency in statistical inference and decision. Journal of the Royal Statistical Society B, 23, 1–37.
Troffaes, M. C. M. (2007). Decision making under uncertainty using imprecise probabilities. International Journal of Approximate Reasoning, 45, 17–29.
Walley, P. (1991). Statistical reasoning with imprecise probabilities. London: Chapman and Hall.
Williams, P. M. (1975). Notes on conditional previsions (Tech. rep.). School of Math. and Phys. Sci., Univ. of Sussex.
Williams, P. M. (2007). Notes on conditional previsions. International Journal of Approximate Reasoning, 44(3), 366–383.
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.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Huntley, N., Troffaes, M.C.M. Normal form backward induction for decision trees with coherent lower previsions. Ann Oper Res 195, 111–134 (2012). https://doi.org/10.1007/s10479-011-0968-2
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-011-0968-2