Rejection in Abstract Argumentation: Harder Than Acceptance?

Authors:

Johannes K. Fichte、Markus Hecher、Yasir Mahmood、Arne Meier

Paper:

https://arxiv.org/abs/2408.10683

Introduction

Abstract argumentation is a cornerstone of artificial intelligence, providing a framework for modeling, evaluating, and comparing arguments. Traditionally, argumentation frameworks (AFs) focus on the acceptance of arguments based on certain conditions. However, real-world scenarios often require the rejection of arguments under specific conditions. This paper, titled “Rejection in Abstract Argumentation: Harder Than Acceptance?” by Johannes K. Fichte, Markus Hecher, Yasir Mahmood, and Arne Meier, explores the complexity and expressiveness of rejection conditions (RCs) in abstract argumentation frameworks.

Related Work

The study of argumentation frameworks has evolved significantly since Dung’s seminal work on AFs. Extensions such as Constrained Argumentation Frameworks (CAFs) and Abstract Dialectical Frameworks (ADFs) have introduced acceptance conditions to enhance expressiveness. However, the concept of rejection has not been explicitly addressed until now. This paper builds on the foundations of AFs, CAFs, ADFs, and Answer Set Programming (ASP) to introduce and analyze rejection conditions.

Research Methodology

The authors propose a novel approach to rejection in abstract argumentation by associating each argument with a specific logic program. This approach allows for flexible rejection conditions that can be more expressive than traditional acceptance conditions. The methodology involves:

1. Defining Rejection Conditions (RCs): Each argument is mapped to a constraint represented by an ASP program.
2. Analyzing Complexity: The complexity of decision and reasoning problems is analyzed, including the impact of structural parameters like treewidth.
3. Comparing with Existing Frameworks: The expressiveness and computational hardness of rejection conditions are compared with acceptance conditions in existing frameworks.

Experimental Design

The experimental design involves several key steps:

1. Framework Definition: The authors define Rejection Augmented Argumentation Frameworks (RCFs) as triples consisting of arguments, attack relations, and rejection conditions.
2. Semantics Extension: The semantics of traditional AFs are extended to incorporate rejection conditions, ensuring that RCs must be invalidated for an extension to be valid.
3. Simulation of Existing Frameworks: The authors demonstrate that RCFs can simulate AFs and CAFs, providing a more general understanding of rejection and acceptance.
4. Complexity Analysis: The complexity of various decision and reasoning problems is analyzed, with a focus on the impact of treewidth.

Results and Analysis

The results of the study are summarized in Table 1, which provides an overview of the complexity results for different classes of programs and rejection conditions. Key findings include:

1. Increased Complexity: Rejection conditions are generally harder to express than acceptance conditions, often increasing computational hardness by one level in the polynomial hierarchy.
2. Treewidth Considerations: The inclusion of treewidth in the complexity analysis provides matching runtime upper and lower bounds, highlighting the impact of structural parameters on computational complexity.
3. Expressiveness: RCFs are shown to be more expressive than AFs and CAFs, capable of modeling scenarios that cannot be captured by traditional frameworks.

Overall Conclusion

The study provides valuable insights into the complexity and expressiveness of rejection conditions in abstract argumentation. The main contributions include the introduction of flexible rejection conditions, a detailed complexity analysis, and the demonstration of RCFs’ expressiveness. The findings suggest that rejection is indeed harder than acceptance in abstract argumentation, with significant implications for the design and analysis of argumentation frameworks.

Future work could explore additional semantics and rejection conditions, as well as the implementation and performance comparison of RCFs with existing AF solvers. The study opens up new avenues for research in abstract argumentation, particularly in scenarios where rejection plays a crucial role.