Formal Analysis of Dialogues on Infinite Argumentation Frameworks

Francesco Belardinelli, Davide Grossi, Nicolas Maudet

Abstract

The paper analyses multi-agent strategic dialogues on possibly infinite argumentation frameworks. We develop a formal model for representing such dialogues, and introduce FOA-ATL, a first-order extension of alternating-time logic, for expressing the interplay of strategic and argumentation-theoretic properties. This setting is investigated with respect to the model checking problem, by means of a suitable notion of bisimulation. This notion of bisimulation is also used to shed light on how static properties of argumentation frameworks influence their dynamic behaviour.

Introduction

Abstract argumentation, pioneered by Phan Minh Dung, typically focuses on static graphs where nodes represent arguments and edges represent attack relations. However, real-world debates—such as legal proceedings or scientific disputes—are inherently dynamic and strategic. Agents do not reveal their entire knowledge base at once; instead, they take turns introducing arguments to influence a shared public record. Furthermore, many applications cannot assume a finite limit on the number of possible arguments. This paper addresses the challenge of formally verifying properties of these infinite-state, multi-agent dialogues.

Dynamic Argumentation Systems and FOA-ATL

To model these interactions, the authors introduce Dynamic Argumentation Systems (DAS). In a DAS, agents (typically a Proponent and an Opponent) possess private views of an argumentation framework and interact by expanding a public framework.

To reason about these systems, the authors develop $FO_A\text{-ATL}$ (First-Order Argumentation Alternating-time Temporal Logic). This logic extends standard ATL with first-order quantification, allowing it to express properties over an infinite set of arguments. For instance, it can specify that an agent has a strategy to ensure the public record remains conflict-free or that a specific argument remains defended regardless of the opponent's moves.

An example of an infinite argumentation framework represented as a chain of arguments.

Bisimulation and Verification

A major hurdle in verifying infinite-state systems is the "state explosion" problem. The authors tackle this by defining notions of Static and Dynamic Bisimulation. These mathematical tools identify when two dialogue states are functionally equivalent. The paper proves that if two states are dynamically bisimilar, they satisfy the same strategic properties in $FO_A\text{-ATL}$, enabling significant state-space reduction for model checking. This is a crucial result for the formal verification of dialogue protocols.

Key Insights: Static vs. Dynamic Properties

A critical finding is that static equivalence of argument graphs does not necessarily imply dynamic equivalence of the dialogues played upon them. Two frameworks might appear identical (statically bisimilar), but the private knowledge of agents or the specific dialogue protocols can lead to diverging outcomes as the debate progresses.

Illustration of how two statically bisimilar argumentation frameworks can diverge during a dialogue sequence.

However, the authors identify a special case: "naive" agents who play any valid move available to them. For these agents, if the underlying graphs are Directed Acyclic Graphs (DAGs), the static structure is sufficient to predict dynamic behavior. This provides a "reduction" that simplifies the verification of systems involving less cunning participants.

Conclusion

By bridging argumentation theory and formal verification, this work provides a rigorous foundation for analyzing strategic debates. The introduction of $FO_A\text{-ATL}$ and the associated bisimulation techniques offer a path toward verifying complex, infinite-state multi-agent systems. While the current model focuses on two-player games and often assumes naive agents for decidability, it sets the stage for future research into multiparty protocols and more sophisticated, strategic agent behavior.

Summary updated

Abstract

The paper analyses multi-agent strategic dialogues on possibly infinite argumentation frameworks. We develop a formal model for representing such dialogues, and introduce FOA-ATL, a first-order extension of alternating-time logic, for expressing the interplay of strategic and argumentation-theoretic properties. This setting is investigated with respect to the model checking problem, by means of a suitable notion of bisimulation. This notion of bisimulation is also used to shed light on how static properties of argumentation frameworks influence their dynamic behaviour.
BibTeX
@inproceedings{belardinelli2015formal,
  author = {Francesco Belardinelli and Davide Grossi and Nicolas Maudet},
  title = {{Formal Analysis of Dialogues on Infinite Argumentation Frameworks}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
  url = {https://openreview.net/forum?id=Sy-ZNNGuZB},
}
Figure