×

Impediments to universal preference-based default theories. (English) Zbl 0736.68069

Summary: Research on nonmonotonic and default reasoning has identified several important criteria for preferring alternative default inferences. The theories of reasoning based on each of these criteria may be viewed as theories of rational inference, in which the reasoner selects maximally preferred states of belief. Though researchers have noted some cases of apparent conflict between the preferences supported by different theories, it has been hoped that these special theories of reasoning may be combined into a universal logic of nonmonotonic reasoning. We show that the different categories of preferences conflict ore than has been realized, and adapt formal results from social choice theory to prove that every universal theory of default reasoning will violate at least one reasonable principle of rational reasoning. Our results can be interpreted as demonstrating that, within the preferential framework, we cannot expect much improvement on the rigid lexicographic priority mechanisms that have been proposed for conflict resolution.

MSC:

68T15 Theorem proving (deduction, resolution, etc.) (MSC2010)
68T27 Logic in artificial intelligence
68T30 Knowledge representation
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arrow, K. J., (Social Choice and Individual Values (1963), Yale University Press: Yale University Press New Haven, CT) · Zbl 0984.91513
[2] Arrow, K. J., Values and collective decision-making, (Laslett, P.; Runciman, W. G., Philosophy, Politics and Society (third series) (1967), Basil Blackwell: Basil Blackwell Oxford), 215-232
[3] Borgida, A.; Imilienski, T., Decision making in committees—a framework for dealing with inconsistency and non-monotonicity, (Proceedings Workshop on Non-Monotonic Reasoning. Proceedings Workshop on Non-Monotonic Reasoning, New Paltz, NY (1984)), 21-32
[4] Brown, A. L.; Shoham, Y., New results on semantical nonmonotonic reasoning, (Reinfrank, M.; de Kleer, J.; Ginsberg, M. L.; etal., Non-Monotonic Reasoning (1989), Springer: Springer New York), 19-26 · Zbl 0675.03008
[5] Doyle, J., A society of mind: multiple perspectives, reasoned assumptions, and virtual copies, (Proceedings IJCAI-83. Proceedings IJCAI-83, Karlsruhe, FRG (1983)), 309-314
[6] Doyle, J., Some theories of reasoned assumptions: an essay in rational psychology, (Tech. Report 83-125 (1983), Department of Computer Science, Carnegie-Mellon University: Department of Computer Science, Carnegie-Mellon University Pittsburgh, PA)
[7] Doyle, J., Reasoned assumptions and Pareto optimality, (Proceedings IJCAI-85. Proceedings IJCAI-85, Los Angeles, CA (1985)), 87-90
[8] Doyle, J., Artificial intelligence and rational self-government, (Tech. Report CS-88-124 (1988), Department of Computer Science, Carnegie-Mellon University: Department of Computer Science, Carnegie-Mellon University Pittsburgh, PA)
[9] Doyle, J., Constructive belief and rational representation, Comput. Intell., 5, 1-11 (1989)
[10] Doyle, J., Rational belief revision, (Presented at the Third International Workshop on Nonmonotonic Reasoning. Presented at the Third International Workshop on Nonmonotonic Reasoning, Stanford, CA (1990)) · Zbl 0766.68126
[11] Doyle, J., Rationality and its roles in reasoning (extended abstract), (Proceedings AAAI-90. Proceedings AAAI-90, Boston, MA (1990)), 1093-1100
[12] Doyle, J.; Wellman, M. P., Impediments to universal preference-based defauit theories, (Brachman, R. J.; Levesque, H. J.; Reiter, R., Proceedings of the First International Conference on Principles of Knowledge Representation and Reasoning. Proceedings of the First International Conference on Principles of Knowledge Representation and Reasoning, Toronto, Ont. (1989), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 94-102
[13] Etherington, D. W., (Reasoning with Incomplete Information (1988), Pitman: Pitman London) · Zbl 0694.68003
[14] Fagin, R.; Halpern, J. Y., Belief, awareness, and limited reasoning: preliminary report, (Proceedings IJCAI-85. Proceedings IJCAI-85, Los Angeles, CA (1985)), 491-501
[15] Gibbard, A., Manipulation of voting schemes: a general result, Econometrica, 41, 587-601 (1973) · Zbl 0325.90081
[16] (Ginsberg, M. L., Readings in Nonmonotonic Reasoning (1987), Morgan Kaufmann: Morgan Kaufmann Los Altos, CA)
[17] Grosof, B. N., Generalizing prioritization (February 1990), Manuscript
[18] Halpern, J. Y.; Moses, Y., Towards a theory of knowledge and ignorance: preliminary report, (Proceedings Workshop on Non-Monotonic Reasoning. Proceedings Workshop on Non-Monotonic Reasoning, New Paltz, NY (1984)), 125-143 · Zbl 0581.68067
[19] Hanks, S.; McDermott, D., Nonmonotonic logic and temporal projection, Artif. Intell., 33, 379-412 (1987) · Zbl 0654.68107
[20] Horty, J. F.; Thomason, R. H., Deontic foundations for nonmonotonic reasoning, (Presented at the Third International Workshop on Nonmonotonic Reasoning. Presented at the Third International Workshop on Nonmonotonic Reasoning, Stanford, CA (1990))
[21] Horty, J. F.; Thomason, R. H.; Touretzky, D. S., A skeptical theory of inheritance in nonmonotonic semantic networks, Artif. Intell., 42, 311-348 (1990) · Zbl 0717.68085
[22] James, W., (The Will to Believe and Other Essays in Popular Philosophy (1897), Longmans, Green, and Co: Longmans, Green, and Co New York)
[23] Keeney, R. L.; Raiffa, H., (Decisions with Multiple Objectives: Preferences and Value Tradeoffs (1976), Wiley: Wiley New York) · Zbl 0396.90001
[24] Konolige, K., Hierarchic autoepistemic theories for nonmonotonic reasoning, (Proceedings AAAI-88. Proceedings AAAI-88, St. Paul, MN (1988)), 439-443
[25] Artif. Intell., 41, 115 (1989/1990) · Zbl 0647.68088
[26] Langlotz, C. P.; Shortliffe, E. H., Logical and decision-theoretic methods for planning under uncertainty, AI Mag., 10, 39-47 (1989)
[27] Levesque, H. J., A logic of implicit and explicit belief, (Proceedings AAAI-84. Proceedings AAAI-84, Austin, TX (1984)), 198-202
[28] Levesque, H. J., Making believers out of computers, Artif. Intell., 30, 81-108 (1986)
[29] Lifschitz, V., Pointwise circumscription: preliminary report, (Proceedings AAAI-86. Proceedings AAAI-86, Philadelphia, PA (1986)), 406-410
[30] Lifschitz, V., Formal theories of action, (Brown, F. M., The Frame Problem in Artificial Intelligence: Proceedings of the 1987 Workshop (1987), Morgan Kaufmann: Morgan Kaufmann Los Altos, CA), 35-57
[31] Lifschitz, V., Between circumscription and autoepistemic logic, (Brachman, R. J.; Levesque, H. J.; Reiter, R., Proceedings of the First International Conference on Principles of Knowledge Representation and Reasoning. Proceedings of the First International Conference on Principles of Knowledge Representation and Reasoning, Toronto, Ont. (1989), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 235-244 · Zbl 0706.03025
[32] Lin, F.; Shoham, Y., Argument systems: a uniform basis for nonmonotonic reasoning, (Brachman, R. J.; Levesque, H. J.; Reiter, R., Proceedings of the First International Conference on Principles of Knowledge Representation and Reasoning. Proceedings of the First International Conference on Principles of Knowledge Representation and Reasoning, Toronto, Ont. (1989), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 245-255
[33] Longley-Cook, L. H., An introduction to credibility theory, (Proc. Casualty Actuarial Soc., 49 (1962)), 194
[34] Loui, R. P., Computing reference classes, (Lemmer, J. F.; Kanal, L. N., Uncertainty in Artificial Intelligence, 2 (1988), North-Holland: North-Holland Amsterdam), 273-289
[35] McCarthy, J., Circumscription—a form of non-monotonic reasoning, Artif. Intell., 13, 27-38 (1980) · Zbl 0435.68073
[36] McCarthy, J., Applications of circumscription to formalizing common-sense knowledge, Artif. Intell., 28, 89-116 (1986)
[37] McDermott, D., AI, logic, and the frame problem, (Brown, F. M., The Frame Problem in Artificial Intelligence: Proceedings of the 1987 Workshop (1987), Morgan Kaufmann: Morgan Kaufmann Los Altos, CA), 105-118
[38] McDermott, D., A critique of pure reason, Comput. Intell., 3, 151-160 (1987)
[39] McDermott, D.; Doyle, J., Non-monotonic logic—I, Artif. Intell., 13, 41-72 (1980) · Zbl 0435.68074
[40] Minsky, M., (The Society of Mind (1986), Simon and Schuster: Simon and Schuster New York)
[41] Moore, R. C., Possible world semantics for autoepistemic logic, (Proceedings Workshop on Non-Monotonic Reasoning. Proceedings Workshop on Non-Monotonic Reasoning, New Paltz, NY (1984)), 21-32
[42] Moore, R. C., Semantical considerations on nonmonotonic logic, Artif. Intell., 25, 75-94 (1985) · Zbl 0569.68079
[43] Mundell, R. A., (Man and Economics (1968), McGraw-Hill: McGraw-Hill New York)
[44] Nowakowska, M., (Language of Motivation and Language of Actions (1973), Mouton & Co: Mouton & Co The Hague)
[45] Pascal, B., Pensées sur la religion et sur quelques autres sujets (1962), Harvill: Harvill London, Translated by M. Turnell, originally published 1662
[46] Pollock, J. L., Defeasible reasoning, Cogn. Sci., 11, 481-518 (1987)
[47] Poole, D., What the lottery paradox tells us about default reasoning, (Brachman, R. J.; Levesque, H. J.; Reiter, R., Proceedings of the First International Conference on Principles of Knowledge Representation and Reasoning. Proceedings of the First International Conference on Principles of Knowledge Representation and Reasoning, Toronto, Ont. (1989), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 333-340 · Zbl 0709.68066
[48] Reiter, R., On closed world data bases, (Gallaire, H.; Minker, J., Logic and Data Bases (1978), Plenum: Plenum New York), 55-76
[49] Reiter, R., A logic for default reasoning, Artif. Intell., 13, 81-132 (1980) · Zbl 0435.68069
[50] Roberts, F. S., (Discrete Mathematical Models (1976), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ)
[51] Roberts, K. W.S., Possibility theorems with interpersonally comparable welfare levels, Rev. Econ. Stud., 47, 409-420 (1980) · Zbl 0432.90008
[52] Rychlik, P., The generalized theory of model preference (preliminary report), (Proceedings AAAI-90. Proceedings AAAI-90, Boston, MA (1990)), 615-620
[53] Sen, A., The impossibility of a Paretian liberal, J. Political Econ., 78, 152-157 (1970)
[54] Sen, A., Social choice theory: a re-examination, Econometrica, 45, 53-89 (1977) · Zbl 0353.90001
[55] Shoham, Y., Nonmonotonic logics: meaning and utility, (Proceedings IJCAI-87. Proceedings IJCAI-87, Milan, Italy (1987)), 388-393
[56] Shoham, Y., (Reasoning about Change: Time and Causation from the Standpoint of Artificial Intelligence (1988), MIT Press: MIT Press Cambridge, MA)
[57] Stein, L. A., Skeptical inheritance: computing the intersection of credulous extensions, (Proceedings IJCAI-89. Proceedings IJCAI-89, Detroit, MI (1989)), 1153-1158 · Zbl 0714.68095
[58] Sternberg, R. J., Intelligence is mental self-government, (Sternberg, R. J.; Detterman, D. K., What is Intelligence? Contemporary Viewpoints on its Nature and Definition (1986), Ablex: Ablex Norwood, NJ), 141-148
[59] Thomason, R. H., The context-sensitivity of belief and desire, (Georgeff, M. P.; Lansky, A. L., Reasoning about Actions and Plans: Proceedings of the 1986 Workshop (1986), Morgan Kaufmann: Morgan Kaufmann Los Altos, CA), 341-360
[60] Touretzky, D. S., (The Mathematics of Inheritance Systems (1986), Morgan Kaufmann: Morgan Kaufmann Los Altos, CA) · Zbl 0675.68006
[61] Touretzky, D. S.; Horty, J. F.; Thomason, R. H., A clash of intuitions: the current state of nonmonotonic multiple inheritance systems, (Proceedings IJCAI-87. Proceedings IJCAI-87, Milan, Italy (1987)), 476-482
[62] Tullock, G., The general irrelevance of the general impossibility theorem, Q. J. Econ., 81, 256-270 (1967)
[63] Van Frassen, B. C., Values and the heart’s command, J. Philos., LXX, 5-19 (1973)
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.