Abstract
Decision trees are useful graphical representations of sequential decision problems. We consider decision trees where events are assigned imprecise probabilities, and examine their normal form decisions; that is, scenarios in which the subject initially decides all his future choices. We present a backward induction method for efficiently finding the set of optimal normal form decisions under maximality. Our algorithm is similar to traditional backward induction for solving extensive forms in that we solve smaller subtrees first, however it is different in that solutions of subtrees are only used as intermediate steps to reach the full solution more efficiently—in particular, under maximality, a decision that is optimal in a subtree can be potentially absent in any optimal policy in the full tree.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Boole, G.: An Investigation of the Laws of Thought on Which Are Founded the Mathematical Theories of Logic and Probabilities. Walton and Maberly, London (1854)
Clemen, R.T., Reilly, T.: Making Hard Decisions. Duxbury Press, Belmont (2001)
Jaffray, J.: Rational decision making with imprecise probabilities. In: Proceedings of 1st International Symposium on Imprecise Probabilities and Their Applications, pp. 183–188 (1999)
Kikuti, D., Cozman, F., de Campos, C.P.: Partially ordered preferences in decision trees: Computing strategies with imprecision in probabilities. In: Proceedings of Multidisciplinary Workshop on Advances in Preference Handling (IJCAI-05, Edinburgh, UK), pp. 118–123 (2005)
Lindley, D.V.: Making Decisions, 2nd edn. Wiley, London (1985)
Raiffa, H., Schlaifer, R.: Applied Statistical Decision Theory. Division of Research, Graduate School of Business Administration. Harvard University, Boston (1961)
Seidenfeld, T.: A contrast between two decision rules for use with (convex) sets of probabilities: Γ-maximin versus E-admissibility. Synthese 140, 69–88 (2004)
Von Neumann, J., Morgenstern, O.: Theory of Games and Economic Behavior. Princeton University Press, Princeton (1953)
Walley, P.: Statistical Reasoning with Imprecise Probabilities. Chapman and Hall, London (1991)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Huntley, N., Troffaes, M.C.M. (2008). An Efficient Normal Form Solution to Decision Trees with Lower Previsions. In: Dubois, D., Lubiano, M.A., Prade, H., Gil, M.Á., Grzegorzewski, P., Hryniewicz, O. (eds) Soft Methods for Handling Variability and Imprecision. Advances in Soft Computing, vol 48. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-85027-4_50
Download citation
DOI: https://doi.org/10.1007/978-3-540-85027-4_50
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-85026-7
Online ISBN: 978-3-540-85027-4
eBook Packages: EngineeringEngineering (R0)