Abstract
A gradual semantics takes a weighted argumentation framework as input and outputs a final acceptability degree for each argument, with different semantics performing the computation in different manners. In this work, we consider the problem of attack inference. That is, given a gradual semantics, a set of arguments with associated initial weights, and the final desirable acceptability degrees associated with each argument, we seek to determine whether there is a set of attacks on those arguments such that we can obtain these acceptability degrees. The main contribution of our work is to demonstrate that the associated decision problem, i.e., whether a set of attacks can exist which allows the final acceptability degrees to occur for given initial weights, is NP-complete for the weighted h-categoriser and card-based semantics, and is polynomial for the weighted max-based semantics, even for the complete version of the problem (where all initial weights and final acceptability degrees are known). We then briefly discuss how this decision problem can be modified to find the attacks themselves and conclude by examining the partial problem where not all initial weights or final acceptability degrees may be known.
Original language | English |
---|---|
Pages (from-to) | 327-345 |
Number of pages | 19 |
Journal | Argument and Computation |
Volume | 14 |
Issue number | 3 |
DOIs | |
Publication status | Published - 7 Nov 2023 |
Data Availability Statement
An implementation of our algorithms using an optimised depth-first-search SSP solver can be found at https://github.com/jhudsy/Gradual_Attack_Inference. We do not provide experimental data as the performance of our solver demonstrates the exponential growth of the underlying subset-sum problem. Systems with more than ∼13 arguments can only rarely be solved in reasonable time using our implementation.Keywords
- Gradual Semantics
- Argumentation
- Complexity
- complexity
- argumentation
- Gradual semantics