Introduction
In classical Abstract Argumentation Frameworks (AAFs), arguments are nodes in a graph where edges represent attacks. While effective for basic conflict resolution, standard AAFs struggle with "meta-reasoning"—reasoning about the status of arguments across different possible outcomes (extensions). For instance, modeling statements like "Carol attends only if it is certain Alice attends" requires epistemic operators that standard AAFs lack.
Epistemic AAFs (EAAFs) were introduced to address this by incorporating strong epistemic attacks (based on credulous acceptance) and weak epistemic attacks (based on skeptical acceptance). However, prior semantics were restricted to acyclic graphs. This research, presented at IJCAI-24, removes that restriction, providing a complete semantics and complexity landscape for general EAAFs that allow for complex, cyclic reasoning about knowledge and belief.
The General EAAF Model
The core innovation lies in allowing cycles involving epistemic attacks. In these frameworks, an argument $a$ can defeat $b$ based on whether $a$ is "possibly" (credulously) or "certainly" (skeptically) accepted across a set of extensions.
Semantics via World Views
To handle cycles, the authors define a new declarative semantics centered on the concept of World Views. A world view is a collection of extensions where all "epistemic arguments" (those targeted by epistemic attacks) behave deterministically—meaning they maintain the same status across every extension within that specific view.
The evaluation process uses a "reduct" method ($\\Delta^\\tau$). By fixing the truth values of epistemic arguments based on a candidate assignment ($\\tau$), the EAAF is transformed into a standard AAF. If the resulting extensions of this AAF satisfy the original epistemic conditions, they form a valid world view. This approach allows for multiple distinct world views, mirroring "possible worlds" in modal logic, where each view represents a consistent interpretation of the epistemic constraints.
Complexity and Expressive Power
The transition from acyclic to general EAAFs significantly increases expressive power but also computational complexity. The paper provides an exhaustive complexity map across major semantics (grounded, complete, preferred, and stable).
Key findings include:
- Complexity Jumps: Reasoning in general EAAFs is notably harder than in standard AAFs. For example, the Verification problem for grounded semantics shifts from polynomial time (P) to coNP-complete.
- High-Level Complexity: Many problems for preferred semantics reside in the second or third levels of the polynomial hierarchy (e.g., $\\Theta^p_3$ or $\\Pi^p_3$), indicating that these frameworks are highly expressive but computationally demanding.
- Possible vs. Necessary: Because EAAFs can have multiple world views, the authors distinguish between Possible (true in at least one world view) and Necessary (true in all world views) variants of verification and acceptance.
Conclusion
This work provides a robust theoretical foundation for reasoning about beliefs in argumentative contexts. By generalizing EAAFs to cyclic structures, it enables the modeling of complex feedback loops in disputes. While the high complexity classes identified present an engineering challenge, the proposed "guess-and-check" algorithm provides a path forward for developing specialized solvers that can handle the expressive power of general EAAFs.
Summary updated