Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Decision Under Uncertainty

  • Chapter
  • First Online:
A Guided Tour of Artificial Intelligence Research

Abstract

The goal of this chapter is to provide a general introduction to decision making under uncertainty. The mathematical foundations of the most popular models used in artificial intelligence are described, notably the Expected Utility model (EU), but also new decision making models, like Rank Dependent Utility (RDU), which significantly extend the descriptive power of EU. Decision making under uncertainty naturally involves risks when decisions are made. The notion of risk is formalized as well as the attitude of agents w.r.t. risk. For this purpose, probabilities are often exploited to model uncertainties. But there exist situations in which agents do not have sufficient knowledge or data available to determine these probability distributions. In this case, more general models of uncertainty are needed and this chapter describes some of them, notably belief functions. Finally, in most artificial intelligence problems, sequences of decisions need be made and, to get an optimal sequence, decisions must not be considered separately but as a whole. We thus study at the end of this chapter models of sequential decision making under uncertainty, notably the most widely used graphical models.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 169.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Hardcover Book
USD 219.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    Outside the EU framework, the behavior of an agent cannot be rational (w.r.t. Savage’s meaning) and, therefore, it is thought in artificial intelligence that such a behavior must be proscribed. In the 70’s and 80’s, decision theorists, notably Kahneman, Tversky and Quiggin, suggested that Savage’s rationality was not the only possible form of rationality and they proposed to depart from the Savagian framework and developed their own kinds of “rationality”. This paved the way to new decision models like, e.g., RDU, that recently attracted the attention of AI researchers.

  2. 2.

    In his book, Savage did not name this operation. The term “splicing” was introduced in Gilboa (2009).

  3. 3.

    Most authors name P2 as the “sure thing principle” but it was pointed out by Peter Wakker that, in Savage’s book, the sure thing principle refers to axioms P2, P3 and P7.

  4. 4.

    Note that qualitative probabilities are slightly different from probabilities, see Kraft et al. (1959) for a proof of this assertion.

  5. 5.

    Savage’s theorem is somewhat more general than the theorem mentioned here: acts need not have a finite support, it is sufficient that the set of consequences \(\mathscr {X}\) is finite. In this case, the summation needs be substituted by an integral w.r.t. the subjective probability measure.

  6. 6.

    For an interpretation in terms of weights of agents’ coalitions or of criteria, see chapter “Multicriteria Decision Making” of this volume.

