Computational complexity theory and the related area of efficient algorithms have formed significant subfields of Abstract Argumentation going back over 20 years. There have been major contributions and an increased understanding of the computational issues that influence and beset effective implementation of argument methods. My aim, in this article, is to attempt to take stock of the standing of work in complexity theory as it presently is within the field of Computational Argument, as well as offering some personal views on its future direction.

Abstract An abstract argumentation framework is a directed graph $(V,E)$ such that the vertices of $V$ denote abstract arguments and $E \subseteq V \times V$ represents the attack relation between them. We present a new ad hoc algorithm for computing the grounded extension of an abstract argumentation framework. We show that the new algorithm runs in $\mathcal{O}(|V|+|E|)$ time. In contrast, the existing state-of-the-art algorithm runs in $\mathcal{O}(|V|+|S||E|)$ time where $S$ is the grounded extension of the input graph.

The concept of strong admissibility plays an important rolein some of the dialectical proof procedures that have been stated forgrounded semantics. As the grounded extension is the (unique) biggeststrongly admissible set, to show that an argument is in the groundedextension it suffices to show that it is in a strongly admissible set. Weare interested in identifying a strongly admissible set that minimizes thenumber of steps needed in the associated dialectical proof procedure. Inthe current work, we look at the computational complexity of doing so.

In the context of abstract argumentation frameworks, the admissibility problem is about deciding whether a given argument (i.e. piece of knowledge) is admissible in a conflicting knowledge base. In this paper we present an enhanced backtracking-based algorithm for solving the admissibility problem. The algorithm performs successfully when applied to a wide range of benchmark abstract argumentation frameworks and when compared to the state-of-the-art algorithm.

We consider a long-established approach to text analysis applying it to the specific structure of oratory and spoken arguments. This method consists of deriving measures of the so-called “Fractal dimension”. Building on previous work linking “aesthetic appeal” to fractal dimensions of a particular value from the fields of music and literary study, we present empirical analyses of a number of different “persuasive texts” against a range of different choices for determining fractality. Initial results suggest that distinctive “oratorical aims” as may be represented in a text become evident via distinctive fractal dimension.

Spectral analysis – the study of the properties of the eigenvalues associated with some matrix derived from an underlying graph form – has proven to offer valuable insights in many domains where graph-theoretic models are prevalent. Abstract argumentation frameworks (afs) are, of course, one such model and have provided a unifying basis for defining semantic properties related to concepts of “argument acceptability”. In this paper we consider the possible benefits of adopting spectral methods as a tool for analysing argumentation structures, presenting a preliminary empirical study of semantics in afs and properties of the associated spectrum.

One often finds in debate involving agents strongly committed to their positions, that argument is promoted not through a rational measured exchange of views but rather through stridency and clamour as proponents try to shout down or otherwise suppress their opponents' opinions. While the presence of moderators may go some way to alleviating the effects of such approaches one has the problems of moderators being ignored and the environment being of a nature that makes the appointment of such infeasible. In this article our concern is, in the first instance, to examine the extent to which an environment where argument is pursued through these means can be modelled. Within this model, we briefly review what techniques may be adopted by participants looking to present their own stance with minimal effort and maximal impact.

Within characteristic function games, agents have the option of joining one of many different coalitions, based on the utility value of each candidate coalition. However, determining this utility value can be computationally complex since the number of coalitions increases exponentially with the number of agents available. Various approaches have been proposed that mediate this problem by distributing the computational load so that each agent calculates only a subset of coalition values. However, current approaches are either highly inefficient due to redundant calculations, or make the benevolence assumption (i.e. are not suitable for adversarial environments). We introduce DCG, a novel algorithm that distributes the calculations of coalition utility values across a community of agents, such that: (i) no inter-agent communication is required; (ii) the coalition value calculations are (approximately) equally partitioned into shares, one for each agent; (iii) the utility value is calculated only once for each coalition, thus redundant calculations are eliminated; (iv) there is an equal number of operations for agents with equal sized shares; and (v) an agent is only allocated those coalitions in which it is a potential member. The DCG algorithm is presented and illustrated by means of an example. We formally prove that our approach allocates all of the coalitions to the agents, and that each coalition is assigned once and only once.

