TL;DR
This paper introduces a new framework, AFP2, that unifies preferences between individual arguments and priority rules between entire sets of arguments. This allows for a more expressive and flexible way to reason about argumentation, capturing existing semantics and enabling new ones, with a focus on understanding the complexity of these reasoning problems.
What Problem Does This Paper Address?
Dung's abstract argumentation frameworks (AFs) provide a powerful way to model reasoning as a system of arguments and attacks. However, real-world arguments often involve nuances like the relative strength of arguments or explicit rules about which conclusions should be preferred. Existing extensions to AFs, like Preference-based Argumentation Frameworks (PAFs), address preferences between arguments, but can sometimes lead to counterintuitive results. Other approaches introduce priority rules between extensions, but these can be complex to manage. This paper aims to bridge this gap by proposing a unified framework that elegantly combines both preferences between arguments and explicit priority rules between sets of arguments, offering a more expressive and computationally tractable approach to abstract argumentation.
Methods
The paper builds upon existing work in abstract argumentation and preference-based argumentation. They introduce two main novelties:
- Cardinality-Based Semantics: They propose new semantics for AFs (cardinality preferred (c-pr) and cardinality semi-stable (c-ss)) that refine existing set-inclusion based semantics (preferred and semi-stable). Instead of just comparing sets of arguments by inclusion, these new semantics consider the cardinality of arguments within extensions, allowing users to prefer solutions with more or fewer arguments.
- AF with Priority Rules (AFP) and AFP2: They introduce a framework called AFP that extends AFs with sequences of priority rules. These rules allow for explicit ordering of extensions based on various criteria. Crucially, they then extend AFP to AFP2 by incorporating preferences between individual arguments (from PAFs) into the priority rules. This allows for a unified way to express preferences at both the argument and extension level. They also analyze the computational complexity of reasoning problems (verification, credulous, and skeptical acceptance) within these new frameworks.
Datasets
Not discussed in the paper. The paper focuses on theoretical frameworks and their properties, not empirical evaluation on specific datasets.
Key Insights and Ideas
- Unifying Preferences: The core insight is that preferences between individual arguments and explicit priority rules between sets of arguments are not mutually exclusive but can be elegantly combined into a single framework (AFP2). This unification simplifies reasoning and increases expressiveness.
- Cardinality as a Preference Criterion: The introduction of cardinality-based semantics (c-pr, c-ss) highlights that preferences can be based not just on the presence or absence of arguments, but also on the size of the accepted set of arguments, offering a more nuanced way to select "optimal" solutions.
- Complexity Trade-offs: The paper systematically analyzes the computational complexity of reasoning problems in their new frameworks. They show that while some problems might increase in complexity compared to basic AFs, others (like credulous and skeptical acceptance under cardinality semantics) become easier, suggesting a potential benefit for practical applications.
- Semantics as Priority Rules: A key conceptual idea is that existing argumentation semantics (like grounded, preferred, stable) can be viewed as specific instances of priority rules within the AFP framework. This provides a unifying perspective on different semantics.
Key Results
- Complexity Analysis: The paper provides detailed complexity results for verification, credulous, and skeptical acceptance problems for PAFs and their new AFP and AFP2 frameworks. For instance, they show that for PAFs, these problems generally increase by one level in the polynomial hierarchy compared to basic AFs. For cardinality-based semantics, credulous and skeptical acceptance become easier (e.g., $\Sigma_2$-complete to $\Delta_2$-complete).
- Expressiveness: AFP2 is shown to be capable of capturing existing PAF semantics and novel ones, demonstrating its expressiveness.
- Relationships between Semantics: Proposition 2 clearly outlines the relationships between cardinality-based semantics (c-pr, c-ss) and classical semantics (st, ss, pr), showing how they refine or relate to each other.
Limitations and Future Work
- Transitivity of Priority Rules: The paper explicitly states that they do not consider the transitive closure of priority rules by default, as it can lead to an exponential blow-up in the number of rules. However, they note that transitivity can be explicitly included if needed.
- Bounded Variables in Rules: The complexity analysis assumes that the number of variables in the body of priority rules is bounded by a constant. While this is often practical, it's a simplification.
- Future Work: The authors suggest several avenues for future research:
- Investigating the connection between their framework and other existing formalisms like value-based AFs and weighted attacks.
- Exploring the relationship between AFP2 and ranking semantics.
- Applying their framework to structured argumentation formalisms.
- Developing ASP implementations for their AFP semantics.
- Investigating preferences in incomplete AFs, probabilistic AFs, and AFs with constraints.
Summary updated