article

Dealing with logical omniscience: Expressiveness and pragmatics

Authors:

Joseph Y. Halpern,

Riccardo PucellaAuthors Info & Claims

Artificial Intelligence, Volume 175, Issue 1

Pages 220 - 235

https://doi.org/10.1016/j.artint.2010.04.009

Published: 01 January 2011 Publication History

Abstract

We examine four approaches for dealing with the logical omniscience problem and their potential applicability: the syntactic approach, awareness, algorithmic knowledge, and impossible possible worlds. Although in some settings these approaches are equi-expressive and can capture all epistemic states, in other settings of interest (especially with probability in the picture), we show that they are not equi-expressive. We then consider the pragmatics of dealing with logical omniscience-how to choose an approach and construct an appropriate model.

References

[1]

P. Berman, J. Garay, K.J. Perry, Towards optimal distributed consensus, in: Proc. 30th IEEE Symposium on the Foundations of Computer Science (FOCS'89), 1989, pp. 410-415.

[2]

Cozic, M., Impossible states at work: Logical omniscience and rational choice. In: Contrib. Econ. Anal., vol. 280. Elsevier.

[3]

Dekel, E., Lipman, B. and Rustichini, A., Standard state-space models preclude unawareness. Econometrica. v66. 159-173.

[4]

Dolev, D. and Yao, A.C., On the security of public key protocols. IEEE Trans. Inform. Theory. v29 i2. 198-208.

[5]

Eberle, R.A., A logic of believing, knowing and inferring. Synthese. v26. 356-382.

[6]

Enderton, H.B., A Mathematical Introduction to Logic. 1972. Academic Press.

[7]

Fagin, R. and Halpern, J.Y., Belief, awareness, and limited reasoning. Artificial Intelligence. v34. 39-76.

[8]

Fagin, R. and Halpern, J.Y., Reasoning about knowledge and probability. J. ACM. v41 i2. 340-367.

[9]

Fagin, R., Halpern, J.Y. and Megiddo, N., A logic for reasoning about probabilities. Inform. Comput. v87 i1/2. 78-128.

[10]

Fagin, R., Halpern, J.Y., Moses, Y. and Vardi, M.Y., Reasoning about Knowledge. 1995. MIT Press.

[11]

Halpern, J.Y., Alternative semantics for unawareness. Games Econ. Behav. v37. 321-339.

[12]

Halpern, J.Y., Moses, Y. and Vardi, M.Y., Algorithmic knowledge. In: Proc. 5th Conference on Theoretical Aspects of Reasoning about Knowledge (TARK'94), Morgan Kaufmann. pp. 255-266.

[13]

Halpern, J.Y. and Pucella, R., Modeling adversaries in a logic for reasoning about security protocols. In: Lecture Notes in Comput. Sci., vol. 2629. pp. 115-132.

[14]

J.Y. Halpern, L.C. Rêgo, Interactive unawareness revisited, in: Theoretical Aspects of Rationality and Knowledge: Proc. Tenth Conference (TARK 2005), 2005, pp. 78-91.

[15]

Halpern, J.Y. and Weissman, V., Using first-order logic to reason about policies. ACM Trans. Inform. Syst. Secur. v11 i4. 1-41.

[16]

Heifetz, A., Meier, M. and Schipper, B., Interactive unawareness. J. Econ. Theory. v130. 78-94.

[17]

Hintikka, J., Impossible possible worlds vindicated. J. Philos. Logic. v4. 475-484.

[18]

Konolige, K., A Deduction Model of Belief. 1986. Morgan Kaufmann, San Francisco.

[19]

Lipman, B.L., Decision theory without logical omniscience: Toward an axiomatic framework for bounded rationality. Rev. Econ. Stud. v66 i2. 339-361.

[20]

K. Manne, Towards a solution to the problem of logical omniscience for resource-bounded agents: An impossible worlds approach to temporal epistemic logic, unpublished manuscript; an abstract appears in: Proc. 2005 Conference of the Australasian Association of Philosophy, 2005.

[21]

J. McCarthy, M. Sato, T. Hayashi, S. Igarishi, On the model theory of knowledge, Tech. Rep. STAN-CS-78-657, Stanford University, 1979.

Digital Library

[22]

Modica, S. and Rustichini, A., Awareness and partitional information structures. Theory Dec. v37. 107-124.

[23]

Modica, S. and Rustichini, A., Unawareness and partitional information structures. Games Econ. Behav. v27 i2. 265-298.

[24]

R.C. Moore, G. Hendrix, Computational models of beliefs and the semantics of belief sentences, Technical Note 187, SRI International, Menlo Park, CA, 1979.

[25]

Moreno, A., Avoiding logical omniscience and perfect reasoning: A survey. AI Commun. v11 i2. 101-122.

[26]

Moses, Y. and Tuttle, M.R., Programming simultaneous actions using common knowledge. Algorithmica. v3. 121-169.

[27]

Pucella, R., Deductive algorithmic knowledge. J. Logic Comput. v16 i2. 287-309.

[28]

Rantala, V., Urn models: A new kind of non-standard model for first-order logic. J. Philos. Logic. v4. 455-474.

[29]

Rantala, V., Impossible worlds semantics and logical omniscience. Acta Philosophica Fennica. v35. 18-24.

[30]

Stalnaker, R., Impossibilities. Philos. Topics. v24. 193-204.

[31]

Wansing, H., A general possible worlds framework for reasoning about knowledge and belief. Studia Logica. v49 i4. 523-539.

Cited By

Aucher G(2020)Expedition in the Update UniverseDynamic Logic. New Trends and Applications10.1007/978-3-030-65840-3_1(1-16)Online publication date: 9-Oct-2020
https://dl.acm.org/doi/10.1007/978-3-030-65840-3_1
Souza M(2020)Towards a Theory of Hyperintensional Belief ChangeIntelligent Systems10.1007/978-3-030-61380-8_19(272-287)Online publication date: 20-Oct-2020
https://dl.acm.org/doi/10.1007/978-3-030-61380-8_19
Askounis DKoutras CMoyzes CZikos Y(2014)Only-Knowing la Halpern-Moses for Non-omniscient Rational AgentsProceedings of the 14th European Conference on Logics in Artificial Intelligence - Volume 876110.1007/978-3-319-11558-0_20(282-296)Online publication date: 24-Sep-2014
https://dl.acm.org/doi/10.1007/978-3-319-11558-0_20
Show More Cited By

Dealing with logical omniscience: Expressiveness and pragmatics
1. Theory of computation

Recommendations

Avoiding logical omniscience and perfect reasoning: a survey

Beliefs have been formally modelled in the last decades using doxastic logics. The possible worlds model and its associated Kripke semantics provide an intuitive semantics for these logics, but they seem to commit us to model agents that are logically ...
The Effort of Reasoning: Modelling the Inference Steps of Boundedly Rational Agents
Abstract
In this paper we design a new logical system to explicitly model the different deductive reasoning steps of a boundedly rational agent. We present an adequate system in line with experimental findings about an agent’s reasoning limitations and the ...
Logical omniscience via proof complexity
CSL'06: Proceedings of the 20th international conference on Computer Science Logic

The Hintikka-style modal logic approach to knowledge contains a well-known defect of logical omniscience, i.e., the unrealistic feature that an agent knows all logical consequences of her assumptions. In this paper, we suggest the following Logical ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Artificial Intelligence

Artificial Intelligence Volume 175, Issue 1

January, 2011

443 pages

ISSN:0004-3702

Issue’s Table of Contents

Copyright © Elsevier B.V. © 2010.

Publisher

Elsevier Science Publishers Ltd.

United Kingdom

Publication History

Published: 01 January 2011

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Aucher G(2020)Expedition in the Update UniverseDynamic Logic. New Trends and Applications10.1007/978-3-030-65840-3_1(1-16)Online publication date: 9-Oct-2020
https://dl.acm.org/doi/10.1007/978-3-030-65840-3_1
Souza M(2020)Towards a Theory of Hyperintensional Belief ChangeIntelligent Systems10.1007/978-3-030-61380-8_19(272-287)Online publication date: 20-Oct-2020
https://dl.acm.org/doi/10.1007/978-3-030-61380-8_19
Askounis DKoutras CMoyzes CZikos Y(2014)Only-Knowing la Halpern-Moses for Non-omniscient Rational AgentsProceedings of the 14th European Conference on Logics in Artificial Intelligence - Volume 876110.1007/978-3-319-11558-0_20(282-296)Online publication date: 24-Sep-2014
https://dl.acm.org/doi/10.1007/978-3-319-11558-0_20
Holliday W(2010)Epistemic logic, relevant alternatives, and the dynamics of contextProceedings of the 2010 international conference on New Directions in Logic, Language and Computation10.1007/978-3-642-31467-4_8(109-129)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.1007/978-3-642-31467-4_8

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents