Preferences and Constraints in Abstract Argumentation

Gianvincenzo Alfano, Sergio Greco, Francesco Parisi, Irina TrubitsynaIJCAI 2023 · DOI

TL;DR

This paper introduces a novel framework for abstract argumentation that allows for more expressive representation of preferences and constraints. By extending existing models to handle three-valued preferences (considering arguments as true, false, or undecided), the authors enable richer reasoning about agent beliefs and decision-making, while maintaining computational complexity comparable to simpler models.

What Problem Does This Paper Address?

Abstract Argumentation Frameworks (AFs), pioneered by Dung, provide a powerful way to model reasoning and decision-making through arguments and their conflicts. However, traditional AFs often struggle to capture nuanced preferences and constraints that agents might hold. For instance, an agent might not just prefer one argument over another, but might prefer a scenario where an argument is false (defeated) over a scenario where another argument is false. Existing extensions, like preference-based AFs (PAFs) and constrained AFs (CAFs), address parts of this, but often fall short. PAFs typically use binary preferences, and CAFs might not distinguish between an argument being false and undecided. This paper aims to bridge this gap by introducing a unified framework that handles three-valued preferences and constraints, allowing for more sophisticated modeling of agent reasoning, especially in multi-agent scenarios.

Methods

The core contribution is the introduction of an extended Preference-based AF (ePAF). This framework extends standard AFs by allowing preferences not just between arguments, but between an argument's status (true, false, or undecided) and another argument's status. For example, a_true > b_false means "argument 'a' being true is preferred to argument 'b' being false." This is a significant departure from traditional PAFs where preferences are typically between arguments themselves.

The authors then combine this with constraints, leading to an extended Preference-based Constrained AF (ePCAF). This framework allows for both three-valued preferences and three-valued constraints (e.g., phi => false, where phi is a propositional formula).

Finally, they extend this to a multi-agent ePCAF (mPCAF), where multiple agents share a common AF but have their own distinct constraints and preferences. This allows for modeling scenarios where different agents might have conflicting viewpoints or decision criteria.

The paper also rigorously analyzes the computational complexity of various reasoning tasks (verification, credulous acceptance, skeptical acceptance) within these new frameworks, comparing them to existing AF, CAF, and PAF models.

Datasets

Not discussed in the paper. The paper focuses on theoretical framework development and complexity analysis, using illustrative examples rather than empirical evaluation on datasets.

Key Insights and Ideas

  • Three-valued preferences are crucial for richer reasoning: The ability to express preferences over the truth status of arguments (true, false, undecided) unlocks a new level of expressiveness, allowing for more nuanced modeling of agent beliefs and desires than simple binary preferences.
  • Unified framework for preferences and constraints: Combining extended preferences with three-valued constraints in ePCAF offers a more compact and expressive way to represent complex agent knowledge compared to separate treatments.
  • Computational complexity remains manageable: Despite the increased expressiveness, the authors demonstrate that the computational complexity of key reasoning tasks in ePAF and ePCAF generally does not exceed that of existing, less expressive frameworks (like PAF under KTV criterion), often increasing by only one level in the polynomial hierarchy. This is a significant finding for practical applicability.
  • Multi-agent scenarios are well-handled: The extension to mPCAF shows that reasoning about multiple agents with diverse preferences and constraints doesn't necessarily lead to a computational explosion, with complexity bounds remaining comparable to single-agent ePCAF.

Key Results

The paper provides detailed complexity results for verification, credulous, and skeptical acceptance problems across different semantics (complete, stable, preferred, semi-stable) for ePAF, ePCAF, and mPCAF. A key finding is that for ePAF and ePCAF, the complexity of these problems generally matches or is only slightly higher than that of PAF under the KTV criterion, and in many cases, it does not increase compared to standard AFs. For instance, verification for ePAF is coNP-complete for complete/stable semantics and Π₁-complete for preferred/semi-stable semantics, which is comparable to PAF. The paper also shows that ePCAF is more expressive than CAF, particularly for credulous acceptance under preferred semantics, where it achieves Σ₁-completeness.

Limitations and Future Work

The authors acknowledge that while their frameworks are more expressive, the complexity analysis is crucial for understanding their practical feasibility. They suggest future work could explore preferences and constraints in other argumentation frameworks (e.g., bipolar AFs, AFs with necessities) and investigate other forms of constraints, such as weak and epistemic constraints. Additionally, they note that their current work focuses on fixed numbers of agents in mPCAF, and exploring scenarios with an arbitrary number of agents could be a direction for future research.

Summary updated

BibTeX
@inproceedings{alfano2023preferences,
  author = {Gianvincenzo Alfano and Sergio Greco and Francesco Parisi and Irina Trubitsyna},
  title = {{Preferences and Constraints in Abstract Argumentation}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/345},
}
Figure