In an abstract argumentation framework, there are often multiple plausible ways to evaluate (or label) the status of each argument as accepted, rejected, or undecided. But often there exists a critical set of arguments whose status is sufficient to determine uniquely the status of every other argument. Once an agent has decided its position on a critical set of arguments, then essentially the entire frame-work has been evaluated. Likewise, once a group, e.g. a jury, agrees on the status of a critical set of arguments, all of their different views over all other arguments are resolved. Thus, critical sets of arguments are important both for efficient evaluation by individual agents and for collective agreement by groups of such. To exploit this idea in practice, however, a number of computational questions must be considered. In particular, how much computational effort is needed to verify that a set is, indeed, a critical set or a minimal critical set. In this paper we determine exact bounds on the computational complexity of these and related questions. In addition we provide similar analyses of issues: a concept closely related to critical set and derived in terms of (equivalence) classes of arguments related through “common” labelling behaviours.

By gaining insight into the structure and behaviours of objects drawn at random from a general class, it is often possible to develop algorithms and techniques which ameliorate the computational difficulty of decision questions arising in the general case. In this paper we present a number of approaches for the random generation of value-based argumentation frameworks (VAFs) built on n arguments and using k values. Via an empirical study we consider the behaviour of the associated random VAFs with respect to the issue of how many arguments within them have the property of being “objectively accepted”. Our studies indicate that the property of having no objectively accepted argument exhibits a so-called “phasetransition effect”, similar in nature to those observed in many other well-established AI studies.

A Dung argumentation framework (AF) is a pair (A,R): A is a set of abstract arguments and R ⊆ A×A is a binary relation, so-called the attack relation, for capturing the conflicting arguments. Labeling based algorithms for enumerating extensions (i.e. sets of acceptable arguments) have been set out such that arguments (i.e. elements of A) are the only subject for labeling. In this paper we present implemented algorithms for listing extensions by labeling attacks (i.e. elements of R) along with arguments. Specifically, these algorithms are concerned with enumerating all extensions of an AF under a number of argumentation semantics: preferred, stable, complete, semi stable, stage, ideal and grounded. Our algorithms have impact, in particular, on enumerating extensions of AF-extended models that allow attacks on attacks. To demonstrate this impact, we instantiate our algorithms for an example of such models: namely argumentation frameworks with recursive attacks (AFRA), thereby we end up with unified algorithms that enumerate extensions of any AF/AFRA.

We introduce a derivative of Dung's seminal abstract argumentation frameworks (afs) through which distinctive features both of Dung's semantics and so-called “value-based” argumentation frameworks (vafs) may be captured. These frameworks, which we describe as uniform afs, thereby recognise that, in some circumstances, arguments may be deemed acceptable, not only as a consequence of subjective viewpoints (as are modelled by the concept of audience in vafs) but also as a consequence of “value independent” acceptance of other arguments: for example in the case of factual statements. We analyse divers acceptability conditions for arguments in uniform afs and obtain a complete picture for the computational complexity of the associated decision questions. Amongst other results it is shown that reasoning in uniform afs may pose significantly greater computational challenges than either standard or value-based questions, a number of problems being complete for the third level of the polynomial hierarchy.

Argument aggregation is the problem of combining argumentation frameworks. An argument aggregation procedure takes as input an argument framework for each agent in a system, intuitively representing the beliefs of that agent with respect to a disputed domain of discourse; the output is an argumentation framework that represents the social position on the domain of discourse. There are clear analogies between argument aggregation and the well-known preference aggregation problem, which has been extensively studied in the social choice community. The first contribution of this paper is to apply some of the methodology developed in social choice theory to argument aggregation. After recalling the basic framework of Dung's abstract argument systems, and introducing the argument aggregation problem, we motivate and formally define a collection of axioms that specific argument aggregation procedures might or might not satisfy. The second contribution of the paper is to consider the analysis of argument aggregation procedures with respect to these various axioms. We consider a natural representation for argument aggregation procedures, based on Boolean circuits. We then investigate the problem of verifying whether an argument aggregation procedure, presented in this way, does or does not satisfy a number of the axioms we introduced.

