Reasoning about common knowledge with infinitely many agents.

*(English)*Zbl 1078.03014The complexity of the satisfiability problem for epistemic logic with an infinite set of agents is characterized in the paper. A consideration of infinitely many agents is motivated by (many) applications where the set of agents is not known in advance and has no a priori upper bound. A language \(\mathcal L^{C}_{\mathcal G}(\Phi)\) is used in the paper, where \(\Phi\) is a set of primitive propositions, \(\mathcal A\) is a possibly infinite set of agents, \(\mathcal G\) is a set of nonempty subsets of \(\mathcal A\) and formulas are build over \(\Phi\) by operators \(\neg, \vee, K_i\), for \(i \in \mathcal A, E_G, C_G\), for \(G \in {\mathcal G}\). \(C_G\) intuitively means “common knowledge among group \(G\)” and \(E_G\) means “everyone in \(G\) knows”. A Kripkean semantics is given for the language(s). Standard axioms and rules for the knowledge operators \(K_i\) are used. Axioms (and a rule) for reasoning about “everyone in \(G\) knows” are crucial for the presented formalization. Finally, also common knowledge is axiomatized in a standard way. Two important and technically difficult main results are obtained. The first main result of the paper is regarding completeness of the axiomatization. It is shown that the axiomatization for reasoning about knowledge and common knowledge (if there are infinitely many agents) is sound and complete. Second, it is shown that there is an exponential decision procedure for satisfiability checking. It is shown that reasoning about knowledge and common knowledge with infinitely many agents is not harder than when there are finitely many agents, provided that we can check the cardinality of set differences \(G - G^{\prime}\), where \(G\) and \(G^{\prime}\) are sets of agents. Complexity results represent improvements over previous results even for finite sets of agents (the results are independent of cardinality). It is also shown that the obtained results depend on how the sets of agents are represented. The used representation involves only set difference and union; it remains an open question whether the results can be extended also for the descriptions that involve intersection and complementation. Finally, directions for extending the results of the paper are described.

Reviewer: Jan Šefránek (Bratislava)

##### MSC:

03B42 | Logics of knowledge and belief (including belief change) |

68T27 | Logic in artificial intelligence |

68T30 | Knowledge representation |

##### Keywords:

reasoning about knowledge; infinitely many agents; axiomatization; completeness; satisfiability; decision procedure; exponential complexity; epistemic logic
PDF
BibTeX
XML
Cite

\textit{J. Y. Halpern} and \textit{R. A. Shore}, Inf. Comput. 191, No. 1, 1--40 (2004; Zbl 1078.03014)

Full Text:
DOI

##### References:

[1] | Aumann, R.J., Agreeing to disagree, Annals of statistics, 4, 6, 1236-1239, (1976) · Zbl 0379.62003 |

[2] | Chellas, B.F., Modal logic, (1980), Cambridge University Press Cambridge, UK · Zbl 0431.03009 |

[3] | Fagin, R.; Halpern, J.Y.; Moses, Y.; Vardi, M.Y., Reasoning about knowledge, (1995), MIT Press Cambridge, MA · Zbl 0839.68095 |

[4] | Fagin, R.; Halpern, J.Y.; Vardi, M.Y., What can machines know? on the properties of knowledge in distributed systems, Journal of the ACM, 39, 2, 328-376, (1992) · Zbl 0799.68179 |

[5] | Fischer, M.J.; Ladner, R.E., Propositional dynamic logic of regular programs, Journal of computer and system sciences, 18, 2, 194-211, (1979) · Zbl 0408.03014 |

[6] | Geanakoplos, J., Common knowledge, (), 1437-1496 · Zbl 0925.90082 |

[7] | Halpern, J.Y., The effect of bounding the number of primitive propositions and the depth of nesting on the complexity of modal logic, Artificial intelligence, 75, 2, 361-372, (1995) · Zbl 1014.03508 |

[8] | Halpern, J.Y.; van der Meyden, R., A logic for SDSI’s linked local name spaces, Journal of computer security, 9, 1,2, 47-74, (2001) |

[9] | J.Y. Halpern, R. van der Meyden, F. Schneider, Logical foundations for trust management, unpublished manuscript, 1999 |

[10] | Halpern, J.Y.; Moses, Y., A guide to completeness and complexity for modal logics of knowledge and belief, Artificial intelligence, 54, 319-379, (1992) · Zbl 0762.68029 |

[11] | R. Rivest, B. Lampson, SDSI—a simple distributed security infrastructure, 1996. Available from http://theory.lcs.mit.edu/ cis/sdsi.html |

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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.