Game Description Language and Dynamic Epistemic Logic Compared

Thorsten Engesser, Robert Mattmüller, Bernhard Nebel, Michael ThielscherIJCAI 2018 · DOI

TL;DR

This paper bridges the gap between two powerful formalisms for reasoning about knowledge in multi-agent systems: Game Description Language (GDL-III) and Dynamic Epistemic Logic (DEL). By developing formal compilations between them, the authors demonstrate their equivalent expressiveness for large fragments, paving the way for combined approaches that leverage the strengths of both.

What Problem Does This Paper Address?

Modeling and reasoning about knowledge in dynamic multi-agent systems is a crucial area of research, with applications ranging from AI game playing to distributed systems. Two prominent frameworks have emerged: Dynamic Epistemic Logic (DEL), based on possible-worlds semantics, and the Game Description Language (GDL-III), a logic-programming-based language for specifying game rules. While both can handle epistemic reasoning, they have complementary strengths and weaknesses. DEL's explicit representation of knowledge through Kripke structures can be complex for modelers, while GDL-III's implicit handling of knowledge via observation tokens offers a more concise syntax but makes formal analysis more challenging. The core problem this paper addresses is to formally compare the expressiveness of these two languages and show how they can be reconciled, enabling the transfer of insights and the development of more powerful, unified approaches.

Methods

The paper's central contribution lies in establishing formal compilations between GDL-III and DEL.

  • GDL-III to DEL Compilation: The authors propose an extension to DEL called "edge-conditioned event models." These models allow for more succinct representation of actions by making event indistinguishability dependent on additional information, such as observation tokens. This extension is crucial for translating GDL-III's state-dependent observations into DEL. The compilation involves constructing a single composite event model in DEL that encapsulates all possible actions and observations from a GDL-III game description. This composite model is then used to translate GDL-III game rules into DEL domain descriptions.
  • DEL to GDL-III Compilation: To translate DEL into GDL-III, the authors address the difference in how initial states are handled. DEL allows for uncertainty about the initial state, while GDL-III assumes common knowledge. They introduce an "initial action" performed by a special "random" agent in GDL-III to generate an initial epistemic model that mirrors the DEL initial state. Subsequent DEL actions are then encoded as sequences of GDL-III rules, using observation tokens to represent the knowledge gained by agents.

The paper provides formal definitions for these compilations and proves their soundness and completeness, demonstrating that the translated systems are isomorphic and satisfy the same formulas.

Datasets

Not discussed in the paper. The paper focuses on formal language comparison and compilation, not on empirical evaluation using specific datasets.

Key Insights and Ideas

  • Equivalent Expressiveness: The most significant insight is that large fragments of GDL-III and DEL are equally expressive. This means that problems solvable in one formalism can be translated and solved in the other, providing a strong theoretical foundation for their comparison.
  • Edge-Conditioned Event Models: The introduction of edge-conditioned event models in DEL is a key methodological innovation. It allows for a more compact representation of epistemic actions, particularly those with state-dependent observations, which is a strength of GDL-III. This extension bridges a critical gap between the two formalisms.
  • Bridging Initial State Uncertainty: The paper elegantly handles the difference in initial state representation by using a "random" agent in GDL-III to simulate the uncertainty present in DEL's initial epistemic models.
  • Unified Framework Potential: The successful compilation suggests the possibility of developing a combined description language that integrates the intuitive syntax of GDL-III (especially its observation tokens) with the clean semantics of DEL, leading to more powerful and user-friendly tools for epistemic reasoning.

Key Results

The paper's primary results are the formal compilations from GDL-III to DEL and vice-versa, along with proofs of their correctness. These proofs establish:

  • Isomorphism of Transition Systems: The transition systems induced by a GDL-III game description and its DEL compilation are isomorphic.
  • Equivalence of Satisfied Formulas: For any formula in the epistemic language, it is satisfied in a given state of the DEL system if and only if it is satisfied in the corresponding state of the GDL-III system.
  • Practical Implications: The compilations demonstrate that GDL-III actions can be represented more compactly in DEL using the proposed edge-conditioned event models, and DEL actions can be encoded in GDL-III using observation tokens.

Limitations and Future Work

  • Sequentialization Assumption: For the DEL to GDL-III compilation, the authors assume that GDL-III games are sequentialized, meaning only one agent acts at a time. This simplifies the translation but might not cover all concurrent multi-agent scenarios.
  • Focus on Fragments: The paper focuses on "large fragments" of GDL-III and DEL. While this establishes equivalence for many practical cases, it doesn't claim full equivalence for all possible constructs.
  • Future Work: The authors suggest that their work paves the way for developing a combined description language that merges the best features of GDL-III and DEL. They also highlight the potential for transferring theoretical complexity results and solution concepts (like implicitly coordinated plans) between the two formalisms. The development of a unified language that offers both the simplicity of GDL-III's syntax and the semantic clarity of DEL is a significant future direction.

Summary updated

BibTeX
@inproceedings{engesser2018game,
  author = {Thorsten Engesser and Robert Mattmüller and Bernhard Nebel and Michael Thielscher},
  title = {{Game Description Language and Dynamic Epistemic Logic Compared}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/248},
}
Figure