Tech Reports


Tractability in Value-based Argumentation

Paul E. Dunne


Value-based argumentation frameworks (VAFs) have proven to be a useful development of Dung's seminal model of argumentation in providing a rational basis for distinguishing mutually incompatible yet individually acceptable sets of arguments. In classifying argument status within value-based frameworks two main decision problems arise: subjective acceptance (SBA) and objective acceptance (OBA). These problems have proven to be somewhat resistant to efficient algorithmic approaches (the general cases being NP-complete and coNP-complete) even when very severe limitations are placed on the structure of the supporting Dung-style framework. Although using the number of values (k) represented within a given VAF leads to fixed parameter tractable (FPT) methods, these are not entirely satisfactory: the rate of growth of the parameter function (k!) making such methods unacceptable in cases where k is moderately large, e.g. k>=20. In this paper we consider an alternative approach to the development of practical algorithms in value-based argumentation. In particular cases this leads to polynomial (in |X|) methods, i.e. irrespective of the value of k. More general examples are shown to be decidable in O(f(k)|X|^2) steps where f(k)=o(k!) resulting in worst-case run times that significantly improve upon enumerating all value orderings.

[Full Paper]