A Study of Unrestricted Abstract Argumentation Frameworks

Ringo Baumann, Christof SpanringIJCAI 2017 · DOI

TL;DR

This paper extends the study of abstract argumentation frameworks (AFs) from finite to unrestricted (potentially infinite) settings. It reveals significant differences in properties like SCC-recursiveness, expansion equivalence, and intertranslatability, highlighting the need for a more general theoretical foundation for argumentation systems.

What Problem Does This Paper Address?

Formal argumentation, a key area in AI for modeling reasoning and decision-making, has largely focused on finite argumentation frameworks (AFs). These AFs are essentially directed graphs where nodes represent arguments and edges represent attacks. While this finite assumption simplifies analysis, many real-world applications, such as nonmonotonic reasoning, multi-agent dialogues, and modeling complex systems, naturally lead to potentially infinite sets of arguments. This paper addresses the gap by systematically analyzing fundamental properties of abstract argumentation in the unrestricted case, where the number of arguments can be infinite. The authors argue that this is crucial for a deeper understanding of argumentation theory and for developing more robust AI systems.

Methods

The paper delves into several key properties of abstract argumentation frameworks:

  • Existence and Uniqueness of Extensions: Building on Dung's foundational work, the authors analyze whether semantics guarantee at least one extension or a unique extension in the unrestricted setting.
  • SCC-Recursiveness: This property is crucial for decomposing AFs and incrementally computing semantics. The paper investigates how SCC-recursiveness behaves in the presence of infinite AFs, where initial SCCs might not exist or recursion might not terminate.
  • Subset Relations between Semantics: The paper examines how the hierarchical relationships between different argumentation semantics (e.g., is the set of preferred extensions always a subset of the set of stable extensions?) change when moving from finite to unrestricted AFs.
  • Expansion Equivalence: This concept captures a stronger form of equivalence than just having the same extensions, ensuring that two AFs behave identically even when augmented with other frameworks. The authors investigate whether syntactic characterizations (kernels) that work for finite AFs still hold for unrestricted ones.
  • Intertranslatability: This property concerns the ability to translate one argumentation semantics into another using functions that map AFs to AFs. The paper explores exact and faithful translations and their limitations in the unrestricted setting.

The methodology involves theoretical analysis, proving theorems, and providing counterexamples to illustrate differences between finite and unrestricted AFs.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis of abstract structures rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Infinite AFs are Not Just an Academic Exercise: The paper strongly emphasizes that infinite AFs arise naturally in practical AI applications, making their study essential, not just a theoretical pursuit.
  • Finite vs. Infinite: A Crucial Distinction: Many properties that hold for finite AFs break down or behave differently in the unrestricted case. This necessitates a re-evaluation of existing theoretical results.
  • SCC-Recursiveness is Fragile: While SCC-recursiveness is a powerful tool for finite AFs, infinite AFs can break this property, leading to non-termination or undefinedness for certain semantics (e.g., cf2 and stg2 are SCC-recursive by definition but not well-defined in the general unrestricted case).
  • Expansion Equivalence is More Sensitive: The notion of expansion equivalence, which is syntactically decidable for finite AFs via kernels, becomes more complex. The paper shows that regularity (a property of finite AFs) can fail, and syntactic characterizations may not hold without additional assumptions like "jointly expandable" frameworks.
  • Intertranslatability is Severely Limited: The ability to translate between semantics, a useful tool for reusing solvers, is significantly restricted in the unrestricted case. Exact translations are often impossible, even for seemingly related semantics.
  • "Fresh" Arguments Matter: The concept of "fresh" arguments (arguments not present in the original framework) plays a crucial role in bridging the gap between finite and unrestricted AFs for certain properties like expansion equivalence.

Key Results

  • Semantics Behavior Changes: Table 1 and Table 2 show that properties like existence, uniqueness, and SCC-recursiveness differ significantly between finite and unrestricted AFs for various semantics (e.g., naive, stable, preferred).
  • SCC-Recursive Semantics: While most standard semantics are not SCC-recursive in the unrestricted case, cf2 and stg2 are SCC-recursive by definition, though they may not be well-defined.
  • Subset Relations Persist (Mostly): Many subset relations between semantics (e.g., grounded is a subset of preferred) carry over to the unrestricted case, but some key distinctions emerge (e.g., Σpr \ (Estb U Σss U Σstg) ≠ 0).
  • Expansion Equivalence Challenges: Theorem 3, which characterizes expansion equivalence via kernels for finite AFs, does not hold in general for unrestricted AFs. However, Theorem 4 shows that if frameworks are "jointly expandable" (meaning there are fresh arguments available), some of these characterizations can be restored.
  • Intertranslatability Limitations: Theorem 8 and Theorem 9 provide some exact translation results, but the paper highlights many cases where exact translations are impossible, particularly for semantics like stable and preferred. Figure 3 illustrates these intertranslatability relationships, showing fewer bidirectional translations in the unrestricted case.

Limitations and Future Work

  • Omitted Proofs: Due to space constraints, the paper omits proofs for most theorems, which would be necessary for a full understanding of the results.
  • Unsolved Characterization Problems: Table 3 indicates that for some semantics, the problem of finding a characterizing kernel for expansion equivalence in the unrestricted case remains unsolved.
  • Further Exploration of "Fresh" Arguments: The paper suggests that exploring the role of "fresh" arguments could help restore some properties in the unrestricted setting, a direction for future work.
  • Alternative Characterizations: Investigating alternative, non-recursive characterizations for semantics like cf2 and stg2 is proposed as a way to overcome undefinedness issues.
  • Logic Program Connections: The paper notes the connection between AFs and logic programs and suggests exploring how results for infinite AFs might inform the study of infinite logic programs.
  • Venn Diagrams for Intersections: The paper mentions that some intersections in the Venn diagrams for signatures are left open, indicating areas for further investigation.

Summary updated

BibTeX
@inproceedings{baumann2017study,
  author = {Ringo Baumann and Christof Spanring},
  title = {{A Study of Unrestricted Abstract Argumentation Frameworks}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/112},
}

Loading related content...

Figure