For Dung's theory of abstract argumentation, algorithms have been introduced for enumerating all preferred extensions. Two specific approaches have been set out that are based on labeling arguments as: IN, OUT or UNDEC. The purpose of this paper is to improve the two existing approaches by introducing two enhancements. Firstly, we employ two more informative labels. Secondly, by using these additional labels, we describe a new scheme for how the arguments' labels change in the course of computing the preferred extensions. Supported by empirical evaluation, we argue that these modifications accelerate computations. Moreover, we show how to apply the new algorithm in the context of value-based frameworks for persuasive argument, and hence, it appears that the new algorithm is usable in other formalisms extending Dung's model.

From theoretical computational perspectives, decision problems in Dung's abstract argumentation frameworks (AFs) are either polynomial solvable or intractable. To investigate practical efficiency, theoretical evaluation of applied algorithms does not necessarily reveal performance dissimilarities. Although experimental analysis of algorithms is a well-established alternative exploited in other domains, such methodology is given a little attention in the context of AFs. The main purpose of this paper is to give an example of how such experiments can be conducted to get meaningful conclusions about algorithms' behavior in situations where theoretical analysis might be of little help. To this end, we pick an extended model of AFs as a case study to empirically examine the efficiency of algorithms related to the acceptability of arguments.

In this article, we examine an argument-based semantics called semi-stable semantics. Semi-stable semantics is quite close to traditional stable semantics in the sense that every stable extension is also a semi-stable extension. One of the advantages of semi-stable semantics is that for finite argumentation frameworks there always exists at least one semi-stable extension. Furthermore, if there also exists at least one stable extension, then the semi-stable extensions coincide with the stable extensions. Semi-stable semantics can be seen as a general approach that can be applied to abstract argumentation, as well as to fields like default logic and answer set programming, yielding an interpretation with properties very similar to those of paraconsistent logic, including the properties of crash resistance and backward compatibility.

One criticism often advanced against abstract argumentation frameworks (AFs), is that these consider only one form of interaction between atomic arguments: specifically that an argument attacks another. Attempts to broaden the class of relationships include bipolar frameworks, where arguments support others, and abstract dialectical frameworks (ADFs). The latter, allow of an argument, x, to be predicated on a given propositional function, Cx, dependent on the corresponding acceptance of its parents, i.e. those y for which 〈y, x〉 occurs. Although offering a richly expressive formalism subsuming both standard and bipolar AFs, an issue that arises with ADFs is whether this expressiveness is achieved in a manner that would be infeasible within standard AFs. Can the semantics used in ADFs be mapped to some AF semantics? How many arguments are needed in an AF to simulate an ADF? We show that (in a formally defined sense) any ADF can be simulated by an AF of similar size and that this translation can be realised by a polynomial time algorithm.

The concept of “ideal semantics” has been promoted as an alternative basis for skeptical reasoning within abstract argumentation settings. Informally, ideal acceptance not only requires an argument to be skeptically accepted in the traditional sense but further insists that the argument is in an admissible set all of whose arguments are also skeptically accepted. The original proposal was couched in terms of the so-called preferred semantics for abstract argumentation. We argue, in this paper, that the notion of “ideal acceptability” is applicable to arbitrary semantics and justify this claim by showing that standard properties of classical ideal semantics, e.g. unique status, continue to hold in any “reasonable” extension-based semantics. We categorise the relationship between the divers concepts of “ideal extension wrt semantics σ” that arise and we present a comprehensive analysis of algorithmic and complexity-theoretic issues.

Given a Boolean propositional formula, φ(Xn) over the basis Ω = {∧, V, ¬}, we consider the following decision problem: is there a subset of literals, S, for which φ(Xn) ≡ ∧y∈Sy or φ(Xn) ≡ ⋁y∈Sy? We prove that the ‘obvious’ Σ2p upper bound is suboptimal and that the problem is decidable in P‖NP the class of languages decidable by polynomial time methods allowed to make non-adaptive queries to an np oracle. We further show that the associated function problem of computing a witnessing such subset when one exists can be solved in FP‖NP.

