On the Learnability of Knowledge in Multi-Agent Logics

Ionela G. MocanuIJCAI 2021 · DOI

TL;DR

This paper proposes a new multi-agent logic for reasoning about beliefs in complex scenarios, aiming for computational tractability. By adopting a "subjective" viewpoint from a single agent and limiting the expressiveness of knowledge representation, the authors pave the way for efficient learning and reasoning in multi-agent systems.

What Problem Does This Paper Address?

Traditional knowledge engineering for multi-agent systems (MAS) is incredibly challenging. While machine learning offers an alternative, most systems focus on single agents. Real-world MAS, however, involve multiple agents coordinating or competing, requiring agents to reason about the knowledge and beliefs of others. Existing formal logics for MAS, like epistemic logics, are often computationally expensive (e.g., PSPACE-complete for entailment checking). While some approaches offer polynomial-time solutions, they impose strict limitations on the form of knowledge representation, often excluding crucial aspects like "knowing whether" or handling disjunctions effectively. This paper tackles the problem of achieving computationally tractable reasoning in multi-agent systems while still capturing nuanced beliefs and knowledge.

Methods

The authors propose a "multi-agent subjective language" (MSL) that reasons from the perspective of a single "root agent" (*). This agent is considered omniscient and reasons about the beliefs of other agents. The core idea is to shift focus from "knowledge" to "belief" and to adopt a perspectival view. The MSL extends propositional logic with belief atoms of the form $B^k_\phi$, representing that agent $A$ believes $\phi$ at level $k$. A key aspect is that modalities can be nested up to a bounded degree $d$. This approach aims to combine the computational efficiency of Subjective Logic with the expressiveness of multi-agent reasoning, specifically by handling partial information and avoiding the "logical omniscience" problem of standard possible-world logics.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Subjectivity for Tractability: Reasoning from a single agent's perspective, rather than a global one, is a key strategy to reduce computational complexity.
  • Belief over Knowledge: Focusing on beliefs rather than absolute knowledge allows for more realistic modeling of agent states and can be more computationally manageable.
  • Bounded Nesting: Limiting the depth of nested beliefs ($d$) is a crucial constraint that enables polynomial-time complexity, offering a trade-off between expressiveness and efficiency.
  • Bridging the Gap: The proposed logic aims to bridge the gap between computationally intractable but highly expressive logics and overly simplified logics that lack practical reasoning power.

Key Results

The paper presents a theoretical framework for a multi-agent logic of belief. The authors demonstrate that by restricting knowledge bases to conjunctions of modal literals and by using a subjective viewpoint with bounded modal depth, polynomial-time learnability results can be achieved. The primary outcome is the proposal of a formal framework that is sound and complete for reasoning in this multi-agent modal logic, with the goal of achieving polynomial guarantees.

Limitations and Future Work

The authors acknowledge that the proposed subjective multi-agent logic has limitations in its range of possible applications due to the restricted perspective of the root agent. Future work involves integrating this logic with limited belief reasoning systems to achieve a tractable reasoning system. The ultimate success criterion is the development of a sound and complete reasoning algorithm for this multi-agent modal logic that exhibits polynomial guarantees. The formal framework itself is still under development.

Summary updated

BibTeX
@inproceedings{mocanu2021learnability,
  author = {Ionela G. Mocanu},
  title = {{On the Learnability of Knowledge in Multi-Agent Logics}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/685},
}
Figure