TL;DR
This paper introduces a novel concept of "robustness" for evaluating the reliability of conclusions drawn from value-based argumentation systems (AVAFs). They define and analyze computational complexity for problems related to how many changes to an audience's preferences are needed to alter the outcome of an argument. This work is crucial for understanding the trustworthiness of AI systems that rely on user preferences.
What Problem Does This Paper Address?
Abstract Argumentation Frameworks (AAFs) are powerful tools for modeling disputes and reasoning. However, real-world scenarios often involve subjective viewpoints. Value-based Argumentation Frameworks (AVAFs) extend AAFs by incorporating an audience's preferences over social values, which in turn influences how arguments attack each other. The challenge addressed here is that the audience's preferences might not be perfectly captured or might change over time. This uncertainty can lead to unreliable conclusions. The authors propose a way to measure the "robustness" of an argument's status (whether it's accepted or not, or if a set of arguments forms an extension) by quantifying how many changes to the audience's preference profile are tolerable before the conclusion changes.
Methods
The core of the paper is the formalization of "robustness degree" for argument statuses. This is framed as a decision problem: given an AVAF, a specific argument status (e.g., a set of arguments being an extension), and an integer k, can we determine if the status remains unchanged even after up to k modifications (insertions or deletions) to the audience's preference specification?
They define four main k-robustness problems:
- RE (Robustness of Extension): Checking if a set S remains an extension.
- RNE (Robustness of Non-Extension): Checking if a set S remains a non-extension.
- RA (Robustness of Acceptance): Checking if an argument a remains accepted (credulously or skeptically).
- RNA (Robustness of Non-Acceptance): Checking if an argument a remains unaccepted.
They also introduce variants for "ins-only" and "del-only" updates, reflecting scenarios where the audience profile might become more specific or more general, respectively. The paper then delves into the computational complexity of these problems, using reductions from known hard problems to establish their complexity classes (e.g., P, NP, coNP). A key lemma proves that checking if a single attack can be deactivated with a limited number of preference deletions is in P, which is instrumental for proving tractability results.
Datasets
Not discussed in the paper. The paper focuses on theoretical analysis and complexity results rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- Quantifying Trustworthiness: The concept of robustness provides a concrete, quantitative measure of how reliable an argument's status is, given potential inaccuracies or changes in audience preferences. This moves beyond simply stating a conclusion to understanding its stability.
- Audience Profile Nuances: The paper highlights that how an audience's preferences are represented matters. Encoding preferences as a set versus a transitive closure leads to different robustness measures, as the former captures explicit beliefs more granularly.
- Complexity Trade-offs: The analysis reveals significant differences in computational complexity for various robustness problems and semantics. For instance, while some robustness problems are tractable (in P), others are hard (coNP-complete), indicating that assessing the stability of conclusions can be computationally demanding.
- Ins-only vs. Del-only: Differentiating between adding and removing preferences offers valuable insights into specific scenarios. For example, "del-only" robustness helps understand how stable a conclusion is if the audience's views become less restrictive.
Key Results
The paper provides a comprehensive complexity analysis of the defined k-robustness problems across different argumentation semantics (e.g., admissible, stable, complete). Key findings include:
- Tractability: Several robustness problems, particularly for "del-only" updates and certain semantics (like conflict-free or admissible), are shown to be in P (polynomial time). For example, RE-DO (robustness of extension with deletions only) is in P for cf, ad, st semantics.
- Hardness: Many other robustness problems are proven to be coNP-complete or NP-hard. For instance, RNE-DO (robustness of non-extension with deletions only) is coNP-complete for admissible semantics.
- Fixed-Parameter Tractability: For a constant number of social values, certain robustness problems become fixed-parameter tractable, meaning their complexity is manageable if the number of values is small, even if the number of arguments is large.
Limitations and Future Work
- Single Audience: The current framework focuses on a single audience. Future work aims to extend this to model multiple audiences and reason about robustness across them.
- Argument Values: Arguments currently promote a single value. The authors suggest extending the framework to handle arguments promoting multiple values.
- Preference Likelihood: The current model treats all preference updates equally. Future work could incorporate a weighted model to reflect the likelihood of certain preference changes.
- Gradual Semantics: The paper proposes defining new gradual semantics for AVAFs where acceptability degrees are derived from robustness degrees.
- Formal Proofs for Other Translations: While the complexity results are argued to hold for alternative translations of preferences to AAFs, formal proofs are left as future work.
Summary updated