Common Knowledge of Abstract Groups

Merlin Humml, Lutz SchröderAAAI 2023 · DOI

TL;DR

This paper introduces Abstract-Group Epistemic Logic (AGEL), a new logic for reasoning about common knowledge among groups of agents defined by abstract properties (like "all doctors") rather than explicit lists. AGEL is shown to be EXPTIME-complete, with a finite model property and a complete axiomatization, offering a more flexible and computationally tractable way to model complex epistemic scenarios.

What Problem Does This Paper Address?

Traditional epistemic logics, which deal with knowledge and belief, often struggle to represent common knowledge within groups of agents that aren't explicitly enumerated. For instance, saying "all doctors know X" is difficult to formalize if the set of doctors is not fixed or known beforehand. Existing approaches typically require listing agents or using rigid, pre-defined groups. This limitation makes it hard to express common knowledge in real-world scenarios where group membership is fluid or defined by properties (e.g., "parents of teenagers," "economists"). AGEL aims to bridge this gap by allowing common knowledge operators to be parameterized by abstract agent concepts from a separate agent logic.

Methods

The core of AGEL lies in its novel common knowledge operator, $C_\psi \phi$, where $\psi$ is a formula from an underlying agent logic that defines the group of agents. The paper defines the syntax and semantics of AGEL, keeping the agent logic generic but requiring it to satisfy certain properties (like being expressible in ALC).

Key technical contributions include:

  • EXPTIME-Completeness: The satisfiability problem for AGEL is proven to be EXPTIME-complete. The lower bound is established by a satisfiability-preserving translation from standard Group Epistemic Logic (GEL). The upper bound is achieved by a translation into the full $\mu$-calculus.
  • Finite Model Property: Unlike the full $\mu$-calculus, AGEL possesses a bounded model property, meaning that if a formula is satisfiable, it is satisfiable in a model of a certain finite size. This is established through a novel filtered model construction.
  • Complete Axiomatization: A Hilbert-style axiomatization (C5) is presented and shown to be weakly complete for AGEL.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Abstract Groups for Common Knowledge: The central idea is to move beyond explicitly listed agents to defining groups by properties. This significantly enhances the expressiveness for real-world scenarios.
  • Decoupling Agent and World Logic: AGEL separates the logic for defining agent groups (the agent logic) from the logic for reasoning about states of the world (the world logic). This modularity allows for flexibility in choosing the agent logic.
  • EXPTIME as a Sweet Spot: The EXPTIME complexity for AGEL is a notable result. It suggests that while reasoning about abstract groups is more complex than simple modal logic, it remains computationally tractable for many practical applications, especially compared to potentially higher complexities of other formalisms.
  • Finite Models for Epistemic Logic: The demonstration of a bounded model property for AGEL is important, as it guarantees that satisfiability checking can be performed on finite structures, which is crucial for automated reasoning.

Key Results

  • EXPTIME-Completeness: The satisfiability problem for AGEL is EXPTIME-complete.
  • Bounded Model Property: AGEL has a finite model property, with models bounded doubly exponentially in the size of the formula.
  • Weak Completeness: A Hilbert-style system (C5) is presented and shown to be weakly complete for AGEL.

Limitations and Future Work

The authors acknowledge that their AGEL formulation assumes "rigid" agent logic, meaning agent concepts are interpreted directly and not subject to uncertainty about their meaning (de re rather than de dicto). Future work could explore extensions to handle non-rigid agent names and concepts, allowing for reasoning about uncertainty in group membership. Other promising directions include incorporating dynamic epistemic logic modalities (like public announcements), distributed knowledge operators, and mechanisms for describing groups based on individual agents' knowledge.

Summary updated

BibTeX
@inproceedings{humml2023common,
  author = {Merlin Humml and Lutz Schröder},
  title = {{Common Knowledge of Abstract Groups}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i5.25791},
}
Figure