We consider the problem of counting (without explicitly enumerating) extensions prescribed by multiple-status semantics in abstract argumentation. Referring to Dung's traditional stable and preferred semantics and to the recently introduced resolution-based grounded semantics (GR*), we show that in general extension counting is computationally hard (actually #P-complete). We then identify non-trivial topological classes of argumentation frameworks where extension counting is tractable. In particular we show, by providing and analyzing the relevant algorithms, that in symmetric argumentation frameworks counting GR* extensions is tractable (but is still hard for stable and preferred estensions), while counting is tractable for all the considered semantics in tree-like argumentation frameworks.

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 |χ|) methods, i.e. irrespective of the value of k. More general examples are shown to be decidable in O(f(k)|χ|2) steps where f(k)=o(k!) resulting in worst-case run times that significantly improve upon enumerating all value orderings.

In abstract frameworks with varied strength attacks (AFV), arguments may attack each other with different strength. An admissible scenario is an admissible set of arguments fulfilling certain strength conditions about defences. In this work we analyze the computational complexity of some decision problems related to the quality of admissible scenarios: checking the property of being top-admissible and the property of being equilibrated. These problems are implying an exhaustive comparison between scenarios, and both of them are shown to be coNP-complete.

Our focus in this paper is to explore how emotional factors can complement rationality in decision making. Our approach is to develop a model of the situation and use this model to generate arguments for and against the actions that an agent can perform. Actions are then chosen by evaluating this set of arguments according to the subjective preferences and emotional state of the agent concerned. A mechanism to control and balance the extent of emotional effects is also introduced. We illustrate our approach with an extended case study based on an implemented system embodying this approach.

We examine properties of a model of resource allocation in which several agents exchange resources in order to optimise their individual holdings. The schemes discussed relate to well-known negotiation protocols proposed in earlier work and we consider a number of alternative notions of ``rationality'' covering both quantitative measures, e.g. cooperative and individual rationality and more qualitative forms, e.g. Pigou-Dalton transfers. While it is known that imposing particular rationality and structural restrictions may result in some reallocations of the resource set becoming unrealisable, in this paper we address the issue of the number of restricted rational deals that may be required to implement a particular reallocation when it is possible to do so. We construct examples showing that this number may be exponential (in the number of resources m), even when all of the agent utility functions are monotonic. We further show that k agents may achieve in a single deal a reallocation requiring exponentially many rational deals if at most k-1 agents can participate, this same reallocation being unrealisable by any sequences of rational deals in which at most k-2 agents are involved.

Models of persuasion, argument, and reasoning motivated by analogies from Law and legal process are now accepted formalisms supporting multi-agent discourse in applications such as contract negotiation and resolving disputed claims. A number of non-classical Logics and proof theories within these have been proposed speci cally to deal with the special circumstances wherein propositional theories are not best suited to address modeling issues arising in legal contexts: e.g. exceptions and defaults are treated in a variety of socalled non-monotonic logics; similarly concepts of credulous, cautious and sceptical belief have been developed, partly to reect diering forms of `burden of proof' that may apply in various judicial contexts. Our concern in this paper is to consider one aspect of legal argument that appears to have been largely neglected in existing work concerning agent discourse protocols { particularly so in the arenas of persuasion and dispute resolution { the use of legitimate procedural devices to defer `undesirable' conclusions being nalised and the deployment of such techniques in seeking to have a decision over-ruled. Motivating our study is the contention that individual agents within an `agent society' could (be programmed to) act in a `non-cooperative' manner: thus, contesting policies/decisions accepted by other agents in the `society' in order to improve some notional `individual' utility. Using Dung's argumentation framework, we present various settings in which the use of `legitimate delay' can be rigorously modeled, formulate some natural decision questions respecting the existence and utility of `prevaricatory tactics', and, nally, illustrate within a greatly simpli ed schema, how carefully-chosen devices may greatly increase the length of ...

We introduce and examine some properties of a new complexity measure for Boolean functions. Unlike classical approaches, which are largely concerned with resource requirements, the measure examined here aims at quantifying the potential for lazy evaluation in a function. This measure is motivated by issues arising in the implementation of demand-driven logic simulators. The range of values that can be taken by the measure is precisely identified and a lower bound on the complexity of 'almost all' Boolean functions derived. In addition asymptotically exact values are derived for the class of all Boolean symmetric functions.>

This paper describes an efficient algorithm for generating large combinational circuits (ca. 10 5 -10 6 gates). The method has been applied to construct networks for testing the performance of new VLSI chip fabrication processes and as a means of producing testbeds for assessing the average performance of digital simulation systems