Qualitative decision theory: from savage's axioms to nonmonotonic reasoning

ABSTRACT

This paper investigates to what extent a purely symbolic approach to decision making under uncertainty is possible, in the scope of artificial intelligence. Contrary to classical approaches to decision theory, we try to rank acts without resorting to any numerical representation of utility or uncertainty, and without using any scale on which both uncertainty and preference could be mapped. Our approach is a variant of Savage's where the setting is finite, and the strict preference on acts is a partial order. It is shown that although many axioms of Savage theory are preserved and despite the intuitive appeal of the ordinal method for constructing a preference over acts, the approach is inconsistent with a probabilistic representation of uncertainty. The latter leads to the kind of paradoxes encountered in the theory of voting. It is shown that the assumption of ordinal invariance enforces a qualitative decision procedure that presupposes a comparative possibility representation of uncertainty, originally due to Lewis, and usual in nonmonotonic reasoning. Our axiomatic investigation thus provides decision-theoretic foundations to the preferential inference of Lehmann and colleagues. However, the obtained decision rules are sometimes either not very decisive or may lead to overconfident decisions, although their basic principles look sound. This paper points out some limitations of purely ordinal approaches to Savage-like decision making under uncertainty, in perfect analogy with similar difficulties in voting theory.

REFERENCES

• 1: Adams, E. W. 1975. The Logic of Conditionals. D. Reidel, Dordrecht, The Netherlands.
• 2: Arrow, K. 1951. Social Choice and Individual Values. Wiley, New York.
• 3: Arrow, K., and Hurwicz, L. 1972. An optimality criterion for decision-making under ignorance. In Uncertainty and Expectations in Economics, C. F. Carter and J. L. Ford, Eds. Basil Blackwell & Mott Ltd., Oxford, England.
• 4: Bacchus, F., and Grove, A. 1996. Utility independence in a qualitative decision theory. In Proceedings of the 5th International Conference on Principles of Knowledge Representation and Reasoning (KR'96, Cambridge, Mass.). pp. 542--552.
• 5: Salem Benferhat , Didier Dubois , Henri Prade, Nonmonotonic reasoning, conditional objects and possibility theory, Artificial Intelligence, v.92 n.1-2, p.259-276, May 1997 [doi>10.1016/S0004-3702(97)00012-X]
• 6: Benferhat, B., Dubois, D., Prade, H. 1999. Possibilistic and standard probabilistic semantics of conditional knowledge bases. J. Logic Comput. 9, 873--895.
• 7: Boutilier, C. 1994. Towards a logic for qualitative decision theory. In Proceedings of the 4th International Conference on Principles of Knowledge Representation and Reasoning (KR'94, Bonn, Germany, May 24--27). pp. 75--86.
• 8: Brafman, R. I., Tennenholtz, M. 1996. On the foundations of qualitative utility theory. In Proceedings of the 13th National Conference on Artificial Intelligence (AAAI-96, Portland, Ore.). pp. 1291--1296.
• 9: Ronen I. Brafman , Moshe Tennenholtz, Modeling agents as qualitative decision makers, Artificial Intelligence, v.94 n.1-2, p.217-268, July 1997 [doi>10.1016/S0004-3702(97)00024-6]
• 10: Ronen I. Brafman , Moshe Tennenholtz, An axiomatic treatment of three qualitative decision criteria, Journal of the ACM (JACM), v.47 n.3, p.452-482, May 2000 [doi>10.1145/337244.337251]
• 11: Stefan Brass, Deduction with Supernormal Defaults, Proceedings of the Second International Workshop on Nonmonotonic and Inductive Logic, p.153-174, December 02-06, 1991
• 12: Brewka, G. 1989. Preferred subtheories: an extended logical framework for default reasoning. In Proceedings of the 11th International Joint Conference on Artificial Intelligence (IJCAI'89, Detroit, Micho., Aug. 20--25). pp. 1043--1048.
• 13: Claudette Cayrol , Véronique Royer , Claire Saurel, Management of Preferences in Assumption-Based Reasoning, Proceedings of the 4th International Conference on Processing and Management of Uncertainty in Knowledge-Based Systems: Advanced Methods in Artificial Intelligence, p.13-22, July 06-10, 1992
• 14: Cohen, M., and Jaffray, J.-Y. 1980. Rational behavior under complete ignorance. Econometrica, 48, 1280--1299.
• 15: Condorcet, M. J. 1785. Essai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix. Imprimerie Royale, Paris, France.
• 16: James P. Delgrande, A preference-based approach to default reasoning: preliminary report, Proceedings of the twelfth national conference on Artificial intelligence (vol. 2), p.902-908, October 1994, Seattle, Washington, United States
• 17: Doyle, J., and Thomason, R. 1999. Background to qualitative decision theory. AI Mag. 20, 2 (Summer), 55--68.
• 18: Jon Doyle , Michael P. Wellman, Impediments to universal preference-based default theories, Artificial Intelligence, v.49 n.1-3, p.97-128, May 1991 [doi>10.1016/0004-3702(91)90007-7]
• 19: D Dubois, Belief structures, possibility theory and decomposable confidence measures on finite sets, Computers and Artificial Intelligence, v.5 n.5, p.403-416, Oct. 1986
• 20: Dubois, D., Fargier, H., and Prade, H. 1997. Decision making under ordinal preferences and uncertainty. In Proceedings of the 13th Conference on Uncertainty in Artificial Intelligence (Providence, R.I.), D. Geiger and P. P. Shenoy, Eds. Morgan Kaufmann, San Francisco, Calif., pp. 157--164. Full paper Report IRIT/9803, Toulouse, France.
• 21: Dubois, D., Fargier, H., and Prade, H. 1998. Comparative uncertainty, belief functions and accepted beliefs. In Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence (Madison, Wisc.), G. Cooper and S. Moral, Eds. Morgan Kaufmann, San Francisco, Calif., pp. 113--120.
• 22: Dubois, D., Fargier, H., Perny, P., and Prade, H. 2001a. A characterization of generalized concordance rules in multicriteria decision-making. In Proceedings of EUROFUSE Workshop on Preference Modelling and Applications (Granada, Spain, April 25--27, 2001). pp. 121--129. To appear in Int. J. Intell. Syst.
• 23: Dubois, D., Fargier, H., and Perny, P. 2002. Qualitative models for decision under uncertainty: an axiomatic approach. To appear J. Art Intell.
• 24: Dubois, D., and Prade, H. 1988. Possibility Theory---An Approach to the Computerized Processing of Uncertainty. Plenum Press, New York.
• 25: Didier Dubois , Henri Prade, Epistemic entrenchment and possibilistic logic, Artificial Intelligence, v.50 n.2, p.223-239, July 1991 [doi>10.1016/0004-3702(91)90101-O]
• 26: Dubois, D., and Prade, H. 1994. Conditional objects as nonmonotonic consequence relations. IEEE Trans. on Systems, Man Cybernet. 24, 1724--1740.
• 27: Didier Dubois , Henri Prade, Conditional objects, possibility theory and default rules, Conditionals: from philosophy to computer science, Oxford University Press, Oxford, 1996
• 28: Dubois, D., and Prade, H. 1995b. Numerical representation of acceptance. In Proceedings of the 11th Conference on Uncertainty in Artificial Intelligence (Montréal, P.Q., Canada, Aug.). pp. 149--156.
• 29: Dubois, D., and Prade, H. 1995c. Possibility theory as a basis for qualitative decision theory. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI'95, Montréal, P.Q., Canada, Aug.). pp. 1924--1930.
• 30: Dubois, D., and Prade, H. 1998. Possibility theory: qualitative and quantitative aspects. In Handbook on Defeasible Reasoning and Uncertainty Management Systems---Volume 1: Quantified Representation of Uncertainty and Imprecision, P. Smets, Ed. Kluwer Academic, Dordrecht, The Netherlands, pp. 169--226.
• 31: Dubois, D., Prade H., and Sabbadin, R. 2001b. Decision-theoretic foundations of possibility theory. European J. Operat. Res. 128, 459--478.
• 32: Fargier, H., and Perny, P. 1999. Qualitative models for decision under uncertainty without the commensurability assumption. In Proceedings of the 15th Conference on Uncertainty in Artificial Intelligence (Providence, R.I.), K. Laskey and H. Prade, Eds. Morgan Kaufmann, San Francisco, Calif., pp. 157--164.
• 33: Fishburn, P. 1975. Axioms for lexicographic preferences. Rev. Econom. Stud. 42, pp. 415--419.
• 34: Fishburn, P. 1986. The axioms of subjective probabilities. Stat. Sci. 1, 335--358.
• 35: Friedman, N., and Halpern, J. 1996. Plausibility measures and default reasoning. In Proceedings of the 13th National Conference on Artificial Intelligence (AAAI'96, Portland, Ore.). pp. 1297--1304. To appear in J. Assoc. Comp. Mach.
• 36: Gärdenfors, P. 1988. Knowledge in Flux. MIT Press, Cambridge, Mass.
• 37: Geffner, H. 1992. High probabilities, model preference and default arguments, Mind Mach. 2, 51--70.
• 38: Grant, S. Kajii, A., and Polak, B. 2000. Decomposable choice under uncertainty, J. Econ. Theory 92, 169--197.
• 39: Grove, A. 1988. Two modellings for theory change. J. Philos. Logic 17, 157--170.
• 40: Halpern, J. 1997. Defining relative likelihood in partially-ordered preferential structures. J. AI Res. 7, 1--24.
• 41: Hurwicz, L. 1951. Optimality criteria for decision making under ignorance. Cowles Commission discussion paper, statistics H 370 mimeographed.
• 42: Jaffray, J.-Y. 1989. Linear utility theory for belief functions. Op. Res. Lett. 8, 107--112.
• 43: Sarit Kraus , Daniel Lehmann , Menachem Magidor, Nonmonotonic reasoning, preferential models and cumulative logics, Artificial Intelligence, v.44 n.1-2, p.167-207, July 1990 [doi>10.1016/0004-3702(90)90101-5]
• 44: Lang, J. 1996. Conditional desires and utilities: an alternative logical approach to qualitative decision theory. In Proceedings of the 12th European Conference on Artificial Intelligence (ECAI'96, Budapest, Hungary). pp. 318--322.
• 45: Lehmann, D. 1996. Generalized qualitative probability: Savage revisited. In Proceedings of the 12th Conference on Uncertainty in Artificial Intelligence (Portland, Ore., Aug.). Morgan Kaufman, San Mateo, Calif., pp. 381--388.
• 46: Daniel Lehmann , Menachem Magidor, What does a conditional knowledge base entail?, Artificial Intelligence, v.55 n.1, p.1-60, May 1992 [doi>10.1016/0004-3702(92)90041-U]
• 47: Lewis, D. 1973. Counterfactuals. Basil Blackwell, London, England.
• 48: Mas-Colell, A., and Sonnenschein, H. F. 1972. General possibility theorems for group decisions. Rev. Econ. Stud. 39, 185--192.
• 49: Moulin, H. 1988. Axioms of Cooperative Decision Making. Cambridge University Press, Cambridge, England.
• 50: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 51: Roubens, M., and Vincke, P. 1985. Preference Modelling. Lecture Notes in Economics and Mathematical Systems, vol. 250. Springer Verlag, Berlin, Germany.
• 52: Sabbadin, R. 2000. Empirical comparison of probabilistic and possibilistic Markov decision processes algorithms. In Proceedings of the 14th European Conference on Artificial Intelligence (ECAI'00, Berlin, Germany). pp. 586--590.
• 53: Savage, L. J. 1972. The Foundations of Statistics. Dover, New York.
• 54: Schmeidler, D. 1989. Subjective probability and expected utility without additivity. Econometrica, 57, 571--587.
• 55: Sen, A. K. 1986. Social choice theory. In Handbook of Mathematical Economics, K. Arrow, and M. D. Intrilligator, Eds. Elsevier, Amsterdam, The Netherlands, Chap. 22, pp. 1173--1181.
• 56: Paul Snow, The emergence of ordered belief from initial ignorance, Proceedings of the twelfth national conference on Artificial intelligence (vol. 1), p.281-286, October 1994, Seattle, Washington, United States
• 57: Paul Snow, Diverse confidence levels in a probabilistic semantics for conditional logics, Artificial Intelligence, v.113 n.1-2, p.269-279, Sept. 1999 [doi>10.1016/S0004-3702(99)00054-5]
• 58: Sek-Wah Tan , Judea Pearl, Qualitative decision theory, Proceedings of the twelfth national conference on Artificial intelligence (vol. 2), p.928-933, October 1994, Seattle, Washington, United States
• 59: Thomason, R. 2000. Desires and defaults: a framework for planning with inferred goals. In Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning (KR'00, Breckenridge, Co., Morgan Kaufmann, San Francisco, Calif, pp. 702--713.
• 60: Von Neumann, J., and Morgenstern, O. 1944. Theory of Games and Economic Behavior, Princeton University Press, Princeton, N.J., revised edition in 1953.
• 61: Wald, A. 1950. Statistical Decision Functions. Wiley, New York.
• 62: Weymark, J. A. 1984. Arrow's theorem with social quasi-orderings. Pub. Choice 42, 235--246.
• 63: Zadeh, L. A. 1978. Fuzzy sets as a basis for a theory of possibility. Fuzzy Sets Syst. 1, 3--28.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Nonmonotonic reasoning and belief revision

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Uncertainty, "fuzzy," and probabilistic reasoning

General Terms:
Theory, Verification

Keywords:
Comparative uncertainty, decision theory, nonmonotonic reasoning, possibility theory, preference relations, qualitative decision theory