Tech Reports

ULCS-10-001

Tractability in Value-based Argumentation

Paul E. Dunne

Abstract

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.

For each technical report listed here, copyright and all intellectual property rights remain with the respective authors. Copyright is effective from the year of publication in each case. By downloading a file from this page, you agree to use it only for purposes of research and scholarship. Any other use of this material or storage of it in any medium or its sale or distribution in any form is expressly forbidden without prior written permission from the authors concerned.