Knowledge, common knowledge and related puzzles (Extended Summary)

ABSTRACT

Many distributed systems, as well as many real life situations, are best described as involving changes in the partial knowledge that components may have about the real state of the whole system. Examples include synchronization and cooperation protocols, cryptographic systems, games, economics and intelligent programs. In such situations the notion of common knowledge has been recognized as of fundamental importance by Lewis [Le] and Aumann [A]. An event is common knowledge if everybody knows it, everybody knows that everybody knows it, and so on. A method for the formal description of such systems and the rigorous proof of certain of their properties is presented. Its limitations are analyzed. As examples, a well-known puzzle and a logical paradox are treated. A propositional language in which one may describe knowledge, common knowledge and their changes with time is defined. In particular one may describe the knowledge that agents may have of the present state of the world, future states of the world and the knowledge that others may or may not have about the present and future states of the world. The language is interpreted in models a la Kripke, where knowledge is interpreted by a binary relation. An axiomatization is given and shown sound and complete with respect to the models. A doubly-exponential deterministic time decision procedure is described.

REFERENCES

• 1: Aumann, Robert J., Agreeing to disagree. The Annals of Statistics Vol. 4, No. 6 pp. 1236-1239 (1976).
• 2: Dolev, D., Halpern, J. Y. and Moses, Y. The cheating spice and related topics (manuscript 1983).
• 3: Dov Gabbay , Amir Pnueli , Saharon Shelah , Jonathan Stavi, On the temporal analysis of fairness, Proceedings of the 7th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.163-173, January 28-30, 1980, Las Vegas, Nevada [doi>10.1145/567446.567462]
• 4: Geanakoplos, John D. and Polemarchakis, Heraklis M., We can't disagree for ever, Journal of Economic Theory Vol. 28 pp. 192-200 (1982).
• 5: Hintikka, Jaakko, Knowledge and belief, an introduction to the logic of the two notions, Cornell Univ. Press, Ithaca and London (1962).
• 6: Joseph Y. Halpern , Michael O. Rabin, A logic to reason about likelihood, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.310-319, December 1983 [doi>10.1145/800061.808760]
• 7: Kraus, S. and Lehmann, D. Decision procedures for Time and Chance, Jerusalem 1983 (manuscript), see also preliminary results in Proceedings of 24th I.E.E.E. Annual Symposium on the Foundations of Computer Science, Tucson, Arizona, November 1983, pp. 202-209.
• 8: Ladner, Richard E. The computational complexity of provability in systems of modal propositional logic, SIAM Journal on Computing, Vol. 6 pp. 467-480 (1977).
• 9: Lewis, David K., Convention, Harvard University Press, Cambridge, Massachusetts, 1969.
• 10: Lehmann, Daniel and Shelah, Saharon, Reasoning with Time and Chance, Information and Control, Vol. 53 pp. 165-198 (1982).
• 11: Milgrom, P., An axiomatic characterization of common knowledge, Econometrica, Vol. 49, No. 1 pp. 219-222 (1981).
• 12: Sato, Masahiko, Kripke-type models for some modal logics, Publications of the research institute for mathematical sciences, Vol. 13 No. 2 pp. 381-468 (1977).
• 13: Stark, W. Richard, A logic of knowledge, Zeitschr. f. math. Logik und Grundlagen d. Math. Vol. 27 pp. 371-374 (1981).

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Knowledge acquisition

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

General Terms:
Human Factors