An axiomatic treatment of three qualitative decision criteria

ABSTRACT

The need for computationally efficient decision-making techniques together with the desire to simplify the processes of knowledge acquisition and agent specification have led various researchers in artificial intelligence to examine qualitative decision tools. However, the adequacy of such tools is not clear. This paper investigates the foundations of maximin, minmax regret, and competitive ratio, three central qualitative decision criteria, by characterizing those behaviors that could result from their use. This characterizaton provides two important insights: (1)under what conditions can we employ an agent model based on these basic qualitative decision criteria, and (2) how “rational” are these decision procedures. For the competitive ratio criterion in particular, this latter issue is of central importance to our understanding of current work on on-line algorithms. Our main result is a constructive representation theorem that uses two choice axioms to characterize maximin, minmax regret, and competitive ratio.

REFERENCES

• 1: ALLEN, J., HENDLER, J., AND TATE, A., EDS. 1990. Readings in Planning. Morgan-Kaufmann, San Francisco, Calif.
• 2: ANSCOMBE, F. J., AND AUMANN, R.J. 1963. A definition of subjective probability. Ann. Math. Stat. 34, 199-205.
• 3: BLUM, L., BRANDENBURGER, A., AND DEKEL, E. 1991. Lexicographic probabilities and equilibrium refinements. Econometrica 59, 61-79.
• 4: Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
• 5: BOUTILIER, C. 1994. Toward a Logic for Qualitative Decision Theory. In Proceedings of the 4th International Conference on Principles of Knowledge Representation and Reasoning. Morgan-Kaufmann, San Francisco, Calif., pp. 75-86.
• 6: BOUTILIER, C., BRAFMAN, R. I., GEIB, C., AND POOLE, D. 1997. Reasoning with ceteris paribus preference statements. In Proceedings of the AAAI Spring Symposium on Qualitative Preferences in Deliberation and Practical Reasoning. AAAI Press, Menlo Park, Calif.
• 7: BRAFMAN, R. I., AND FRIEDMAN, N. 1995. On decision-theoretic foundations for defaults. In Proceedings of the 14th International Joint Conference on Artificial Intelligence.
• 8: BRAFMAN, R. I., AND TENNENHOLTZ, M. 1994. Belief ascription and mental-level modelling. In Proceedings of the 4th International Conference on Principles of Knowledge Representation and Reasoning, J. Doyle, E. Sandewall, and P. Torasso, Eds., pp. 87-98.
• 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: Gregory F. Cooper, The computational complexity of probabilistic inference using Bayesian belief networks (research note), Artificial Intelligence, v.42 n.2-3, p.393-405, March 1990 [doi>10.1016/0004-3702(90)90060-D]
• 11: DARWICHE, A., AND GOLDSZMIDT, M. 1994. On the relation between kappa calculus and probabilistic reasoning. In Proceedings of the lOth Conference on Uncertainty in Artificial Intelligence (UAI '94). Morgan-Kaufmann, San Francisco, Calif., pp. 145-153.
• 12: J. Doyle, Constructive belief and rational representation, Computational Intelligence, v.5 n.1, p.1-11, February 1989 [doi>10.1111/j.1467-8640.1989.tb00311.x]
• 13: DOYLE, J., AND THOMASON, R. 1997. Qualitative preferences in deliberation and practical reasoning. Working notes of the AAAI spring symposium.
• 14: DOYLE, J., AND WELLMAN, M. 1994. Representing preferences as ceteris paribus comparatives. In Proceedings of the AAAI Spring Symposium on Decision-Theoretic Planning. AAAI Press, Menlo Park, Calif., pp. 69-75.
• 15: Jon Doyle , Michael P. Wellman, Impediments to Universal preference-based default theories, Proceedings of the first international conference on Principles of knowledge representation and reasoning, p.94-102, December 1989
• 16: DUBOIS, D., AND PRADE, H. 1995. Possibility theory as a basis for qualitative decision theory. In Proceedings of the 14th International Joint Conference on Artificial Intelligence. pp. 1924-1930.
• 17: DUBOIS, D., PRADE, H., AND SABBADIN, R. 2000. Decision-theoretic foundations of qualitative possibility theory. Europ. J. Oper. Res., to appear.
• 18: EL-YANIV, R. 2000. On the decision theoretic foundations of the competative ratio criterion. Unpublished manuscript.
• 19: Ronald Fagin , Joseph Y. Halpern , Moshe Y. Vardi , Yoram Moses, Reasoning about knowledge, MIT Press, Cambridge, MA, 1995
• 20: FISHBURN, P. C. 1988. Nonlinear Preference and Utility Theory. Johns Hopkins University Press, Baltimore, Md.
• 21: FORBUS, K.D. 1985. Qualitative process theory. In Qualitative Reasoning About Physical Systems. D. Bobrow, Ed. The MIT Press, Cambridge, Mass.
• 22: Nir Friedman , Joseph Y. Halpern, A knowledge-based framework for belief change part I: foundations, Proceedings of the 5th conference on Theoretical aspects of reasoning about knowledge, p.44-64, March 13-16, 1994, Pacific Grove, California
• 23: FUDENBERG, D., AND TIROLE, J. 1991. Game Theory. MIT Press, Cambridge, Mass.
• 24: Peter Gardenfors, Belief Revision, Cambridge University Press, New York, NY, 1992
• 25: GILBOA, I., AND SCHMEIDLER, D. 1989. Maxmin expected utility with a non-unique prior. J. Math. Econ. 18, 141-153.
• 26: GILBOA, I., AND SCHMEIDLER, D. 1995. Case-based decision theory. Quart. J. Econ. 110, 605-639.
• 27: Matthew L. Ginsberg, Readings in nonmonotonic reasoning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1987
• 28: J Halpern, Reasoning about knowledge: an overview, Proceedings of the 1986 Conference on Theoretical aspects of reasoning about knowledge, p.1-17, March 1986, Monterey, California, United States
• 29: Joseph Y. Halpern , Yoram Moses, Knowledge and common knowledge in a distributed environment, Journal of the ACM (JACM), v.37 n.3, p.549-587, July 1990 [doi>10.1145/79147.79161]
• 30: Sergiu Hart , Salvatore Modica , David Schmeidler, A neo2 Bayesian foundation of the maxmin value for two-person zero-sum games, International Journal of Game Theory, v.23 n.4, p.347-358, 1994 [doi>10.1007/BF01242948]
• 31: HOWARD, R.A. 1960. Dynamic Programming and Markov Processes. MIT Press, Cambridge, Mass.
• 32: KREPS, D.M. 1988. Notes on the Theory of Choice. Westview Press, Boulder, Colo.
• 33: LAMARRE, P., AND SHOHAM, Y. 1994. Knowledge, certainty, belief and conditionalization. In Proceedings of the 4th International Conference on Principles of Knowledge Representation and Reasoning. Morgan-Kaufmann, San Francisco, Calif., pp. 415-424.
• 34: LEHMANN, D. 1996. Generalized qualitative probability: Savage revisited. In Proceedings of the 12th Annual Conference on Uncertainty in Artificial Intelligence (UAI '96). Morgan-Kaufmann, San Francisco, Calif., pp. 381-388.
• 35: Hector J Levesque, Knowledge representation and reasoning, Annual review of computer science vol. 1, 1986, Annual Reviews Inc., Palo Alto, CA, 1986
• 36: LUCE, R. D., AND RAIFFA, H. 1957. Games and Decisions. Wiley, New York.
• 37: MmNOR, J. 1954. Games against nature. In Decision Processes, R. M. Thrall, C. H. Coombs, and R. L. Davis, Eds. Wiley, New York.
• 38: Christos H. Papadimitriou , Mihalis Yannakakis, Shortest Paths Without a Map, Proceedings of the 16th International Colloquium on Automata, Languages and Programming, p.610-620, July 11-15, 1989
• 39: S J Rosenschein, Formal theories of knowledge in AI and robotics, New Generation Computing, v.3 n.4, p.345-357, 1985 [doi>10.1007/BF03037076]
• 40: SAVAGE, L.J. 1972. The Foundations of Statistics. Dover Publications, New York.
• 41: Solomon Eyal Shimony, Finding MAPs for belief networks is NP-hard, Artificial Intelligence, v.68 n.2, p.399-410, Aug. 1994 [doi>10.1016/0004-3702(94)90072-8]
• 42: 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
• 43: TAN, S. W., AND PEARL, J. 1994. Specification and evaluation of preferences under uncertainty. In Proceedings of the 4th International Conference on Principles of Knowledge Representation and Reasoning. pp. 530-539.
• 44: VON NEUMANN, J., AND MORGENSTERN, 0. 1944. Theory of Games and Economic Behavior. Princeton University Press, Princeton, N. J.
• 45: WALD, A. 1950. Statistical Decision Functions. Wiley, New York.
• 46: 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

General Terms:
Theory

Keywords:
agent models, choice theory, foundations of online algorithms, qualitative decision theory