References

  • Allais M (1953) Le comportement de l’homme rationnel devant le risque: critique des postulats et axiomes de l’école américaine. Econometrica 21:503–546

    Article  MathSciNet  MATH  Google Scholar 

  • Anand P (1993) The philosophy of intransitive preference. Econ J 103(417):337–346

    Article  Google Scholar 

  • Anscombe F, Aumann R (1963) A definition of subjective probability. Ann Math Stat 34:199–205

    Article  MathSciNet  MATH  Google Scholar 

  • Argall BD, Chernova S, Veloso M, Browning B (2009) A survey of robot learning from demonstration. Robot Auton Syst 57:469–483

    Article  Google Scholar 

  • Arrow KJ (1965) Aspects of the theory of risk bearing, chapter The theory of risk aversion. Yrjo Jahnsson Fondation, pp 90–120

    Google Scholar 

  • Bellman R (1957) Dynamic programming. Princeton University Press, Princeton

    Google Scholar 

  • Bernoulli D (1738) Specimen theoriae novae de mensura sortis. Commentarii academiae scientiarum imperialis Petropolitanae 5:175–192

    Google Scholar 

  • Bleichrodt H (1996) Applications of utility theory in the economic evaluation of health care. PhD thesis, Erasmus University, Rotterdam, the Netherlands

    Google Scholar 

  • Boutilier C (1994) Towards a logic for qualitative decision theory. In: Proceedings of the international conference on principles of knowledge representation and reasoning (KR’94), pp 75–56

    Google Scholar 

  • Boutilier C (2002) A POMDP formulation of preference elicitation problems. In: Proceedings of the national conference on artificial intelligence (AAAI’02), pp 239–246

    Google Scholar 

  • Boutilier C, Regan K, Viappiani P (2010) Simultaneous elicitation of preference features and utility. In: Proceedings of the national conference on artificial intelligence (AAAI’10), pp 1160–1167

    Google Scholar 

  • Brafman RI, Tennenholtz M (1996) On the foundation of qualitative decision theory. In: Proceedings of the national conference on artificial intelligence (AAAI’96), pp 1291–1296

    Google Scholar 

  • Chajewska U, Koller D, Parr R (2000) Making rational decisions using adaptive utility elicitation. In: Proceedings of the national conference on artificial intelligence (AAAI’00), pp 363–369

    Google Scholar 

  • Chateauneuf A (1999) Comonotonicity axioms and RDU theory for arbitrary consequences. J Math Econ 32:21–45

    Article  MATH  Google Scholar 

  • Chateauneuf A, Cohen M (1994) Risk-seeking with diminishing marginal utility in a non-expected utility model. J Risk Uncertain 9:77–91

    Article  MATH  Google Scholar 

  • Chateauneuf A, Cohen M, Meilijson I (2004) Four notions of mean-preserving increase in risk, risk attitudes and applications to the rank-dependent expected utility model. J Math Econ 40(6):547–571

    Article  MathSciNet  MATH  Google Scholar 

  • Chew S, Karni E, Safra Z (1987) Risk aversion in the theory of expected utility with rank dependent preferences. J Econ Theory 42:370–381

    Article  MATH  Google Scholar 

  • Chew S, Wakker PP (1996) The comonotonic sure thing principle. J Risk Uncertain 12:5–27

    Article  MATH  Google Scholar 

  • Conati C, Gertner AS, VanLehn K, Drudzel MJ (1997) On-line student modeling for coached problem solving using Bayesian networks. In: Proceedings of the international conference on user modeling (UM’97)

    Google Scholar 

  • Dasgupta P (2006) Distributed automatic target recognition using multiagent UAV swarms. In: Proceedings of the international conference on autonomous agents and multiagent systems (AAMAS’06), pp 479–481

    Google Scholar 

  • de Salvo Braz R, Amir E, Roth D (2005) Lifted first-order probabilistic inference. In Proceedings of the international joint conference on artificial intelligence (IJCAI’05), pp 1319–1325

    Google Scholar 

  • Dempster AP (1967) Upper and lower probabilities induced by a multivalued mapping. Ann Math Stat 38:325–339

    Article  MathSciNet  MATH  Google Scholar 

  • Doucet A, Johansen A (2011) The Oxford handbook of nonlinear filtering, chapter a tutorial on particle filtering and smoothing: fifteen years later. Oxford University Press, Oxford, pp 656–704

    Google Scholar 

  • Dubois D, Fargier H, Perny P (2003) Qualitative decision theory with preference relations and comparative uncertainty: an axiomatic approach. Artif Intell J 148(1):219–260

    Article  MathSciNet  MATH  Google Scholar 

  • Dubois D, Fargier H, Perny P, Prade H (2002) Qualitative decision theory: from Savage’s axioms to nonmonotonic reasoning. Int J Assoc Comput Mach 49(4):455–495

    Article  MathSciNet  MATH  Google Scholar 

  • Dubois D, Fargier H, Prade H (1997) Decision-making under ordinal preferences and uncertainty. In: Proceedings of the conference on Uncertainty in artificial intelligence (UAI’97), pp 157–164

    Google Scholar 

  • Dubois D, Le Berre D, Prade H, Sabbadin R (1999) Using possibilistic logic for modeling qualitative decision: ATMS-based algorithms. Fund Inform 37(1–2):1–30

    MathSciNet  MATH  Google Scholar 

  • Dubois D, Prade H (1995) Possibility theory as a basis of qualitative decision theory. In: Proceedings of the international joint conference on artificial intelligence (IJCAI’95), pp 1924–1930

    Google Scholar 

  • Dubois D, Prade H, Sabbadin R (1998) Qualitative decision theory with Sugeno integrals. In: Proceedings of the conference on uncertainty in artificial intelligence (UAI’98), pp 121–128

    Google Scholar 

  • Ellsberg D (1961) Risk, ambiguity and the Savage axioms. Q J Econ 75:643–669

    Article  MathSciNet  MATH  Google Scholar 

  • Fargier H, Lang J, Sabbadin R (1998) Towards qualitative approaches to multistage decision making. Int J Approx Reason 19:441–471

    Article  MATH  Google Scholar 

  • Fishburn PC (1970) Utility theory for decision making. Wiley, New York

    Book  MATH  Google Scholar 

  • Fishburn PC (1982) The foundations of expected utility. Kluwer

    Google Scholar 

  • Fishburn PC, Roberts FS (1978) Mixture axioms in linear and multilinear utility theories. Theory Decis 9:161–171

    Article  MathSciNet  MATH  Google Scholar 

  • Franklin R, Spiegelhalter D, Macartney F, Bull K (1991) Evaluation of an algorithm for neonates. Br Med J 302:935–939

    Article  Google Scholar 

  • Getoor L, Taskar B (2007) Introduction to statistical relational learning. MIT Press, Cambridge

    Google Scholar 

  • Gilboa I (1987) Expected utility with purely subjective non-additive probabilities. J Math Econ 16:65–88

    Article  MATH  Google Scholar 

  • Gilboa I (2009) Theory of decision under uncertainty. Econometric society monographs. Cambridge University Press, Cambridge

    Book  MATH  Google Scholar 

  • Gonzales C, Perny P (2004) GAI networks for utility elicitation. In: Proceedings of the international conference on principles of knowledge representation and reasoning (KR’04), pp 224–234

    Google Scholar 

  • Herstein IN, Milnor J (1953) An axiomatic approach to measurable utility. Econometrica 21:291–297

    Article  MathSciNet  MATH  Google Scholar 

  • Horvitz E, Barry M (1995) Display of information for time-critical decision making. In: Proceedings of the conference on uncertainty in artificial intelligence (UAI’95), pp 296–305

    Google Scholar 

  • Horvitz E, Breese J, Heckerman D, Hovel D, Rommelse K (1998) The Lumière project: Bayesian user modeling for inferring the goals and needs of software users. In: Proceedings of the conference on uncertainty in artificial intelligence (UAI’98), pp 256–265

    Google Scholar 

  • Howard RA (1960) Dynamic programming and Markov processes. MIT Press, Cambridge

    Google Scholar 

  • Howard RA, Matheson JE (1984) Influence diagrams. In: Howard R, Matheson J (eds) Readings on the principles and applications of decision analysis, vol 2. Strategic Decision Group, Menlo Park, pp 719–762

    Google Scholar 

  • Hurwicz L (1951) Optimality criteria for decision making under ignorance, vol 370. Cowles Commission discussion paper, Statistics

    Google Scholar 

  • Ingersoll J (1987) Theory of financial decision making. Rowman and Littlefeld

    Google Scholar 

  • Jaffray J-Y (1988) Choice under risk and the security factor: an axiomatic model. Theory Decis 24(2):169–200

    Article  MathSciNet  MATH  Google Scholar 

  • Jaffray J-Y (1989) Linear utility theory for belief functions. Oper Res Lett 8:107–112

    Article  MathSciNet  MATH  Google Scholar 

  • Jensen F, Jensen FV, Dittmer SL (1994) From influence diagrams to junction trees. In: Proceedings of the conference on uncertainty in artificial intelligence (UAI’94)

    Google Scholar 

  • Jensen FV, Kjærulff U, Kristiansen B, Langseth H, Skaanning C, Vomlel J, Vomlelova M (2001) The SACSO methodology for troubleshooting complex systems

    Google Scholar 

  • Jensen NE (1967) An introduction to Bernoullian utility theory. I: utility functions. Swed J Econ 69:163–183

    Article  Google Scholar 

  • Kahneman D, Tversky A (1972) Subjective probability: a judgment of representativeness. Cogn Psychol 3:430–454

    Article  Google Scholar 

  • Kahneman D, Tversky A (1979) Prospect theory: an analysis of decision under risk. Econometrica 47:263–291

    Article  MathSciNet  MATH  Google Scholar 

  • Keeney RL, Raiffa H (1993)Decisions with multiple objectives - preferences and value tradeoffs. Cambridge University Press, Cambridge. (Version originale en 1976 chez Wiley)

    Google Scholar 

  • Khosravi H, Schulte O, Man T, Xu X, Bina B (2010) Structure learning for Markov logic networks with many descriptive attributes. In: Proceedings of the national conference on artificial intelligence (AAAI’10)

    Google Scholar 

  • Knight F (1921) Risk, uncertainty and profit. Houghton Miffin

    Google Scholar 

  • Kok S, Domingos P (2009) Learning Markov logic network structure via hypergraph lifting. In: Proceedings of the international conference on machine learning (ICML’09)

    Google Scholar 

  • Kraft CH, Pratt JW, Seidenberg A (1959) Intuitive probability on finite sets. Ann Math Stat 30:408–419

    Article  MathSciNet  MATH  Google Scholar 

  • Lehmann D (1996) Generalized qualitative probability: Savage revisited. In: Proceedings of the conference on uncertainty in artificial intelligence (UAI’96), pp 381–388

    Google Scholar 

  • Lu T, Boutilier C (2011) Robust approximation and incremental elicitation in voting protocols. In Proceedings of the international joint conference on artificial intelligence (IJCAI’11), pp 287–293

    Google Scholar 

  • Machina M (1982) Expected utility analysis without the independence axiom. Econometrica 50:277–323

    Article  MathSciNet  MATH  Google Scholar 

  • Monahan GE (1982) A survey of partially observable Markov decision processes: theory, models and algorithms. Manag Sci 28:1–16

    Article  MathSciNet  MATH  Google Scholar 

  • Pearl J (1988) Probabilistic reasoning in intelligent systems: networks of plausible inference. Morgan Kaufman Publishers Inc

    Google Scholar 

  • Perny P, Rolland A (2006) Reference-dependent qualitative models for decision making under uncertainty. In: Proceedings of the European conference on artificial intelligence (ECAI’06), pp 422–426

    Google Scholar 

  • Pratt J (1964) Risk aversion in the small and in the large. Econometrica 32:122–136

    Article  MATH  Google Scholar 

  • Puterman ML (1994) Markov decision processes: discrete stochastic dynamic programming. Wiley, New York

    Book  MATH  Google Scholar 

  • Quiggin J (1982) A theory of anticipated utility. J Econ Behav Organ 3:323–343

    Article  Google Scholar 

  • Quiggin J (1992) Increasing risk: another definition. In: Chikan A (ed) Progress in decision, utility and risk theory. Kluwer, Dordrecht

    Google Scholar 

  • Quiggin J (1993) Generalized expected utility theory: the rank-dependent model. Springer, Berlin

    Google Scholar 

  • Raiffa H (1968) Decision analysis: introductory lectures on choices under uncertainty. Addison-Wesley, Reading

    MATH  Google Scholar 

  • Ramsey FP (1931) Truth and probability. In: Ramsey F (ed) The foundations of mathematics and other logical essays. Harcourt, Brace and Co, California

    Google Scholar 

  • Regan K, Boutilier C (2011) Robust online optimization of reward-uncertain MDPs. In: Proceedings of the international joint conference on artificial intelligence (IJCAI’11), pp 2165–2171

    Google Scholar 

  • Rotschild M, Stiglitz J (1970) Increasing risk I: a definition. J Econ Theory 2:225–243

    Article  MathSciNet  Google Scholar 

  • Rotschild M, Stiglitz J (1971) Increasing risk II: its economic consequences. J Econ Theory 3:66–84

    Article  MathSciNet  Google Scholar 

  • Sabbadin R (1998) Une Approche Ordinale de la Décision dans l’Incertain: Axiomatisation, Représentation Logique et Application à la Décision Séquentielle. Thèse de doctorat, Université Paul Sabatier, Toulouse, France

    Google Scholar 

  • Sabbadin R (2001) Possibilistic Markov decision processes. Eng Appl Artif Intell 14:287–300

    Article  Google Scholar 

  • Savage LJ (1954) The foundations of statistics. Dover

    Google Scholar 

  • Schmeidler D (1986) Integral representation without additivity. In: Proceedings of the American mathematical society (AMS), vol 97, pp 255–261

    Google Scholar 

  • Shachter R (1986) Evaluating influence diagrams. Oper Res 34:871–882

    Article  MathSciNet  Google Scholar 

  • Shafer G (1976) Mathematical theory of evidence. Princeton University Press, Princeton

    Google Scholar 

  • Sondik E (1971) The optimal control of partially observable Markov processes. PhD thesis. Stanford University

    Google Scholar 

  • Sordoni A, Briot J-P, Alvarez I, Vasconcelos E, Irving M, Melo G (2010) Design of a participatory decision making agent architecture based on argumentation and influence function: application to a serious game about biodiversity conservation. RAIRO Oper Res 44(4):269–284

    Article  MathSciNet  MATH  Google Scholar 

  • Tan S, Pearl J (1994) Qualitative decision theory. In: Proceedings of the national conference on artificial intelligence (AAAI’94), pp 928–933

    Google Scholar 

  • von Neumann J, Morgenstern O (1944) Theory of games and economic behaviour. Princetown University Press, Princetown

    MATH  Google Scholar 

  • Wakker PP (1990) Under stochastic dominance Choquet expected utility and anticipated utility are identical. Theory Decis 29:119–132

    Article  MathSciNet  MATH  Google Scholar 

  • Wakker PP (1994) Separating marginal utility and risk aversion. Theory Decis 36:1–44

    Article  MathSciNet  MATH  Google Scholar 

  • Wald A (1950) Statistical decision functions. Wiley, New York

    MATH  Google Scholar 

  • Wang T, Boutilier C (2003) Incremental utility elicitation with the minimax regret decision criterion. In: Proceedings of the international joint conference on artificial intelligence (IJCAI’03), pp 309–316

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Aix Marseille Université, Université de Toulon, CNRS, LIS, Marseille, France

    Christophe Gonzales

  2. Sorbonne Université, CNRS, Laboratoire d’Informatique de Paris 6, LIP6, 75005, Paris, France

    Patrice Perny

Authors
  1. Christophe Gonzales
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Patrice Perny
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Christophe Gonzales .

Editor information

Editors and Affiliations

  1. CRIL-CNRS, Université d'Artois and Institut Universitaire de France, Lens, France

    Pierre Marquis

  2. Aix Marseille Université, Université de Toulon, CNRS, LIS, Marseille, France

    Odile Papini

  3. IRIT, CNRS and Université Paul Sabatier, Toulouse, France

    Henri Prade

Rights and permissions

Reprints and permissions

Copyright information

© 2020 Springer Nature Switzerland AG

About this chapter

Check for updates. Verify currency and authenticity via CrossMark

Cite this chapter

Gonzales, C., Perny, P. (2020). Decision Under Uncertainty. In: Marquis, P., Papini, O., Prade, H. (eds) A Guided Tour of Artificial Intelligence Research. Springer, Cham. https://doi.org/10.1007/978-3-030-06164-7_17

Download citation

Publish with us

Policies and ethics

Search

Navigation