×

Sequential decision making with partially ordered preferences. (English) Zbl 1231.91073

Summary: This paper presents new insights and novel algorithms for strategy selection in sequential decision making with partially ordered preferences; that is, where some strategies may be incomparable with respect to expected utility. We assume that incomparability amongst strategies is caused by indeterminacy/imprecision in probability values. We investigate six criteria for consequentialist strategy selection: \(\varGamma \)-maximin, \(\varGamma \)-maximax, \(\varGamma \)-maximix, interval dominance, maximality and E-admissibility. We focus on the popular decision tree and influence diagram representations. Algorithms resort to linear/multilinear programming; we describe implementation and experiments.

MSC:

91B06 Decision theory
06A06 Partial orders, general
90C90 Applications of mathematical programming

Software:

CP-nets
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Allais, M.; Hagen, O., Expected Utility Hypotheses and the Allais Paradox (1979), D. Reidel Publishing Company: D. Reidel Publishing Company Dordrecht, Holland · Zbl 0468.90002
[2] Aumann, R. J., Utility theory without the completeness axiom, Econometrica, 30, 3, 445-461 (July 1962)
[3] Berger, J. O., Statistical Decision Theory and Bayesian Analysis (1985), Springer: Springer New York · Zbl 0572.62008
[4] Bertsimas, D.; Tsitsiklis, J. N., Introduction to Linear Optimization (1997), Athena Scientific: Athena Scientific Belmont, Massachusetts
[5] Blume, L.; Brandeburger, A.; Dekel, E., Lexicographic probabilities and choice under uncertainty, Econometrica, 59, 1, 61-79 (January 1991)
[6] B. Bonet, R. Givan, in: 5th International Planning Competition: Non-deterministic Track, call for participation, 2005.; B. Bonet, R. Givan, in: 5th International Planning Competition: Non-deterministic Track, call for participation, 2005.
[7] Boutilier, C.; Brafman, R. I.; Hoos, H. H.; Poole, D., CP-nets: A tool for representing and reasoning with conditional ceteris paribus preference statements, Journal of Artificial Intelligence Research, 21, 135-191 (2004) · Zbl 1080.68685
[8] Breese, J.; Fertig, K., Decision making with interval influence diagrams, (Sixth Conference on Uncertainty in Artificial Intelligence (1990), Elsevier Science: Elsevier Science New York), 122-129
[9] Bykvist, K., Time-partial morality and dynamic choice, (Rabinowicz, W., Value and Choice - Some Common Themes in Decision Theory and Moral Philosophy, Lund Philosophy Reports (2000)), 53-64
[10] G.F. Cooper, A method for using belief networks as influence diagrams, in: Proceedings of the 4th Conference on Uncertainty in Artificial Intelligence, Minneapolis, 1988, pp. 55-63.; G.F. Cooper, A method for using belief networks as influence diagrams, in: Proceedings of the 4th Conference on Uncertainty in Artificial Intelligence, Minneapolis, 1988, pp. 55-63.
[11] Couso, I.; Moral, S.; Walley, P., A survey of concepts of independence for imprecise probabilities, Risk, Decision and Policy, 5, 2, 165-181 (2000)
[12] Cozman, F. G., Separation properties of sets of probabilities, (Boutilier, C.; Goldszmidt, M., Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence (July 2000), Morgan Kaufmann: Morgan Kaufmann San Francisco), 107-115
[13] Cozman, F. G., Graphical models for imprecise probabilities, International Journal of Approximate Reasoning, 39, 2-3, 167-184 (June 2005)
[14] Danielson, M.; Ekenberg, L., Computing upper and lower bounds in interval decision trees, European Journal of Operational Research, 181, 2, 808-816 (September 2007)
[15] Danielson, M.; Ekenberg, L.; Johansson, J.; Larsson, A., The DecideIT decision tool, (Bernard, J.-M.; Seidenfeld, T.; Zaffalon, M., Proceedings of the 3rd International Symposium on Imprecise Probabilities and Their Applications (July 2003), Carleton Scientific: Carleton Scientific Lugano, Switzerland), 204-217
[16] de Campos, C. P.; Cozman, F. G., Inference in credal networks using multilinear programming, (Proceedings of the 2nd European Starting AI Researcher Symposium (August 2004), IOS Press: IOS Press Valencia, Spain), 50-61
[17] de Campos, C. P.; Cozman, F. G., The inferential complexity of Bayesian and credal networks, (Proceedings of the 9th International Joint Conference on Artificial Intelligence (July-August 2005), Edinburgh: Edinburgh Scotland, UK), 1313-1318
[18] C.P. de Campos, F.G. Cozman, Inference in credal networks through integer programming, in: International Symposium on Imprecise Probability: Theories and Applications, Prague, 2007, pp. 145-154.; C.P. de Campos, F.G. Cozman, Inference in credal networks through integer programming, in: International Symposium on Imprecise Probability: Theories and Applications, Prague, 2007, pp. 145-154.
[19] C.P. de Campos, Q. Ji, Strategy selection in influence diagrams using imprecise probabilities, in: Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence, Helsinki, Finland, July 2008, pp. 121-128.; C.P. de Campos, Q. Ji, Strategy selection in influence diagrams using imprecise probabilities, in: Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence, Helsinki, Finland, July 2008, pp. 121-128.
[20] Ellsberg, D., Risk, ambiguity, and the Savage axioms, The Quarterly Journal of Economics, 75, 4, 643-669 (1961) · Zbl 1280.91045
[21] Etchart, N., Adequate moods for Non-EU decision making in a sequential framework, Theory and Decision, 52, 1-28 (February 2002)
[22] Fertig, K.; Breese, J., Probability intervals over influence diagrams, IEEE Transactions on Pattern Analysis and Machine Intelligence, 15, 3, 280-286 (1993)
[23] Fishburn, P. C., Utility Theory for Decision Making (1970), Kriefer Publishing Company: Kriefer Publishing Company New York · Zbl 0213.46202
[24] Georgakopoulos, G.; Kavvadias, D.; Papadimitriou, C. H., Probabilistic satisfiability, Journal of Complexity, 4, 1, 1-11 (March 1988)
[25] Gilboa, I.; Schmeidler, D., Maxmin expected utility with non-unique prior, Journal of Mathematical Economics, 18, 2, 141-153 (1989) · Zbl 0675.90012
[26] Giron, F. J.; Rios, S., Quasi-Bayesian Behaviour: A More Realistic Approach to Decision Making? (1980), University Press: University Press Valencia · Zbl 0459.62006
[27] Hailperin, T., Best possible inequalities for the probability of a logical function of events, American Mathematical Monthly, 72, 343-359 (1965) · Zbl 0132.13706
[28] Hammond, P. J., Changing tastes and coherent dynamic choice, The Review of Economic Studies, 43, 1, 159-173 (1976) · Zbl 0367.90011
[29] P.J. Hammond, Consequentialism and the independence axiom, in: B.R. Munier (Ed.), Risk, Decision and Rationality (Proceedings of the 3rd International Conference on the Foundations and Applications of Utility, Risk and Decision Theories), Dordrecht, Holland, 1988, pp. 503-516.; P.J. Hammond, Consequentialism and the independence axiom, in: B.R. Munier (Ed.), Risk, Decision and Rationality (Proceedings of the 3rd International Conference on the Foundations and Applications of Utility, Risk and Decision Theories), Dordrecht, Holland, 1988, pp. 503-516. · Zbl 0667.90006
[30] Hammond, P. J., Orderly decision theory: a comment on Professor Seidenfeld, Economics and Philosophy, 4, 272-297 (1988)
[31] P. Hansen, B. Jaumard, Probabilistic satisfiability, Tech. Rep. G-96-31, Les Cahiers du GERAD, École Polytechique de Montréal, 1996.; P. Hansen, B. Jaumard, Probabilistic satisfiability, Tech. Rep. G-96-31, Les Cahiers du GERAD, École Polytechique de Montréal, 1996. · Zbl 1015.68198
[32] Hansen, P.; Perron, S., Merging the local and global approaches to probabilistic satisfiability, International Journal of Approximate Reasoning, 47, 2, 125-140 (2008) · Zbl 1343.68220
[33] Harmanec, D., Generalizing Markov decision processes to imprecise probabilities, Journal of Statistical Planning and Inference, 105, 1, 199-213 (June 2002)
[34] Howard, R. A.; Matheson, J. E., Influence diagrams, Decision Analysis, 2, 3, 127-143 (2005)
[35] N. Huntley, M. Troffaes, An efficient normal form solution to decision trees with lower previsions, in: International Workshop on Soft Methods in Probability and Statistics, 2008, pp. 419-426.; N. Huntley, M. Troffaes, An efficient normal form solution to decision trees with lower previsions, in: International Workshop on Soft Methods in Probability and Statistics, 2008, pp. 419-426.
[36] L. Hurwicz, A class of criteria for decision-making under ignorance, Cowles Comission Paper 356, 1951.; L. Hurwicz, A class of criteria for decision-making under ignorance, Cowles Comission Paper 356, 1951.
[37] Itoh, H.; Nakamura, K., Partially observable Markov decision processes with imprecise parameters, Artificial Intelligence, 171, 8-9, 453-490 (2007) · Zbl 1168.68578
[38] J.-Y. Jaffray, Rational decision making with imprecise probabilities, in: G.D. Cooman, F.G. Cozman, S. Moral, P. Walley (Eds.), Proceedings of the 1st International Symposium on Imprecise Probabilities and Their Applications, Ghent, Belgium, June 1999, pp. 183-188.; J.-Y. Jaffray, Rational decision making with imprecise probabilities, in: G.D. Cooman, F.G. Cozman, S. Moral, P. Walley (Eds.), Proceedings of the 1st International Symposium on Imprecise Probabilities and Their Applications, Ghent, Belgium, June 1999, pp. 183-188.
[39] Jaumard, B.; Hansen, P.; de Aragão, M. P., Column generation methods for probabilistic logic, ORSA Journal on Computing, 3, 2, 135-148 (1991) · Zbl 0800.68864
[40] Kahneman, D.; Tversky, A., Prospect theory: An analysis of decisions under risk, Econometrica, 47, 262-291 (1979) · Zbl 0411.90012
[41] D. Kikuti, F.G. Cozman, Influence diagrams with partially ordered preferences, in: 3rd Multidisciplinary Workshop on Advances in Preference Handling, 2007.; D. Kikuti, F.G. Cozman, Influence diagrams with partially ordered preferences, in: 3rd Multidisciplinary Workshop on Advances in Preference Handling, 2007.
[42] Kikuti, D.; Cozman, F. G.; de Campos, C. P., Partially ordered preferences in decision trees: Computing strategies with imprecision in probabilities, (Workshop on Advances in Preference Handling (July 2005), Edinburgh: Edinburgh United Kingdom), 118-123
[43] Kyburg, H. E.; Pittarelli, M., Set-based Bayesianism, IEEE Transactions on Systems, Man and Cybernetics, Part A, 26, 3, 324-339 (1996)
[44] Lauritzen, S. L.; Nilsson, D., Representing and solving decision problems with limited information, Management Science, 47, 9, 1235-1251 (2001) · Zbl 1232.90343
[45] Levi, I., On indeterminate probabilities, The Journal of Philosophy, 71, 391-418 (1974)
[46] Levi, I., The Enterprise of Knowledge (1980), The MIT Press: The MIT Press Massachusetts
[47] Luce, R. D.; Raiffa, H., Games and Decisions (1957), Wiley: Wiley New York · Zbl 0084.15704
[48] Luo, C.; Yu, C.; Lobo, J.; Wang, G.; Pham, T., Computation of best bounds of probabilities from uncertain data, Computational Intelligence, 12, 4, 541-566 (1996)
[49] Machina, M. J., Dynamic consistency and non-expected utility models of choice under uncertainty, Journal of Economic Literature, 27, 4, 1622-1688 (December 1989)
[50] McClennen, E. F., Rationality and Dynamic Choice: Foundational Explorations (1990), Cambridge University Press: Cambridge University Press Cambridge
[51] McClennen, E. F., Pragmatic rationality and rules, Philosophy and Public Affairs, 26, 3, 210-258 (1997)
[52] T.D. Nielsen, J.-Y. Jaffray, An operational approach to rational decision making based on rank dependent utility, 2001, unpublished manuscript available on http://www.cs.aau.dk/ tdn/papers/nielsen-jaffray-01.pdf; T.D. Nielsen, J.-Y. Jaffray, An operational approach to rational decision making based on rank dependent utility, 2001, unpublished manuscript available on http://www.cs.aau.dk/ tdn/papers/nielsen-jaffray-01.pdf
[53] Nielsen, T. D.; Jensen, F. V., Welldefined decision scenarios, (Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence (July 1999), Morgan Kaufmann: Morgan Kaufmann Stockholm, Sweden), 502-511
[54] Pearl, J., Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference (1988), Morgan Kaufmann Publishers: Morgan Kaufmann Publishers Los Altos, CA
[55] Quiggin, J. C., A theory of anticipated utility, Journal of Economic Behavior & Organization, 3, 4, 323-343 (December 1982)
[56] Raiffa, H., Decision Analysis: Introductory Lectures on Choices under Uncertainty (1968), Addison-Wesley: Addison-Wesley Massachusetts · Zbl 0181.21802
[57] Samuelson, P. A., Consumption theory in terms of revealed preference, Econometrica, 15, 243-253 (1948)
[58] Satia, J. K.; Lave, R. E., Markovian decision processes with uncertain transition probabilities, Operations Research, 21, 3, 728-740 (May-June 1973)
[59] M.J. Schervish, T. Seidenfeld, J.B. Kadane, I. Levi, Extensions of expected utility theory and some limitations of pairwise comparisons, in: Proceedings of the 3rd International Symposium on Imprecise Probabilities and Their Applications, Lugano, Switzerland, July 2003, pp. 496-510.; M.J. Schervish, T. Seidenfeld, J.B. Kadane, I. Levi, Extensions of expected utility theory and some limitations of pairwise comparisons, in: Proceedings of the 3rd International Symposium on Imprecise Probabilities and Their Applications, Lugano, Switzerland, July 2003, pp. 496-510.
[60] Seidenfeld, T., A contrast between two decision rules for use with (convex) sets of probabilities: \(Γ\)-Maximin versus E-Admissibility, Synthese, 140, 1-2, 69-88 (May 2004)
[61] Seidenfeld, T.; Schervish, M. J.; Kadane, J. B., Decisions without ordering, (Sieg, W., Acting and Reflecting (1990), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht), 143-170
[62] Seidenfeld, T.; Schervish, M. J.; Kadane, J. B., A representation of partially ordered preferences, Annals of Statistics, 23, 6, 2168-2217 (December 1995)
[63] Shachter, R., Bayes-Ball: the rational pastime (for determining irrelevance and requisite information in belief networks and influence diagrams), (Proceedings of the 14th Annual Conference on Uncertainty in Artificial Intelligence (UAI-98) (1998), Morgan Kaufmann: Morgan Kaufmann San Francisco, CA), 480-487
[64] Shachter, R., Efficient value of information computation, (Proceedings of the 15th Annual Conference on Uncertainty in Artificial Intelligence (UAI-99) (1999), Morgan Kaufmann: Morgan Kaufmann San Francisco, CA), 594-601
[65] Sherali, H. D.; Tuncbilek, C. H., A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique, Journal of Global Optimization, 2, 1, 101-112 (March 1992)
[66] Simon, H. A., A behavioral model of rational choice, The Quarterly Journal of Economics, 69, 1, 99-118 (1955)
[67] Strotz, R., Myopia and inconsistency in dynamic utility maximization, The Review of Economic Studies, 23, 3, 165-180 (1956)
[68] Tatman, J. A.; Shachter, R. D., Dynamic programming and influence diagrams, IEEE Transactions on Systems, Man and Cybernetics, 20, 2, 365-379 (1990) · Zbl 0715.90094
[69] F.W. Trevizan, F.G. Cozman, L.N. de Barros, Planning under risk and Knightian uncertainty, in: International Joint Conference on Artificial Intelligence, 2007, pp. 2023-2028.; F.W. Trevizan, F.G. Cozman, L.N. de Barros, Planning under risk and Knightian uncertainty, in: International Joint Conference on Artificial Intelligence, 2007, pp. 2023-2028.
[70] M.C.M. Troffaes, Decision making with imprecise probabilities: A short review, in: F. Cozman (Ed.), Society for Imprecise Probability Theory and Applications Newsletter, Manno, Switzerland, December 2004, pp. 4-7.; M.C.M. Troffaes, Decision making with imprecise probabilities: A short review, in: F. Cozman (Ed.), Society for Imprecise Probability Theory and Applications Newsletter, Manno, Switzerland, December 2004, pp. 4-7.
[71] Troffaes, M. C.M., Decision making under uncertainty using imprecise probabilities, International Journal of Approximate Reasoning, 45, 1, 17-29 (2007) · Zbl 1119.91028
[72] L.V. Utkin, T. Augustin, Powerful algorithms for decision making under partial prior information and general ambiguity attitudes, in: Proceedings of the 4th International Symposium on Imprecise Probabilities and Their Applications, Pittsburgh, Pennsylvania, July 2005, pp. 349-358.; L.V. Utkin, T. Augustin, Powerful algorithms for decision making under partial prior information and general ambiguity attitudes, in: Proceedings of the 4th International Symposium on Imprecise Probabilities and Their Applications, Pittsburgh, Pennsylvania, July 2005, pp. 349-358.
[73] Walley, P., Statistical Reasoning with Imprecise Probabilities (1991), Chapman and Hall: Chapman and Hall London · Zbl 0732.62004
[74] White, C. C.; El-Deib, H. K., Markov decision processes with imprecise transition probabilities, Operations Research, 42, 4, 739-749 (July-August 1994)
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.