Common knowledge in interaction structures

ABSTRACT

We consider two simple variants of a framework for reasoning about knowledge amongst communicating groups of players. Our goal is to clarify the resulting epistemic issues. In particular, we investigate what is the impact of common knowledge of the underlying hypergraph connecting the players, and under what conditions common knowledge distributes over disjunction. We also obtain two versions of the classic result that common knowledge cannot be achieved in the absence of a simultaneous event (here a message sent to the whole group).

REFERENCES

• 1: K. R. Apt, A. Witzel, and J. A. Zvesper. Strategy elimination in games with interaction structures. Manuscript, 2009.
• 2: K. M. Chandy , Jayadev Misra, How processes learn, Distributed Computing, v.1 n.1, p.40-52, Jan. 1986 [doi>10.1007/BF01843569]
• 3: Ronald Fagin , Joseph Y. Halpern , Moshe Y. Vardi , Yoram Moses, Reasoning about knowledge, MIT Press, Cambridge, MA, 1995
• 4: R. Fagin, J. Y. Halpern, Y. Moses, and M. Y. Vardi. Common knowledge revisited. Annals of Pure and Applied Logic, 96(1--3):89--105, 1999.
• 5: 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]
• 6: Matthew O. Jackson, Social and Economic Networks, Princeton University Press, Princeton, NJ, 2008
• 7: E. Pacuit and R. Parikh. Reasoning about communication graphs. In Interactive Logic, volume 1 of Texts in Logic and Games, pages 135--157, London, 2007. Amsterdam University Press.
• 8: F. Roelofsen. Exploring logical perspectives on distributed information and its dynamics. Master's thesis, ILLC, University of Amsterdam, 2005.
• 9: J. van Benthem. One is a lonely number: Logic and communication. In Logic Colloquium 2002, volume 27 of Lecture Notes in Logic, pages 96--129. A K Peters, 2006.
• 10: Johan van Benthem , Jelle Gerbrandy , Eric Pacuit, Merging frameworks for interaction: DEL and ETL, Proceedings of the 11th conference on Theoretical aspects of rationality and knowledge, June 25-27, 2007, Brussels, Belgium [doi>10.1145/1324249.1324262]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.1 Expressions and Their Representation
          Subjects: Representations (general and polynomial)

General Terms:
Algorithms, Design, Theory