United we stand: Accruals in strength-based argumentation

Abstract

Argumentation has been an important topic in knowledge representation, reasoning and multi-agent systems during the last twenty years. In this paper, we propose a new abstract framework where arguments are associated with a strength, namely a quantitative information which is used to determine whether an attack between arguments succeeds or not. Our Strength-based Argumentation Framework (StrAF) combines ideas of Preference-based and Weighted Argumentation Frameworks in an original way, which permits to define acceptability semantics sensitive to the existence of accruals between arguments. The question of accruals arises in situations where several arguments defending the same position (but from different points of view) against another argument are unable to individually defeat this argument, but could do it collectively if they combine their strengths. We investigate some of the theoretical and computational properties of our new framework and semantics, and present a reasoning algorithm that is based on a translation of the problem into pseudo-boolean constraint satisfaction. This paper proposes an intuitive framework which allows strength compensations in an argumentation context where attacks may not succeed, completed by an approach which detects accruals throughout the reasoning process without requiring the elicitation of all compensatory combinations of arguments as an input.

1. Introduction

Argumentation has been a main research topic in artificial intelligence for the last twenty years, with applications in various domains such as decision making [4], automated negotiation [33], reasoning with inconsistent knowledge [13], legal reasoning [11], and multi-agent systems [54]. A lot of works have been proposed, mainly based on the influential argumentation framework (AF) of Dung [35]. An AF is characterized by a set of abstract entities called arguments and an attack relation between arguments. A series of semantics have been defined to determine which arguments are acceptable, usually by computing sets of arguments called extensions that represent arguments that are compatible with each other [7]. Besides situations where arguments are reasons for believing some claims, AFs allow to model different situations where conflicts arise between pieces of information, and to obtain some valuable conclusions.

Reasoning with such an AF supposes that there is no ambiguity about the nature of conflicts and how to resolve them. However, and even when the nature of conflicts is certain, different agents may apply contrasting policies to resolve these conflicts, depending on the relative priorities they associate with arguments. These relative priorities may be represented as a relation of preference between arguments [3], or by a relation of preference between the values attached to arguments [10]. In these works, the reasoning process is achieved in two steps: first a defeat relation is defined as the combination of the initial attack relation and the preference relation. Then, an extension-based semantics of Dung is applied on the graph obtained from the set of arguments combined with the resulting defeat relation. However, none of these frameworks allows to finely compare arguments with respect to a quantitative strength. Intuitively speaking, considering a strength-based framework allows to induce priorities among arguments by merely associating a weight to each argument, and specially does not require to examine each possible pairs of arguments.

Assigning a quantitative information to arguments has been considered in different contexts. First, [15] associates arguments with a numerical value that represents “fuzziness, probability or a preference in general”; the extensions given by Dung’s semantics are then refined depending on the weights of the arguments that belong to them. Then, a different approach considers arguments mapped to a quantitative strength in another context: instead of defining arguments status through the notion of extension, rankings or graduations of arguments can be defined by analyzing the arguments’ intrinsic strength and the attack relation between arguments [2]. Contrary to preference-based argumentation, these weighted argumentation frameworks defined in [2,15] do not consider a notion of defeat in the reasoning process. Moreover, none of the options presented above permits to consider collective attacks [57], and especially accrual of arguments.

The idea of accruals, i.e. arguments that cannot on their own defeat their target but together can succeed, has been initially studied in the literature of philosophy. While, at first, some doubts have been expressed about the meaning of arguments accrual [59,60], more recently assumptions under which accruals of arguments make sense have been pointed out [56]. However the question of whether arguments should accrue or not is out of the scope of this paper. Indeed, this discussion may be decisive when considering arguments as reasons for supporting a claim, but we do not restrict our study to such applications and opt instead for a general view of argumentation as a formal tool to deal with conflicting pieces of information. In addition and more specifically, the question of accruals of reasons has been addressed in the AI literature (see [57,62,66] for examples). Although these studies differ from this paper since they settle in a rule-based argumentation context, corresponding approaches furthermore require to express explicitly a priori all sets of accruals to take them into account throughout the reasoning process. To the best of our knowledge, the question of how accruals can be detected during the reasoning process has not been addressed in the literature.

The aim of this paper is to study this question. More precisely, we propose an approach which:

allows strength compensations in an argumentation context where attacks may not succeed;

detects accruals of arguments during the reasoning process without requiring their explicit elicitation in the model as an input.

To this purpose, we define the Strength-based Argumentation Framework which combines in an original way the quantitative strength expressed in weighted argumentation frameworks on one hand, and the notion of defeat relation introduced in the contexts of preference-based and value-based argumentation on another hand. Then, we generalize the notion of defeat to define a notion of collective defeat. In the following, we use the term of accrual to identify a set of arguments that attack a same target. While arguments in this set might not be able to individually defeat their common target, they could nevertheless achieve the defeat by combining their strength. The representation proposed in this paper allows to compute the strength of an existing accrual, and consequently to decide about the outcome of a conflict between an accrual and an individual argument (or between two accruals) by applying a slightly adapted version of the Dung acceptability semantics.

The paper is organized as follows. Section 2 recalls the basic notions of abstract argumentation. In Section 3, we propose an intuitive framework for representing strength of arguments, and we define formally a defeat-based semantics for our Strength-based Argumentation Frameworks (StrAFs). Then Section 4 introduces accrual of arguments, and provides some theoretical properties of these new semantics that are sensitive to this notion of accrual and produce extensions that are usually ignored by existing semantics. In Section 5, we study the complexity of the reasoning processes for first some particular sub-classes of StrAFs, and then for the general case. We show that, despite this reasoning mechanism may appear to be theoretically intractable, we can rely on the power of Pseudo-Boolean constraints solvers to compute extensions produced by our framework. Section 6 discusses in details existing related work. Finally, Section 7 concludes the paper and describes some tracks for future research.

2. Preliminaries

Most of the studies addressed to the literature of argumentation for the last twenty years have been inspired by the work of [35]. This section presents the basics of abstract argumentation frameworks.

An argumentation framework (AF), as introduced by Dung in [35], is a pair $⟨\mathcal{A}\mathrm{,}\mathcal{R}⟩$ , where $\mathcal{A}$ is a set of arguments, and $\mathcal{R}\subseteq \mathcal{A}\times \mathcal{A}$ is an attack relation. The relation a attacks b, or b is attacked by a, is denoted by $\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in \mathcal{R}$ . We focus on finite argumentation frameworks, i.e. AFs such that $\mathcal{A}$ is a finite set.

In [35], different acceptability semantics have been introduced. These are based on two basic concepts, defence and conflict-freeness, defined as follows:

Definition 1 (Defence/Conflict-freeness).

Let $\mathit{A}\mathit{F}=⟨\mathcal{A}\mathrm{,}\mathcal{R}⟩$ be an argumentation system. Let $\mathit{S}\subseteq \mathcal{A}$ .

S is conflict-free if and only if ∄ $\mathit{a}\mathrm{,}\mathit{b}\in \mathit{S}$ s.t ( $\mathit{a}\mathrm{,}\mathit{b}$ ) $\in \mathcal{R}$ .

S defends $\mathit{a}\in \mathcal{A}$ if and only if ∀ $\mathit{b}\in \mathcal{A}$ , if $\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}\in \mathcal{R}$ , then $\exists \mathit{c}\in \mathit{S}$ such that $\mathrm{(}\mathit{c}\mathrm{,}\mathit{b}\mathrm{)}\in \mathcal{R}$ .

The set of all conflict-free sets of $\mathit{A}\mathit{F}$ is denoted $cf\mathrm{(}\mathit{A}\mathit{F}\mathrm{)}$ .

The basic idea behind these semantics is the following: for a rational agent, an argument a is acceptable if he can defend a against all attacks. All the arguments acceptable for a rational agent will be gathered in a so-called extension. An extension must satisfy a consistency requirement and must defend all its elements.

Definition 2 (Acceptability semantics).

Let $\mathit{A}\mathit{F}=⟨\mathcal{A}\mathrm{,}\mathcal{R}⟩$ be an AF and $\mathit{S}\in cf\mathrm{(}\mathit{A}\mathit{F}\mathrm{)}$ .

S is an admissible set if and only if S defends any element in S.

S is a preferred extension if and only if S is a ⊆-maximal admissible set.

S is a stable extension if and only if it is a conflict free set that defeats any argument in $\mathcal{A}\setminus \mathit{S}$ .

The sets of admissible, preferred and stable extensions are respectively denoted by $ad\mathrm{(}\mathit{A}\mathit{F}\mathrm{)}$ , $pr\mathrm{(}\mathit{A}\mathit{F}\mathrm{)}$ and $st\mathrm{(}\mathit{A}\mathit{F}\mathrm{)}$ .

We show that, besides the natural application of AFs to “real argumentation” (i.e. debates based on the exchange of arguments, where each argument is a reason for supporting some claim), Dung’s AFs can be used to model reasoning problems in presence of conflicting information.

Example 1.

John is a gardener, he has several options for working on the next day: he can maintain the garden of different houses (A, B, C D, E and F), but there are different constraints:

He can work at house A between 3:00 p.m. and 5:00 p.m.;

He can work at house B between 4:00 p.m. and 7:00 p.m.;

He can work at house C between 8:00 a.m. and 10:00 a.m.;

He can work at house D between 9:00 a.m. and 12:00 a.m;

He can work at house E between 12:00 p.m. and 2:00 p.m;

He can work at house F between 1:00 p.m. and 3:00 p.m;

Because of schedule overlapping, houses A and B cannot both be selected by John, and similarly for houses C and D on the one hand, and E and F on the other hand. This situation is represented by $\mathit{A}{\mathit{F}}_{\mathrm{john}}$ given at Fig. 1(a), where argument X is accepted if John decides to maintain the garden of house X. Now, if the owner of house C tells John that, finally, he cannot come between 8:00 a.m. and 10:00 a.m., but rather between 5:00 p.m. and 7:00 p.m., we obtain the situation described by $\mathit{A}{\mathit{F}}_{\mathrm{john}}^2$ (Fig. 1(b)).

The extensions of $\mathit{A}{\mathit{F}}_{\mathrm{john}}$ and $\mathit{A}{\mathit{F}}_{\mathrm{john}}^2$ for the different aforementioned semantics are given at Table 1. All these sets of extensions can represent reasonable choices of working activities for John.

Fig. 1.

Both versions of John’s garden situation.

Table 1

Extensions of $\mathit{A}{\mathit{F}}_{\mathrm{john}}$ and $\mathit{A}{\mathit{F}}_{\mathrm{john}}^2$

σ	$\mathit{\sigma }\mathrm{(}\mathit{A}{\mathit{F}}_{\mathrm{john}}\mathrm{)}$
cf, ad	∅, $\{\mathit{A}\}$ , $\{\mathit{B}\}$ , $\{\mathit{C}\}$ , $\{\mathit{D}\}$ , $\{\mathit{E}\}$ , $\{\mathit{F}\}$ , $\{\mathit{A}\mathrm{,}\mathit{C}\}$ , $\{\mathit{A}\mathrm{,}\mathit{D}\}$ , $\{\mathit{A}\mathrm{,}\mathit{E}\}$ , $\{\mathit{A}\mathrm{,}\mathit{F}\}$ ,
	$\{\mathit{B}\mathrm{,}\mathit{C}\}$ , $\{\mathit{B}\mathrm{,}\mathit{D}\}$ , $\{\mathit{B}\mathrm{,}\mathit{E}\}$ , $\{\mathit{B}\mathrm{,}\mathit{F}\}$ , $\{\mathit{C}\mathrm{,}\mathit{E}\}$ , $\{\mathit{C}\mathrm{,}\mathit{F}\}$ , $\{\mathit{D}\mathrm{,}\mathit{E}\}$ , $\{\mathit{D}\mathrm{,}\mathit{F}\}$
	$\{\mathit{A}\mathrm{,}\mathit{C}\mathrm{,}\mathit{E}\}$ , $\{\mathit{A}\mathrm{,}\mathit{C}\mathrm{,}\mathit{F}\}$ , $\{\mathit{A}\mathrm{,}\mathit{D}\mathrm{,}\mathit{E}\}$ , $\{\mathit{A}\mathrm{,}\mathit{D}\mathrm{,}\mathit{F}\}$ , $\{\mathit{B}\mathrm{,}\mathit{C}\mathrm{,}\mathit{E}\}$ , $\{\mathit{B}\mathrm{,}\mathit{C}\mathrm{,}\mathit{F}\}$ , $\{\mathit{B}\mathrm{,}\mathit{D}\mathrm{,}\mathit{E}\}$ , $\{\mathit{B}\mathrm{,}\mathit{D}\mathrm{,}\mathit{F}\}$
pr, st	$\{\mathit{A}\mathrm{,}\mathit{C}\mathrm{,}\mathit{E}\}$ , $\{\mathit{A}\mathrm{,}\mathit{C}\mathrm{,}\mathit{F}\}$ , $\{\mathit{A}\mathrm{,}\mathit{D}\mathrm{,}\mathit{E}\}$ , $\{\mathit{A}\mathrm{,}\mathit{D}\mathrm{,}\mathit{F}\}$ , $\{\mathit{B}\mathrm{,}\mathit{C}\mathrm{,}\mathit{E}\}$ , $\{\mathit{B}\mathrm{,}\mathit{C}\mathrm{,}\mathit{F}\}$ , $\{\mathit{B}\mathrm{,}\mathit{D}\mathrm{,}\mathit{E}\}$ , $\{\mathit{B}\mathrm{,}\mathit{D}\mathrm{,}\mathit{F}\}$
σ	$\mathit{\sigma }\mathrm{(}\mathit{A}{\mathit{F}}_{\mathrm{john}}^2\mathrm{)}$
cf, ad	∅, $\{\mathit{A}\}$ , $\{\mathit{B}\}$ , $\{\mathit{C}\}$ , $\{\mathit{D}\}$ , $\{\mathit{E}\}$ , $\{\mathit{F}\}$ , $\{\mathit{A}\mathrm{,}\mathit{E}\}$ , $\{\mathit{B}\mathrm{,}\mathit{E}\}$ , $\{\mathit{C}\mathrm{,}\mathit{E}\}$ , $\{\mathit{D}\mathrm{,}\mathit{E}\}$ , $\{\mathit{A}\mathrm{,}\mathit{F}\}$ , $\{\mathit{B}\mathrm{,}\mathit{F}\}$ , $\{\mathit{C}\mathrm{,}\mathit{F}\}$ , $\{\mathit{D}\mathrm{,}\mathit{F}\}$ ,
	$\{\mathit{A}\mathrm{,}\mathit{C}\}$ , $\{\mathit{A}\mathrm{,}\mathit{D}\}$ , $\{\mathit{B}\mathrm{,}\mathit{D}\}$ , $\{\mathit{C}\mathrm{,}\mathit{D}\}$ , $\{\mathit{A}\mathrm{,}\mathit{C}\mathrm{,}\mathit{E}\}$ , $\{\mathit{A}\mathrm{,}\mathit{D}\mathrm{,}\mathit{E}\}$ , $\{\mathit{B}\mathrm{,}\mathit{D}\mathrm{,}\mathit{E}\}$ , $\{\mathit{C}\mathrm{,}\mathit{D}\mathrm{,}\mathit{E}\}$ ,
	$\{\mathit{A}\mathrm{,}\mathit{C}\mathrm{,}\mathit{F}\}$ , $\{\mathit{A}\mathrm{,}\mathit{D}\mathrm{,}\mathit{F}\}$ , $\{\mathit{B}\mathrm{,}\mathit{D}\mathrm{,}\mathit{F}\}$ , $\{\mathit{C}\mathrm{,}\mathit{D}\mathrm{,}\mathit{F}\}$ , $\{\mathit{A}\mathrm{,}\mathit{C}\mathrm{,}\mathit{D}\}$ , $\{\mathit{A}\mathrm{,}\mathit{C}\mathrm{,}\mathit{D}\mathrm{,}\mathit{E}\}$ , $\{\mathit{A}\mathrm{,}\mathit{C}\mathrm{,}\mathit{D}\mathrm{,}\mathit{F}\}$
pr, st	$\{\mathit{A}\mathrm{,}\mathit{C}\mathrm{,}\mathit{D}\mathrm{,}\mathit{E}\}$ , $\{\mathit{A}\mathrm{,}\mathit{C}\mathrm{,}\mathit{D}\mathrm{,}\mathit{F}\}$ , $\{\mathit{B}\mathrm{,}\mathit{D}\mathrm{,}\mathit{E}\}$ , $\{\mathit{B}\mathrm{,}\mathit{D}\mathrm{,}\mathit{F}\}$

Notice that $cf\mathrm{(}\mathit{A}{\mathit{F}}_{\mathrm{john}}\mathrm{)}=ad\mathrm{(}\mathit{A}{\mathit{F}}_{\mathrm{john}}\mathrm{)}$ and $pr\mathrm{(}\mathit{A}{\mathit{F}}_{\mathrm{john}}\mathrm{)}=st\mathrm{(}\mathit{A}{\mathit{F}}_{\mathrm{john}}\mathrm{)}$ (and similarly for $\mathit{A}{\mathit{F}}_{\mathrm{john}}^2$ ). This comes from the fact that these AFs are symmetric [28]. This is not the case in general, but it is well-known that $\forall \mathit{A}\mathit{F}$ , $st\mathrm{(}\mathit{A}\mathit{F}\mathrm{)}\subseteq pr\mathrm{(}\mathit{A}\mathit{F}\mathrm{)}\subseteq ad\mathrm{(}\mathit{A}\mathit{F}\mathrm{)}\subseteq cf\mathrm{(}\mathit{A}\mathit{F}\mathrm{)}$ . See [7,35] for more details about the extension-based semantics.

3. Strength-based argumentation frameworks

3.1. Representing strength in abstract argumentation

We have described in the introduction some intuitions on the meaning of the numerical strength associated with arguments. While [15] mentions “fuzziness, probability or a preference in general”, or a notion of trust about the arguments, [2] associates the weights to an intrinsic strength, that represents votes given by users [48], a certainty degree of arguments premises [12] or trustworthiness of the source of information [32]. A similar intuitive explanation is given in [55,61] for weights associated with arguments, and in [37] for weights associated with attacks.

Game theory techniques have also been borrowed to determine what is the strength of an argument depending on the structure of the argumentation graph [53]. While this approach gives a concrete meaning to the strength of arguments, here the strength is the output of the process, in the spirit of gradual semantics [8,24]. On the contrary, we want to have the strength as input of our reasoning process.

Concrete applications of argumentation frameworks with strength of arguments have been studied recently. Quantitative Argumentation Debates (QuAD frameworks) [9] associate arguments to a numerical strength (called base score), and their gradual semantics define a degree of acceptance for each argument. A variant of QuAD frameworks [64] has been used to give a novel method for opinion polling, with arguments base scores corresponding to users votes.

Quantitative Bipolar Argumentation Frameworks (QBAFs) [8] are a general abstract argumentation framework where arguments are related by both attacks and supports [25], and they are attached with a base score. Again, the semantics of these frameworks yields a degree of acceptance for each argument. In [27], QBAFs are used to aggregate reviews of movies from Internet database, in particular the notes given on the famous website RottenTomatoes are used as the base score of arguments.

An argumentation framework for persuasion is defined in [65], where arguments are associated with integer weights. However, these weights can be interpreted as the arguments weakness instead of the arguments strength, since they represent the cost of the action supported by the argument. Thus, the higher is the weight, the weaker is the argument.

In our running example, we show how strengths of arguments can be used to represent the utility for the agent that some arguments belong to the extensions (for instance, the money earned when performing some task). For a matter of simplicity, we will use natural numbers for modelling the strength of arguments in all our definitions and examples, although our approach can be extended with positive real numbers. However, the behaviour of our accrual-sensitive semantics may not be preserved in some specific cases, that are discussed in Section 4.1.

3.2. Formal definition of StrAFs

Let us now formally introduce the Strength-based Argumentation Framework. Intuitively speaking, a StrAF is an argumentation framework where each argument is associated with a weight (here a non-negative integer) which represents its strength:

Definition 3 (Strength-based Argumentation Framework).

A Strength-based Argumentation Framework (StrAF) is a triple $⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{S}⟩$ where $\mathcal{A}$ and $\mathcal{R}$ are respectively arguments and attacks, and $\mathcal{S}:\mathcal{A}\to \mathbb{N}$ is a strength function.

In our framework, the higher is the weight, the stronger is the argument this weight is associated with. Let us illustrate this representation with the following example:

Example 2.

Let us continue Example 1. Depending of the size of the garden, John’s salary for these works is not the same: houses A, B, C, D, E and F are worth respectively 40 Euros, 60 Euros, 40 Euros, 80 Euros, 40 Euros and 60 Euros. For each argument, the salary that John gets corresponds to the strength of the argument. So, from $\mathit{A}{\mathit{F}}_{\mathrm{john}}$ and $\mathit{A}{\mathit{F}}_{\mathrm{john}}^2$ , we can define StrAFs ${\mathit{StrAF}}_{\mathrm{john}}=⟨{\mathcal{A}}_{\mathrm{john}}\mathrm{,}{\mathcal{R}}_{\mathrm{john}}\mathrm{,}{\mathcal{S}}_{\mathrm{john}}⟩$ and ${\mathit{StrAF}}_{\mathrm{john}}^2=⟨{\mathcal{A}}_{\mathrm{john}}\mathrm{,}{\mathcal{R}}_{\mathrm{john}}^2\mathrm{,}{\mathcal{S}}_{\mathrm{john}}⟩$ described at Fig. 2, where $\mathcal{S}\mathrm{(}\mathit{A}\mathrm{)}=\mathcal{S}\mathrm{(}\mathit{C}\mathrm{)}=\mathcal{S}\mathrm{(}\mathit{E}\mathrm{)}=40$ , $\mathcal{S}\mathrm{(}\mathit{B}\mathrm{)}=\mathcal{S}\mathrm{(}\mathit{F}\mathrm{)}=60$ and $\mathcal{S}\mathrm{(}\mathit{D}\mathrm{)}=80$ . This means that an argument X is stronger than an argument Y if John earns more money when maintaining the garden of house X rather than house Y.

Fig. 2.

Both versions of John’s garden situation.

Now, we adapt Dung-style semantics to StrAFs. To do so, we borrow the notion of defeat relation from Preference-based AFs and Value-based AFs [3,10].

Definition 4 (Defeat Relation and Extension Semantics).

Given $\mathit{StrAF}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{S}⟩$ a StrAF, the defeat relation Def is defined by $Def=\{\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in \mathcal{R}\mid \mathcal{S}\mathrm{(}\mathit{b}\mathrm{)}\ngtr \mathcal{S}\mathrm{(}\mathit{a}\mathrm{)}\}$ .

Extension-based semantics of $\mathit{StrAF}$ can be defined by considering the extensions of the classical AF $\mathit{DefAF}=⟨\mathcal{A}\mathrm{,}Def⟩$ , i.e. $\mathit{\sigma }\mathrm{(}\mathit{StrAF}\mathrm{)}=\mathit{\sigma }\mathrm{(}\mathit{DefAF}\mathrm{)}$ for $\mathit{\sigma }\in \{cf\mathrm{,}ad\mathrm{,}pr\mathrm{,}st\}$ .1

¹

Of course, the same mechanism can be applied to other semantics that are not considered in this paper.

This definition mimics the definition of Preference-based AFs, except that here the notion of preference is expressed through a quantitative measure. A similar notion can be found in [16] where the concept of defence is refined by taking advantage of weights associated with attack relations.

Example 3.

We continue Example 2. For both $\mathit{StrA}{F}_{\mathrm{john}}$ and ${\mathit{StrAF}}_{\mathrm{john}}^2$ , we describe below the graphs corresponding to the defeat relation.

In the case of ${\mathit{DefAF}}_{\mathrm{john}}$ (Fig. 3(a)), we observe that using the defeat relation leads to an intuitive result: for any semantics $\mathit{\sigma }\in \{ad\mathrm{,}pr\mathrm{,}st\}$ as introduced in Definition 2, the single extension is $\{\mathit{B}\mathrm{,}\mathit{D}\mathrm{,}\mathit{F}\}$ , which is the best option for John (since he will earn 200 Euros). However, in the second situation depicted at Fig. 3(b), any semantics $\mathit{\sigma }\in \{ad\mathrm{,}pr\mathrm{,}st\}$ gives $\mathit{\sigma }\mathrm{(}{\mathit{AF}}_{\mathrm{john}}^2\mathrm{)}=\{\mathit{B}\mathrm{,}\mathit{D}\mathrm{,}\mathit{F}\}$ ; this option is worth 200 Euros and is not optimal (indeed $\{\mathit{A}\mathrm{,}\mathit{C}\mathrm{,}\mathit{D}\mathrm{,}\mathit{F}\}$ is an extension of $\mathit{A}{\mathit{F}}_{\mathrm{john}}^2$ , and is worth 220 Euros).

Fig. 3.

Defeat graphs for John’s garden situation.

These defeat-based semantics are relevant when the strength associated with an argument is individual and independent from other arguments, likewise the behavior of Preference-based AFs. In our case, the semantics may produce an extension which is not the most desirable outcome, like it is the case with ${\mathit{DefAF}}_{\mathrm{john}}^2$ . This is why we propose to define semantics sensitive to the notion of accrual of arguments.

4. Accrual of arguments

Recent works have tackled the question of “quality versus quantity”: is it worse for an argument to be attacked by only one strong attacker, or to be attacked by plenty of quite weak attackers? In the context of gradual semantics, this question is materialized by the principles of Quality Precedence and Cardinality Precedence. A Compensation principle is also stated to describe situations where several weak arguments have the same effect on their target as fewer strong arguments [1,2,20]. Although the context is not the same (since we consider extension-based semantics), a similar intuition leads to our definition of accruals: several arguments may be individually too weak to defeat their target, but their collective attack may be strong enough to compensate or even exceed the target’s strength.

4.1. StrAFs with accrual

In this paper, we assume that weights associated with arguments are commensurable. Roughly speaking, this means that these weights are comparable from an argument to another, and aggregating them (with e.g. a Sum-based operation) makes sense. This kind of assumptions suits well situations where, for instance, weights associated with arguments are provided by an expert or a group of experts sharing a same representation scale, or are regarded as rewards granted for the acceptance of some arguments. An example of the latter is provided by our running example.

Let us first formally define the notion of accrual of arguments:

Definition 5.

Let $\mathit{StrAF}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{S}⟩$ be a StrAF. A set of arguments $\mathit{\kappa }\subseteq \mathcal{A}$ is called accrual if and only if $\exists \mathit{c}\in \mathcal{A}$ such that ∀ $\mathit{a}\in \mathit{\kappa }$ , $\mathrm{(}\mathit{a}\mathrm{,}\mathit{c}\mathrm{)}\in \mathcal{R}$ . Moreover, we say that κ is an accrual that attacks argument c.

Intuitively, an accrual is a set of arguments such that there exists an argument which is attacked by all arguments in this set. Let us illustrate this notion with our running example:

Example 4.

In ${\mathit{StrAF}}_{\mathrm{john}}^2$ describing John’s situation (see Example 2), there is (for instance) an accrual $\mathit{\kappa }=\{\mathit{A}\mathrm{,}\mathit{C}\}$ attacking the argument B.

In the following, we choose to opt for a pessimistic view of attacking an accrual. An accrual is said to be attacked by an argument if and only if at least one of its arguments is attacked. Then, several definitions of an accrual attacking another accrual are possible. In what follows, we choose to focus on the following one, which corresponds again to the pessimistic case: an accrual κ attacks an accrual ${\mathit{\kappa }}^{\prime }$ if and only if there exists an argument in ${\mathit{\kappa }}^{\prime }$ such that all arguments of κ attack this argument. Formally:

Definition 6.

Let $\mathit{StrAF}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{S}⟩$ be a StrAF, and $\mathit{\kappa }\subseteq \mathcal{A}$ , ${\mathit{\kappa }}^{\prime }\subseteq \mathcal{A}$ two accruals. Then, κ attacks ${\mathit{\kappa }}^{\prime }$ if and only if $\exists \mathit{a}\in {\mathit{\kappa }}^{\prime }$ such that κ attacks a.

We then define the collective strength associated with an accrual κ, denoted by $coval\mathrm{(}\mathit{\kappa }\mathrm{)}$ , as the combination of values associated with arguments. Formally:

Definition 7.

Let $\mathit{StrAF}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{S}⟩$ be a StrAF and $\mathit{\kappa }=\{{\mathit{a}}_1\mathrm{,}\dots \mathrm{,}{\mathit{a}}_{\mathit{n}}\}\subseteq \mathcal{A}$ be an accrual. Then the collective strength associated with κ is: $$\begin{array}{c}coval\mathrm{(}\mathit{\kappa }\mathrm{)}=coval\mathrm{(}\mathcal{S}\mathrm{(}{\mathit{a}}_1\mathrm{)}\mathrm{,}\dots \mathrm{,}\mathcal{S}\mathrm{(}{\mathit{a}}_{\mathit{n}}\mathrm{)}\mathrm{)}\end{array}$$ where coval is an aggregation operator, i.e. a mapping from a vector of integers to an integer that satisfies: (non-decreasingness)

if ${\mathit{x}}_{\mathit{i}}⩾{\mathit{x}}_{\mathit{i}}^{\prime }$ , then $coval\mathrm{(}{\mathit{x}}_1\mathrm{,}\dots \mathrm{,}{\mathit{x}}_{\mathit{i}}\mathrm{,}\dots \mathrm{,}{\mathit{x}}_{\mathit{n}}\mathrm{)}⩾coval\mathrm{(}{\mathit{x}}_1\mathrm{,}\dots \mathrm{,}{\mathit{x}}_{\mathit{i}}^{\prime }\mathrm{,}\dots \mathrm{,}{\mathit{x}}_{\mathit{n}}\mathrm{)}$ ;

(minimality)

$coval\mathrm{(}{\mathit{x}}_1\mathrm{,}\dots \mathrm{,}{\mathit{x}}_{\mathit{n}}\mathrm{)}=0$ if and only if ${\mathit{x}}_1=\cdots ={\mathit{x}}_{\mathit{n}}=0$ ;

(identity)

$coval\mathrm{(}\mathit{x}\mathrm{)}=\mathit{x}$ ;

(accrual)

$coval\mathrm{(}{\mathit{x}}_1\mathrm{,}\dots \mathrm{,}{\mathit{x}}_{\mathit{n}}\mathrm{)}⩽coval\mathrm{(}{\mathit{x}}_1\mathrm{,}\dots \mathrm{,}{\mathit{x}}_{\mathit{n}}\mathrm{,}\mathit{y}\mathrm{)}$ .

These properties are quite natural for defining the strength of an accrual. Non-decreasingness means that, if $\mathit{a}\notin \mathit{\kappa }$ and $\mathit{b}\notin \mathit{\kappa }$ , then the accrual $\mathit{\kappa }\cup \{\mathit{a}\}$ is stronger than the accrual $\mathit{\kappa }\cup \{\mathit{b}\}$ when a is stronger than b. Minimality states that the accumulation of arguments “without” strength (i.e. $\mathcal{S}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}=0$ ) does not create a collective strength from the void, and that non-null arguments cannot cancel each other’s strength when they are taken together. Identity ensures that the “collective” strength of a singleton is exactly the intrinsic strength of the argument in this singleton. These properties are used for defining aggregation operators with other purposes, like defining extensions in AFs with weighted attacks [29]; they correspond to the basic properties of semirings [14,16]. Finally, we consider the Accrual property: any set of arguments is at least as strong as all its subsets.

The coval operator may be a classical aggregation function like the sum ∑, the maximum max or the weighted sum. Conversely, the product Π does not satisfy the minimality property. Furthermore, one can notice that if we extend our approach to positive real numbers for representing the strength, then the product Π operator does not satisfy the accrual properties if some values belong to the interval $[0\mathrm{,}1]$ . Nevertheless, all the properties remain satisfied by Π if only natural or real numbers greater or equal to 1 are allowed.

To accommodate the notion of accrual we extend the semantics of StrAFs to take collective defeat as follows.

We say that an argument a is collectively defeated by an accrual κ if and only if the collective strength associated with κ is greater or equal to the value associated with a.

Definition 8.

Let $\mathit{StrAF}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{S}⟩$ be a StrAF, $\mathit{a}\in \mathcal{A}$ , and coval an aggregation operator. Then, an accrual κ defeats a with respect to coval, denoted by $\mathit{\kappa }{⊳}_{coval}\mathit{a}$ , if and only if

$\mathit{\kappa }\subseteq \mathcal{A}$ is an accrual that attacks a;

$coval\mathrm{(}\mathit{\kappa }\mathrm{)}⩾\mathcal{S}\mathrm{(}\mathit{a}\mathrm{)}$ .

If coval is clear from the context, we use $\mathit{\kappa }⊳\mathit{a}$ instead of $\mathit{\kappa }{⊳}_{coval}\mathit{a}$ .

We can introduce the notion of an accrual that defeats another accrual as follows:

Definition 9.

Let $\mathit{StrAF}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{S}⟩$ be a StrAF, coval an aggregation operator and $\mathit{\kappa }\subseteq \mathcal{A}$ , ${\mathit{\kappa }}^{\prime }\subseteq \mathcal{A}$ two accruals. Then κ defeats ${\mathit{\kappa }}^{\prime }$ , denoted by $\mathit{\kappa }⊳{\mathit{\kappa }}^{\prime }$ , if and only if there exists $\mathit{a}\in {\mathit{\kappa }}^{\prime }$ such that $\mathit{\kappa }⊳\mathit{a}$ .

Roughly speaking, an accrual defeats another accrual if the first accrual induces a defeat against at least one argument of the second accrual.

In [16], the strength of an attack from a set S to a set ${\mathit{S}}^{\prime }$ of arguments is defined as the aggregation of strengths associated with all the attacks from any argument in S to any argument in ${\mathit{S}}^{\prime }$ . While this may look similar to defeats between accruals, these are actually different concepts. Indeed, since [16] do not associate strength with arguments, but with attacks, there is no comparison between strength associated respectively with S and ${\mathit{S}}^{\prime }$ . Moreover, in our approach, defeating any argument of an accrual is enough to consider the whole accrual as defeated. Nevertheless, one can notice that a subset of this defeated accrual can still be an undefeated accrual.

Let us illustrate the notion of collective attacks with our running example.

Example 5.

We continue Example 2. The natural aggregation operator here is $coval=\sum$ , since the strength of an accrual is the money earned by John for maintaining several gardens (corresponding to the arguments in the accrual). We observe that, in ${\mathit{StrAF}}_{\mathrm{john}}^2$ , the accruals ${\mathit{\kappa }}_1=\{\mathit{B}\}$ and ${\mathit{\kappa }}_2=\{\mathit{A}\mathrm{,}\mathit{C}\}$ defeat each other. Indeed, $coval\mathrm{(}{\mathit{\kappa }}_1\mathrm{)}=\mathcal{S}\mathrm{(}\mathit{B}\mathrm{)}=60⩾\mathcal{S}\mathrm{(}\mathit{A}\mathrm{)}$ , while $coval\mathrm{(}{\mathit{\kappa }}_2\mathrm{)}=\mathcal{S}\mathrm{(}\mathit{A}\mathrm{)}+\mathcal{S}\mathrm{(}\mathit{C}\mathrm{)}=80⩾\mathcal{S}\mathrm{(}\mathit{B}\mathrm{)}$ .

The following example illustrates our approach in a non-symmetrical abstract argumentation context. Example 6.

Fig. 4.

The StrAF that describes the situation of Joe and Jack.

Let us consider the example provided in [57], composed of the following abstract arguments:

${\mathit{A}}_1$ : “Joe does not like Jack”;

${\mathit{A}}_2$ : “There is a nail in Jack’s antique coffee table”;

${\mathit{A}}_3$ : “Joe hammered a nail into Jack’s antique coffee table”;

${\mathit{A}}_4$ : “Joe plays golf, so Joe has full use of his arms”;

${\mathit{A}}_5$ : “Joe has no arms, so Joe cannot use a hammer, so Joe did not hammer a nail into Jack’s antique coffee table”.

As examples of attacks, one can on a first hand notice that the argument ${\mathit{A}}_5$ directly attacks (and thus defeats) the argument ${\mathit{A}}_3$ , whereas arguments ${\mathit{A}}_3$ and ${\mathit{A}}_4$ directly attack (and also defeat) the argument ${\mathit{A}}_5$ .

On another hand, authors in [57] discuss that arguments ${\mathit{A}}_1$ and ${\mathit{A}}_2$ attack the argument ${\mathit{A}}_5$ since they can provide the conclusion that Joe has hammered a nail into Jack’s antique coffee table, but cannot separately defeat it. However, when considered together, ${\mathit{A}}_1$ and ${\mathit{A}}_2$ may constitute a stronger argument that defeats ${\mathit{A}}_5$ . These examples of attacks are illustrated by Fig. 4.

In our framework, let ${\mathit{x}}_{\mathit{i}}$ be the strength associated with the argument ${\mathit{A}}_{\mathit{i}}$ , for $\mathit{i}\in \{1\mathrm{,}\dots \mathrm{,}5\}$ . Let us assume that ${\mathit{x}}_3={\mathit{x}}_5$ (since ${\mathit{A}}_3$ and ${\mathit{A}}_5$ defeat each other), and ${\mathit{x}}_4⩾{\mathit{x}}_5$ (since ${\mathit{A}}_4$ defeat ${\mathit{A}}_5$ ). Several cases are then possible:

either strengths associated with arguments are such that either ${\mathit{x}}_1⩾{\mathit{x}}_5$ or ${\mathit{x}}_2⩾{\mathit{x}}_5$ : in this case, either the argument ${\mathit{A}}_1$ or the argument ${\mathit{A}}_2$ is considered solid enough to individually defeat the argument ${\mathit{A}}_5$ ;

either strengths associated with arguments are such that ${\mathit{x}}_1\mathrm{<}{\mathit{x}}_5$ , ${\mathit{x}}_2\mathrm{<}{\mathit{x}}_5$ and ${\mathit{x}}_1+{\mathit{x}}_2⩾{\mathit{x}}_5$ : in this case arguments ${\mathit{A}}_1$ and ${\mathit{A}}_2$ are too weak to defeat individually argument ${\mathit{A}}_5$ but form an accrual to collectively defeat it;

or finally strengths associated with arguments are such that ${\mathit{x}}_1\mathrm{<}{\mathit{x}}_5$ , ${\mathit{x}}_2\mathrm{<}{\mathit{x}}_5$ and ${\mathit{x}}_1+{\mathit{x}}_2\mathrm{<}{\mathit{x}}_5$ : in this case arguments ${\mathit{A}}_1$ and ${\mathit{A}}_2$ cannot defeat ${\mathit{A}}_5$ neither individually nor collectively.

Roughly speaking, according to the importance one chooses to attach to these arguments and thus depending on the strengths associated with arguments ${\mathit{A}}_1$ , ${\mathit{A}}_2$ and ${\mathit{A}}_5$ , ${\mathit{A}}_1$ and ${\mathit{A}}_2$ can individually or collectively defeat ${\mathit{A}}_5$ or not.

4.2. Extension-based semantics for StrAFS

In [35], different acceptability semantics have been introduced for computing the status of arguments. These are based on two basic concepts, defence and conflict-freeness, which can be adapted to the context of accruals.

The notion of conflict-freeness can be defined into two different senses, the strong and the weak conflict-freeness.

Definition 10 (Defence/Conflict-freeness).

Let $\mathit{StrAF}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{S}⟩$ be a StrAF, coval an aggregation operator, and $\mathit{S}\subseteq \mathcal{A}$ .

S is strongly conflict-free if and only if $\nexists \mathit{a}\mathrm{,}\mathit{b}\in \mathit{S}$ such that $\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in \mathcal{R}$ .

S is weakly conflict-free if and only if there are no accruals ${\mathit{\kappa }}_1\subseteq \mathit{S}$ and ${\mathit{\kappa }}_2\subseteq \mathit{S}$ such that ${\mathit{\kappa }}_1{⊳}_{coval}{\mathit{\kappa }}_2$ .

S defends an element $\mathit{a}\in \mathcal{A}$ if and only if for all accruals ${\mathit{\kappa }}_1\subseteq \mathcal{A}$ , if ${\mathit{\kappa }}_1{⊳}_{coval}\mathit{a}$ , then there exists an accrual ${\mathit{\kappa }}_2\subseteq \mathit{S}$ such that ${\mathit{\kappa }}_2{⊳}_{coval}{\mathit{\kappa }}_1$ .

Depending on the notion of conflict-freeness that is applied, two versions of acceptability semantics are derived, that are defined formally below.

Definition 11 (Acceptability semantics).

Let $\mathit{StrAF}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{S}⟩$ be a StrAF, coval an aggregation operator, and S a strong (respectively weak) conflict free set of arguments.

S is a strong (respectively weak) admissible set if and only if S defends all elements of S.

S is a strong (respectively weak) preferred extension if and only if S is a ⊆-maximal strong (respectively weak) admissible set.

S is a strong (respectively weak) stable extension if and only if for each argument $\mathit{a}\in \mathcal{A}\setminus \mathit{S}$ , there is an accrual $\mathit{\kappa }\subseteq \mathit{S}$ such that $\mathit{\kappa }⊳\mathit{a}$ .

For any semantics $\mathit{\sigma }\in \{cf\mathrm{,}ad\mathrm{,}pr\mathrm{,}st\}$ , the set of strong (respectively weak) σ extension of $\mathit{StrAF}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{S}⟩$ with respect to coval is denoted by ${\mathit{\sigma }}_{\mathit{S}}^{coval}\mathrm{(}\mathit{StrAF}\mathrm{)}$ (respectively ${\mathit{\sigma }}_{\mathit{W}}^{coval}\mathrm{(}\mathit{StrAF}\mathrm{)}$ ). We drop coval from the notations when it is clear from the context.

It is easy to see that a strong extension is a weak extension as well, since the absence of attacks in a set S (i.e. strong conflict-freeness) straightforwardly implies the absence of accrual in S defeating elements of S (i.e. weak conflict-freeness). Therefore ${\mathit{\sigma }}_{\mathit{S}}\mathrm{(}\mathit{StrAF}\mathrm{)}\subseteq {\mathit{\sigma }}_{\mathit{W}}\mathrm{(}\mathit{StrAF}\mathrm{)}$ for any semantics σ.

We also remark a relation between weak semantics of StrAFs and semantics of AFs with collective attacks [57]. Indeed, if $\mathit{\kappa }⊳\mathit{a}$ holds in a StrAF, we can define an AF with collective attacks where the set of arguments κ attacks a (according to the notion of attacks defined in [57]). Thus, weak conflict-freeness (and the weak semantics based on weak conflict-freeness) coincide with the conflict-freeness and semantics for AFs with collective attacks. However, we notice that StrAFs allow a more modular representation of argument accrual, since they are only based on individual attacks and arguments strengths, and they do not need to be explicitly defined a priori.

We show that the usual relationship between semantics also holds for StrAFs.

Proposition 1 (Semantics Inclusion).

Let $\mathit{StrAF}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{S}⟩$ be a StrAF and coval an aggregation operator. For $\mathit{X}\in \{\mathit{S}\mathrm{,}\mathit{W}\}$ , ${st}_{\mathit{X}}\mathrm{(}\mathit{StrAF}\mathrm{)}\subseteq {pr}_{\mathit{X}}\mathrm{(}\mathit{StrAF}\mathrm{)}\subseteq {ad}_{\mathit{X}}\mathrm{(}\mathit{StrAF}\mathrm{)}$ .

Proof.

The fact that every strong (respectively weak) preferred extension is a strong (respectively weak) admissible extension is straightforward from the definition.

Let $\mathit{E}\subseteq \mathcal{A}$ be a strong (respectively weak) stable extension of $\mathit{StrAF}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{S}⟩$ with respect to coval, i.e. $\forall \mathit{a}\in \mathcal{A}\setminus \mathit{S}$ , there is an accrual $\mathit{\kappa }\subseteq \mathit{E}$ such that $\mathit{\kappa }⊳\mathit{a}$ .

First we prove that E is a strong (respectively weak) admissible extension. Let $\mathit{\kappa }\subseteq \mathcal{A}$ be an accrual such that $\mathit{\kappa }⊳\mathit{a}$ , with $\mathit{a}\in \mathit{E}$ . There are two cases. Case 1

$\mathit{\kappa }\subseteq \mathit{E}$ implies that E is neither strongly nor weakly conflict-free, this is a contradiction.

Case 2

$\mathit{\kappa }⊈\mathit{E}$ implies that $\exists \mathit{b}\in \mathit{\kappa }\setminus \mathit{E}$ , and since E is a strong (respectively weak) stable extension, $\mathit{E}⊳\mathit{b}$ holds. Thus $\mathit{E}⊳\mathit{\kappa }$ , and we conclude that E is a strong (respectively weak) admissible extension.

Now we prove that E is a strong (respectively weak) preferred extension. Using reductio ad absurdum, we suppose that E is not a strong (respectively weak) preferred extension, this means that $\exists {\mathit{E}}^{\prime }\subseteq \mathit{A}$ a strong (respectively weak) admissible extension such that $\mathit{E}\subset {\mathit{E}}^{\prime }$ . So $\exists \mathit{a}\in {\mathit{E}}^{\prime }\setminus \mathit{E}$ . We have previously established that $\exists \mathit{\kappa }\subseteq \mathit{E}\subset {\mathit{E}}^{\prime }$ is such that $\mathit{\kappa }⊳\mathit{a}$ , so ${\mathit{E}}^{\prime }$ is not weakly conflict-free, and therefore not strongly conflict-free. This is a contradiction with the fact that ${\mathit{E}}^{\prime }$ is a strong (respectively weak) admissible extension, and thus E is a ⊆-maximal strong (respectively weak) admissible extension, i.e. a strong (respectively weak) preferred extension. □

Example 7.

Now we give the strong stable extensions of ${\mathit{StrAF}}_{\mathrm{john}}$ and ${\mathit{StrAF}}_{\mathrm{john}}^2$ , with $coval=\sum$ . It is easy to see that ${st}_{\mathit{S}}^{\mathrm{\Sigma }}\mathrm{(}{\mathit{StrAF}}_{\mathrm{john}}\mathrm{)}=\{\{\mathit{B}\mathrm{,}\mathit{D}\mathrm{,}\mathit{F}\}\}$ since B, D and F respectively defeat A, C and E; this is the same result given by the “classical” defeat-based stable semantics (see Example 3), and it is the optimal solution for John. In the case of the second StrAF, we obtain ${st}_{\mathit{S}}^{\mathrm{\Sigma }}\mathrm{(}{\mathit{StrAF}}_{\mathrm{john}}^2\mathrm{)}=\{\{\mathit{A}\mathrm{,}\mathit{C}\mathrm{,}\mathit{D}\mathrm{,}\mathit{F}\}\mathrm{,}\{\mathit{B}\mathrm{,}\mathit{D}\mathrm{,}\mathit{F}\}\}$ . We observe that the optimal solution $\{\mathit{A}\mathrm{,}\mathit{C}\mathrm{,}\mathit{D}\mathrm{,}\mathit{F}\}$ is now an extension, contrary to the outcome of the defeat-based stable semantics.

Since both StrAFs are symmetric, the weak stable extensions are equal to the strong stable extensions (see Proposition 6 for the proof), but it is not the case in general (see Example 8 for an illustration).

Now we prove that Dung’s argumentation theory is an instance of our StrAF, as it is shown in the following result, that proves a one to one correspondence between the semantics of a Dung’s AFs and the strong semantics of StrAFs.

Definition 12.

Given an argumentation framework $\mathit{A}\mathit{F}=⟨\mathcal{A}\mathrm{,}\mathcal{R}⟩$ , the StrAF associated with AF is ${\mathit{StrAF}}_{\mathit{A}\mathit{F}}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{S}⟩$ with $\mathcal{S}\mathrm{(}\mathit{a}\mathrm{)}=1$ , $\forall \mathit{a}\in \mathcal{A}$ and $coval=\sum$ .

Lemma 1.

Let $\mathit{A}\mathit{F}=⟨\mathcal{A}\mathrm{,}\mathcal{R}⟩$ be a Dung’s AF, and ${\mathit{StrAF}}_{\mathit{A}\mathit{F}}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{S}⟩$ its associated StrAF. The set $\mathit{S}\subseteq \mathcal{A}$ is conflict-free in $\mathit{A}\mathit{F}$ if and only if it is strongly conflict-free in ${\mathit{StrAF}}_{\mathit{A}\mathit{F}}$ .

Lemma 1 is obvious from the definition of strong conflict-freeness.

Lemma 2.

Let $\mathit{A}\mathit{F}=⟨\mathcal{A}\mathrm{,}\mathcal{R}⟩$ be a Dung’s AF, and ${\mathit{StrAF}}_{\mathit{A}\mathit{F}}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{S}⟩$ its associated StrAF. The set $\mathit{S}\subseteq \mathcal{A}$ defends the argument $\mathit{a}\in \mathcal{A}$ in $\mathit{A}\mathit{F}$ if and only if $\mathit{S}\subseteq \mathcal{A}$ defends the argument $\mathit{a}\in \mathcal{A}$ in ${\mathit{StrAF}}_{\mathit{A}\mathit{F}}$ .

Proof.

Let us suppose that $\mathit{S}\subseteq \mathcal{A}$ defends the argument $\mathit{a}\in \mathcal{A}$ in $\mathit{A}\mathit{F}$ . This means that for each $\mathit{b}\in \mathcal{A}$ such that $\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}\in \mathcal{R}$ , $\exists \mathit{c}\in \mathit{S}$ such that $\mathrm{(}\mathit{c}\mathrm{,}\mathit{b}\mathrm{)}\in \mathcal{R}$ .

Now, let us consider an accrual ${\mathit{\kappa }}_1\subseteq \mathcal{A}$ such that ${\mathit{\kappa }}_1⊳\mathit{a}$ . As established previously, $\forall \mathit{b}\in {\mathit{\kappa }}_1$ , $\exists \mathit{c}\in \mathit{S}$ such that $\mathrm{(}\mathit{c}\mathrm{,}\mathit{b}\mathrm{)}\in \mathcal{R}$ , i.e. $\exists {\mathit{\kappa }}_2=\{\mathit{c}\}\subseteq \mathit{S}$ such that ${\mathit{\kappa }}_2$ attacks b. Since $coval\mathrm{(}{\mathit{\kappa }}_2\mathrm{)}=\mathcal{S}\mathrm{(}\mathit{c}\mathrm{)}=1=\mathcal{S}\mathrm{(}\mathit{b}\mathrm{)}$ , ${\mathit{\kappa }}_2⊳\mathit{b}$ and thus ${\mathit{\kappa }}_2⊳{\mathit{\kappa }}_1$ . So S defends the argument a in ${\mathit{StrAF}}_{\mathit{A}\mathit{F}}$ .

Now we suppose that $\mathit{S}\subseteq \mathcal{A}$ defends the argument $\mathit{a}\in \mathcal{A}$ in ${\mathit{StrAF}}_{\mathit{A}\mathit{F}}$ , i.e. for all accruals ${\mathit{\kappa }}_1$ that defeat a, $\exists {\mathit{\kappa }}_2\subseteq \mathit{S}$ such that ${\mathit{\kappa }}_2⊳{\mathit{\kappa }}_1$ . Since all arguments strengths are equal to 1, every argument $\mathit{b}\in \mathcal{A}$ attacking a corresponds to an accrual ${\mathit{\kappa }}_1=\{\mathit{b}\}$ defeating a. So $\exists {\mathit{\kappa }}_2\subseteq \mathit{S}$ such that ${\mathit{\kappa }}_2⊳{\mathit{\kappa }}_1=\{\mathit{b}\}$ , and thus $\exists \mathit{c}\in {\mathit{\kappa }}_2\subseteq \mathit{S}$ such that $\mathrm{(}\mathit{c}\mathrm{,}\mathit{b}\mathrm{)}\in \mathcal{R}$ . So we conclude that S defends the argument a in $\mathit{A}\mathit{F}$ . □

Proposition 2 (Dung Compatibility).

Let $\mathit{A}\mathit{F}=⟨\mathcal{A}\mathrm{,}\mathcal{R}⟩$ be a Dung’s AF, and ${\mathit{StrAF}}_{\mathit{A}\mathit{F}}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{S}⟩$ , with $coval=\sum$ , its associated StrAF. For $\mathit{\sigma }\in \{cf\mathrm{,}ad\mathrm{,}pr\mathrm{,}st\}$ , $\mathit{\sigma }\mathrm{(}\mathit{A}\mathit{F}\mathrm{)}={\mathit{\sigma }}_{\mathit{S}}\mathrm{(}{\mathit{StrAF}}_{\mathit{A}\mathit{F}}\mathrm{)}$ .

Proof.

The proof follows from Definition 11, Lemma 1 and Lemma 2. □

This result holds for any semantics based on conflict-freeness and defence, including those which are out of the scope of this paper. From the above, and the observation that for a StrAF associated with a Dung’s theory $\mathit{A}\mathit{F}$ , the notions of strong and weak conflict-freeness coincide, we easily obtain the following corollary.

Corollary 1.

Let $\mathit{A}\mathit{F}$ be a Dung’s AF, and ${\mathit{StrAF}}_{\mathit{A}\mathit{F}}$ its associated StrAF. For $\mathit{\sigma }\in \{cf\mathrm{,}ad\mathrm{,}pr\mathrm{,}st\}$ , $\mathit{\sigma }\mathrm{(}\mathit{A}\mathit{F}\mathrm{)}={\mathit{\sigma }}_{\mathit{W}}\mathrm{(}\mathit{StrA}{F}_{AF}\mathrm{)}$ .

Proposition 2 and Corollary 1 are major tools for providing hardness results in the complexity study of StrAFs, in the next Section.

5. Complexity and algorithms

This section discusses the complexity of various reasoning problems for StrAFs as well as algorithms for solving them. In the rest of the paper, we assume that coval is tractable, i.e. it can be computed in polynomial time. Usual aggregation operators (like ∑, Π or max) are tractable. We suppose that the reader is familiar with the basic notions of complexity theory; for more details about this topic, we refer the reader to e.g. [6].

5.1. Complexity of acyclic frameworks

A $\mathit{StrAF}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{S}⟩$ is acyclic if the relation $\mathcal{R}$ is acyclic. Recall that Dung’s acyclic argumentation frameworks have exactly one stable extension. The following example shows that this is not the case for StrAFs under the strong stable semantics.

Example 8.

Let $\mathit{StrAF}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{S}⟩$ be a StrAF with $\mathcal{A}=\{\mathit{a}\mathrm{,}\mathit{b}\}$ , $\mathcal{R}=\{\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\}$ , $\mathcal{S}\mathrm{(}\mathit{a}\mathrm{)}=1$ , $\mathcal{S}\mathrm{(}\mathit{b}\mathrm{)}=2$ . For $coval=\sum$ , we have ${st}_{\mathit{S}}^{\mathrm{\Sigma }}\mathrm{(}\mathit{StrAF}\mathrm{)}=\varnothing$ , whereas ${st}_{\mathit{W}}^{\mathrm{\Sigma }}\mathrm{(}\mathit{StrAF}\mathrm{)}=\{\{\mathit{a}\mathrm{,}\mathit{b}\}\}$ .

In fact, we prove the existence of a weak stable extension for every acyclic StrAF, by providing Algorithm 1. Given $\mathit{StrAF}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{S}⟩$ and an argument $\mathit{a}\in \mathcal{A}$ , the set of attackers of a, denoted by ${\mathrm{\Gamma }}_{\mathit{StrAF}}^{-}\mathrm{(}\mathit{a}\mathrm{)}$ , is defined as ${\mathrm{\Gamma }}_{\mathit{StrAF}}^{-}\mathrm{(}\mathit{a}\mathrm{)}=\{\mathit{b}\mid \mathit{b}\in \mathcal{A}\text{ and }\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}\in \mathcal{R}\}$ . When $\mathit{StrAF}$ is clear from the context we write simply ${\mathrm{\Gamma }}^{-}\mathrm{(}\mathit{a}\mathrm{)}$ .

Algorithm 1:

Algorithm compute-acyclic-extension( $⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{S}⟩$ , coval)

Proposition 3 (Termination and Correctness for Acyclic StrAFs).

Algorithm  1 compute-acyclic-extension always terminates. The set E returned by the algorithm is the unique weak stable extension of the input acyclic $\mathit{StrAF}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{S}⟩$ with respect to coval.

Proof.

Let us first prove that Algorithm 1 always terminates. The only modifications of the argumentation graph are removals of arguments (step 6). One can remark that removing nodes from an acyclic graph leads to another acyclic graph. Thus, at each iteration of the loop, there is at least one non-attacked argument a that is added to ${\mathit{E}}^{\prime }$ (step 3). This implies that each iteration of the loop strictly decreases the size of $\mathcal{A}$ . After at most $|\mathcal{A}|$ iterations, $\mathcal{A}$ is guaranteed to be empty, so the algorithm terminates.

Now let us prove that the algorithm is correct. Let E be the set returned by Algorithm 1compute-acyclic-extension. Let us now suppose that E is not a weak stable extension of the input acyclic $\mathit{StrAF}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{S}⟩$ with respect to coval. According to Definition 11, we can have two cases. Case 1

E is not weakly conflict free. That means $\exists \mathit{\kappa }\subseteq \mathit{E}$ an accrual and $\exists \mathit{b}\in \mathit{E}$ such that $\mathit{\kappa }⊳\mathit{b}$ . This is impossible: since b is defeated, it implies that ${\mathrm{\Gamma }}^{-}\mathrm{(}\mathit{b}\mathrm{)}\ne \varnothing$ , thus b is not added to the sets ${\mathit{E}}^{\prime }$ and E (steps 3 and 4). Then, steps 5 and 6 exclude from $\mathcal{A}$ the argument b, so it will never be added to ${\mathit{E}}^{\prime }$ at the following iterations of the while loop.

Case 2

There exists an argument $\mathit{a}\in \mathcal{A}\setminus \mathit{E}$ such that $\forall \mathit{\kappa }\subseteq \mathit{E}$ , $\mathit{\kappa }⋫\mathit{a}$ . However, by construction, such an argument a is never added to ${\mathit{A}}^{\prime }$ (step 5), so it is not removed from $\mathcal{A}$ at step 6. At some point, all its attackers must have been removed, so ${\mathrm{\Gamma }}^{-}\mathrm{(}\mathit{a}\mathrm{)}=\varnothing$ ; this implies that a is added to E at some iteration of the loop (steps 3 and 4), which is a contradiction since by assumption $\mathit{a}\in \mathcal{A}\setminus \mathit{E}$ .

Thus E is a weak stable extension.

Now let us prove that E is the unique weak stable extension. Let us suppose that $\exists {\mathit{E}}^{\prime }\in {st}_{\mathit{W}}^{coval}\mathrm{(}\mathit{StrAF}\mathrm{)}$ such that $\mathit{E}\ne {\mathit{E}}^{\prime }$ . We show iteratively that such an extension ${\mathit{E}}^{\prime }$ contains exactly the same arguments than E, which is contradictory.

First, we observe that the non-empty set U of arguments that are unattacked in $\mathit{StrAF}$ is such that $\mathit{U}\subseteq \mathit{E}$ and $\mathit{U}\subseteq {\mathit{E}}^{\prime }$ . Indeed, these are the arguments that are added to E at the first iteration of the loop, step 3 and 4 of Algorithm 1. Since every unattacked argument a cannot be defeated by an accrual, it has to belong to every weak stable extension and in particular to ${\mathit{E}}^{\prime }$ . At this step, we observe that the set of arguments D that are defeated by any accrual $\mathit{\kappa }\subseteq \mathit{U}$ cannot belong to ${\mathit{E}}^{\prime }$ , since these arguments are defeated by some accrual in ${\mathit{E}}^{\prime }$ . These arguments are exactly the ones that are put aside from E by step 5 and 6 of Algorithm 1.

Since $\mathit{StrAF}$ is assumed to be acyclic, arguments that are defeated by some accrual in D cannot be defeated by some accruals that are not in D, and are then straightforwardly defended by some accrual in U. Thereby these arguments must belong to ${\mathit{E}}^{\prime }$ since they are defended by ${\mathit{E}}^{\prime }$ and moreover cannot be defeated by any defended accrual. We also observe that this arguments are the one added to E at steps 3 and 4 of the next iteration of Algorithm 1 following steps 5 and 6 which has put aside arguments of D.

This process then repeats iteratively until it terminates since $\mathcal{A}$ is finite and $\mathit{StrAF}$ is acyclic. One can observe that, at each step of this process, arguments added to E by Algorithm 1 must be in ${\mathit{E}}^{\prime }$ , and conversely arguments set aside by Algorithm 1 cannot belong to ${\mathit{E}}^{\prime }$ . We thus finally obtain that $\mathit{E}={\mathit{E}}^{\prime }$ which contradicts our assumption, and so E is the unique weak stable extension. □

Algorithm 1 is a polynomial time procedure when the set ${\mathit{A}}^{\prime }$ can be computed in polynomial time.

Proposition 4 (Extension Computation for Acyclic StrAFs).

Let $\mathit{StrAF}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{S}⟩$ be an acyclic StrAF and coval an aggregation operator. Computing a weak stable extension of $\mathit{StrAF}$ is polynomial.

Proof.

As it is explained in the proof of Proposition 3, we know that the number of iterations of the while loop is at most $|\mathcal{A}|$ . Determining the set ${\mathit{E}}^{\prime }$ of non-attacked arguments is doable in polynomial time, as well as the standard set operations at steps 4 and 6. Since coval is tractable, the computation of the set ${\mathit{A}}^{\prime }$ is also polynomial. This concludes the proof. □

We notice that Algorithm 1 corresponds to the well-known algorithm for computing the grounded extension in Dung’s theory. This is not surprising, since the stable semantics coincide with the single-status grounded semantics for acyclic graphs (as well as any reasonable semantics).

Although we know that strong stable extensions may not exist for acyclic graphs, we show that deciding whether they exist or not is tractable.

Proposition 5 (Extension Existence for Acyclic StrAFs).

Let $\mathit{StrAF}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{S}⟩$ be an acyclic StrAF and coval an aggregation operator. Deciding whether $\mathit{StrAF}$ has a strong stable extension is polynomial.

Proof.

We know that if $\mathit{StrAF}$ admits a strong stable extension, then it is also a weak stable extension. Since $\mathit{StrAF}$ is acyclic, it admits a single weak stable extension, which is the set polynomially computed by Algorithm 1. This set E (by definition of weak stable extensions) defeats every argument $\mathit{a}\in \mathcal{A}\setminus \mathit{E}$ . For deciding whether E is also the strong stable extension, we just have to check if it is strongly conflict-free; that can be done in polynomial time. □

Remark: Since there is a single weak stable extension, and computing this extension is polynomial (Proposition 4), both skeptical and credulous acceptance coincide for weak stable semantics, and are polynomial reasoning tasks. Similarly, Proposition 5 shows that, if a strong stable extension exists for an acyclic StrAF then it can be polynomially computed by Algorithm 1, and thus credulous (and skeptical) acceptance are polynomial as well.

5.2. Complexity of symmetric frameworks

Now we consider the case of symmetric StrAFs, i.e. frameworks for which $\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in \mathcal{R}$ if and only if $\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}\in \mathcal{R}$ . This corresponds to situations like the one depicted in Example 2 with John’s gardens problem. We prove here that, in spite of the specific structure of this subclass of StrAFs, reasoning is at the first level of the polynomial hierarchy (i.e. the same complexity as general StrAFs, as shown in Section 5.3).

First, we prove that strong and weak semantics coincide for symmetric StrAFs.

Proposition 6 (Weak/Strong Coincidence).

Let $\mathit{StrAF}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{S}⟩$ be a symmetric StrAF and coval an aggregation operator. ${cf}_{\mathit{S}}^{coval}\mathrm{(}\mathit{StrAF}\mathrm{)}={cf}_{\mathit{W}}^{coval}\mathrm{(}\mathit{StrAF}\mathrm{)}$ .

Proof.

We already know that ${cf}_{\mathit{S}}^{coval}\mathrm{(}\mathit{StrAF}\mathrm{)}\subseteq {cf}_{\mathit{W}}^{coval}\mathrm{(}\mathit{StrAF}\mathrm{)}$ (straightforward from the definition of strong and weak conflict-freeness). Now, let us prove the opposite inclusion, using reductio ad absurdum. We suppose that $\exists \mathit{E}\in {cf}_{\mathit{W}}^{coval}\mathrm{(}\mathit{StrAF}\mathrm{)}$ such that $\mathit{E}\notin {cf}_{\mathit{S}}^{coval}\mathrm{(}\mathit{StrAF}\mathrm{)}$ . This means that $\exists \mathit{a}\mathrm{,}\mathit{b}\in \mathit{E}$ such that $\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in \mathcal{R}$ . Since $\mathit{StrAF}$ is symmetric, we know that $\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}\in \mathcal{R}$ also holds. Now, if $\mathcal{S}\mathrm{(}\mathit{a}\mathrm{)}⩾\mathcal{S}\mathrm{(}\mathit{b}\mathrm{)}$ then $\{\mathit{a}\}{⊳}_{coval}\mathit{b}$ , otherwise $\mathcal{S}\mathrm{(}\mathit{b}\mathrm{)}\mathrm{>}\mathcal{S}\mathrm{(}\mathit{a}\mathrm{)}$ and then $\{\mathit{b}\}{⊳}_{coval}\mathit{a}$ . Whatever the situation, E is not weakly conflict-free, which is a contradiction. So we deduce that ${cf}_{\mathit{W}}^{coval}\mathrm{(}\mathit{StrAF}\mathrm{)}\subseteq {cf}_{\mathit{S}}^{coval}\mathrm{(}\mathit{StrAF}\mathrm{)}$ , and we conclude ${cf}_{\mathit{S}}^{coval}\mathrm{(}\mathit{StrAF}\mathrm{)}={cf}_{\mathit{W}}^{coval}\mathrm{(}\mathit{StrAF}\mathrm{)}$ . □

Proposition 6 implies that ${ad}_{\mathit{S}}^{coval}\mathrm{(}\mathit{StrAF}\mathrm{)}={ad}_{\mathit{W}}^{coval}\mathrm{(}\mathit{StrAF}\mathrm{)}$ , ${pr}_{\mathit{S}}^{coval}\mathrm{(}\mathit{StrAF}\mathrm{)}={pr}_{\mathit{W}}^{coval}\mathrm{(}\mathit{StrAF}\mathrm{)}$ and ${st}_{\mathit{S}}^{coval}\mathrm{(}\mathit{StrAF}\mathrm{)}={st}_{\mathit{W}}^{coval}\mathrm{(}\mathit{StrAF}\mathrm{)}$ , for any symmetric $\mathit{StrAF}$ and any coval.

Now we study credulous and skeptical reasoning; we show that deciding whether an argument belongs to some (respectively each) strong (or weak) extension is NP-complete (respectively coNP-complete).

Proposition 7 (Argument Acceptance for Symmetric StrAFs).

Let $\mathit{StrAF}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{S}⟩$ be a symmetric StrAF and coval an aggregation function. Given $\mathit{a}\in \mathcal{A}$ and $\mathit{X}\in \{\mathit{S}\mathrm{,}\mathit{W}\}$ ,

deciding whether $\exists \mathit{E}\in {st}_{\mathit{X}}\mathrm{(}\mathit{StrAF}\mathrm{)}$ such that $\mathit{a}\in \mathit{E}$ is NP -complete.

deciding whether $\forall \mathit{E}\in {st}_{\mathit{X}}\mathrm{(}\mathit{StrAF}\mathrm{)}$ , $\mathit{a}\in \mathit{E}$ is coNP -complete.

Proof.

It has been proven [38,39] that credulous (respectively skeptical) acceptance is NP-complete (respectively coNP-complete) for symmetric argumentation frameworks. From Proposition 2 and Corollary 1, we know that any argumentation framework can be associated with a StrAF that has exactly the same set of (weak or strong) extensions. So, for a symmetric $\mathit{A}\mathit{F}=⟨\mathcal{A}\mathrm{,}\mathcal{R}⟩$ and $\mathit{a}\in \mathcal{A}$ , we can define a symmetric StrAF such that its (weak or strong) stable extensions correspond to the stable extensions of $\mathit{A}\mathit{F}$ . So, a is credulously (respectively skeptically) accepted in $\mathit{A}\mathit{F}$ with respect to the stable semantics if and only if a is credulously (respectively skeptically) accepted in $\mathit{StrAF}$ with respect to (weak or strong) stable semantics. We can conclude that credulous (respectively skeptical) acceptance for StrAFs is NP-hard (respectively coNP-hard).

For NP-membership and coNP-membership, the proof is the same as for Proposition 12 in the case of general StrAFs. □

Proposition 8 (Extension Existence for Symmetric StrAFs).

Given $\mathit{StrAF}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{S}⟩$ a symmetric StrAF and coval an aggregation function, checking whether ${st}_{\mathit{X}}^{coval}\mathrm{(}\mathit{StrAF}\mathrm{)}\ne \varnothing$ isNP-complete, with $\mathit{X}\in \{\mathit{S}\mathrm{,}\mathit{W}\}$ .

Proof.

The NP-membership can be deduced from the fact the extension existence belongs to NP in the case of general StrAFs (see Proposition 11).

For proving NP-hardness, we use a reduction similar to the one proposed in [38]. Let us consider any $\mathit{A}\mathit{F}=⟨\mathit{A}\mathrm{,}\mathit{R}⟩$ . We define a symmetric StrAF such that its (weak or strong) stable extensions exactly coincide with the stable extensions of $\mathit{A}\mathit{F}$ . Formally, $\mathit{StrAF}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{S}⟩$ with:

$\mathcal{A}=\mathit{A}\cup {\mathit{A}}^{\prime }$ , where ${\mathit{A}}^{\prime }=\{{\mathit{x}}^{\prime }\mid \mathit{x}\in \mathit{A}\}$ , i.e. for any argument $\mathit{x}\in \mathit{A}$ , we create ${\mathit{x}}^{\prime }$ a copy of x;

$\mathcal{R}={\mathcal{R}}_1\cup {\mathcal{R}}_2\cup {\mathcal{R}}_3\cup {\mathcal{R}}_4$ , where

• ${\mathcal{R}}_1=\{\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}\mid \mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in \mathit{R}\}$ , i.e. all the attacks from $\mathit{A}\mathit{F}$ are made symmetric;

• ${\mathcal{R}}_2=\{\mathrm{(}\mathit{a}\mathrm{,}{\mathit{a}}^{\prime }\mathrm{)}\mathrm{,}\mathrm{(}{\mathit{a}}^{\prime }\mathrm{,}\mathit{a}\mathrm{)}\mid \mathit{a}\in \mathit{A}\}$ , i.e. each argument from $\mathit{A}\mathit{F}$ attacks (and is attacked by) its copy;

• ${\mathcal{R}}_3=\{\mathrm{(}\mathit{a}\mathrm{,}{\mathit{b}}^{\prime }\mathrm{)}\mathrm{,}\mathrm{(}{\mathit{b}}^{\prime }\mathrm{,}\mathit{a}\mathrm{)}\mid \mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in \mathit{R}\}$ , i.e. if a attacks b in $\mathit{A}\mathit{F}$ , then a attacks (and is attacked by) the copy of b;

• ${\mathcal{R}}_4=\{\mathrm{(}{\mathit{a}}^{\prime }\mathrm{,}{\mathit{a}}^{\prime }\mathrm{)}\mid {\mathit{a}}^{\prime }\in {\mathit{A}}^{\prime }\}$ , i.e. each copy is a self-attacking argument.

if $\exists \mathit{b}\in \mathit{A}$ such that $\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in \mathit{R}$ , then $\mathcal{S}\mathrm{(}\mathit{a}\mathrm{)}=\mathit{M}$ , with M an arbitrary large number ( $\mathit{M}⩾|\mathcal{A}|$ ), otherwise $\mathcal{S}\mathrm{(}\mathit{a}\mathrm{)}=1$ .

Figure 5 illustrates the reduction from an $\mathit{A}\mathit{F}$ to its corresponding symmetric StrAF.

Fig. 5.

An example of our reduction from $\mathit{A}\mathit{F}$ to $\mathit{StrAF}$ .

Let us prove that $st\mathrm{(}\mathit{A}\mathit{F}\mathrm{)}={st}_{\mathit{S}}\mathrm{(}\mathit{StrAF}\mathrm{)}$ . We start by the proof that $st\mathrm{(}\mathit{A}\mathit{F}\mathrm{)}\subseteq {st}_{\mathit{S}}\mathrm{(}\mathit{StrAF}\mathrm{)}$ . Let $\mathit{E}\in st\mathrm{(}\mathit{A}\mathit{F}\mathrm{)}$ be a stable extension of $\mathit{A}\mathit{F}$ . By definition, E is conflict-free in $\mathit{A}\mathit{F}$ . Moreover, by the definition of $\mathit{StrAF}$ , $\forall \mathit{a}\mathrm{,}\mathit{b}\in \mathit{A}$ , if $\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\notin \mathit{R}$ and $\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}\notin \mathit{R}$ , then $\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\notin \mathcal{R}$ and $\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}\notin \mathcal{R}$ : the construction of the $\mathit{StrAF}$ makes the attacks in $\mathit{A}\mathit{F}$ symmetrical, but no new conflicts are created. So E is strongly conflict-free in $\mathit{StrAF}$ .

Now, we need to prove that each argument $\mathit{a}\in \mathcal{A}\setminus \mathit{E}$ is defeated by an accrual $\mathit{\kappa }\subseteq \mathit{E}$ . Let us consider such an argument $\mathit{a}\in \mathcal{A}\setminus \mathit{E}$ .

If $\mathit{a}\in \mathit{A}\setminus \mathit{E}$ (i.e. a is an argument that belongs to $\mathit{A}\mathit{F}$ , not a copy), then (since E is a stable extension of $\mathit{A}\mathit{F}$ ) $\exists \mathit{b}\in \mathit{E}$ such that $\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}\in \mathit{R}$ . This implies that $\mathcal{S}\mathrm{(}\mathit{b}\mathrm{)}=\mathit{M}$ , so whatever the strength of a, $\mathcal{S}\mathrm{(}\mathit{b}\mathrm{)}⩾\mathcal{S}\mathrm{(}\mathit{a}\mathrm{)}$ . This means that $\{\mathit{b}\}⊳\mathit{a}$ , where $\{\mathit{b}\}$ is an accrual included in E.

Otherwise, $\mathit{a}\in {\mathit{A}}^{\prime }$ . This means that $\mathit{a}={\mathit{x}}^{\prime }$ , for some $\mathit{x}\in \mathit{A}$ . Moreover, by definition of $\mathit{StrAF}$ , $\mathcal{S}\mathrm{(}\mathit{a}\mathrm{)}=1$ .

• If $\mathit{x}\in \mathit{E}$ , since $\mathrm{(}\mathit{x}\mathrm{,}{\mathit{x}}^{\prime }\mathrm{)}\in \mathcal{R}$ , there is an accrual $\{\mathit{x}\}\subseteq \mathit{E}$ such that $\{\mathit{x}\}⊳{\mathit{x}}^{\prime }$ , i.e. $\{\mathit{x}\}⊳\mathit{a}$ .

• If $\mathit{x}\notin \mathit{E}$ , $\exists \mathit{y}\in \mathit{E}$ such that $\mathrm{(}\mathit{y}\mathrm{,}\mathit{x}\mathrm{)}\in \mathit{R}$ . This implies that $\mathrm{(}\mathit{y}\mathrm{,}{\mathit{x}}^{\prime }\mathrm{)}\in \mathcal{R}$ , thus $\{\mathit{y}\}⊳{\mathit{x}}^{\prime }$ , i.e. $\{\mathit{y}\}⊳\mathit{a}$ .

We can conclude that $\mathit{E}\in {st}_{\mathit{S}}\mathrm{(}\mathit{StrAF}\mathrm{)}$ , so $st\mathrm{(}\mathit{A}\mathit{F}\mathrm{)}\subseteq {st}_{\mathit{S}}\mathrm{(}\mathit{StrAF}\mathrm{)}$ .

Now, we prove that ${st}_{\mathit{S}}\mathrm{(}\mathit{StrAF}\mathrm{)}\subseteq st\mathrm{(}\mathit{A}\mathit{F}\mathrm{)}$ . Let E be a strong stable extension of $\mathit{StrAF}$ . First, we notice that there can be no argument ${\mathit{a}}^{\prime }\in {\mathit{A}}^{\prime }$ in the extension: each ${\mathit{a}}^{\prime }\in {\mathit{A}}^{\prime }$ attacks itself, so if ${\mathit{a}}^{\prime }\in \mathit{E}$ , then E is not strongly conflict-free, and thus E cannot be a strong stable extension. So $\mathit{E}\subseteq \mathit{A}$ .

Since E is strongly conflict-free in $\mathit{StrAF}$ , we can prove that E is conflict-free in $\mathit{A}\mathit{F}$ . Indeed, the construction of $\mathit{StrAF}$ from $\mathit{A}\mathit{F}$ only adds attacks (by making the conflicts symmetrical). So, if there is no attack between two arguments $\mathit{a}\mathrm{,}\mathit{b}\in \mathit{A}$ in $\mathit{StrAF}$ , it means that there is no attack between them in $\mathit{A}\mathit{F}$ either.

We still have to prove that E attacks each argument $\mathit{b}\in \mathit{A}\setminus \mathit{E}$ in $\mathit{A}\mathit{F}$ . Using reductio ad absurdum, we suppose that $\exists \mathit{b}\in \mathit{A}\setminus \mathit{E}$ such that b is not attacked by E in $\mathit{A}\mathit{F}$ , i.e. $\forall \mathit{a}\in \mathit{E}$ , $\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\notin \mathit{R}$ . This implies (by definition of $\mathit{StrAF}$ ) that, $\forall \mathit{a}\in \mathit{E}$ , $\mathrm{(}\mathit{a}\mathrm{,}{\mathit{b}}^{\prime }\mathrm{)}\notin \mathcal{R}$ . So $\nexists \mathit{\kappa }\subseteq \mathit{E}$ such that $\mathit{\kappa }⊳{\mathit{b}}^{\prime }$ : the copy ${\mathit{b}}^{\prime }$ of b is not attacked, and thus not defeated by E is $\mathit{StrAF}$ . So E is not a strong stable extension of $\mathit{StrAF}$ : this is a contradiction.

We can now conclude that $\mathit{E}\in st\mathrm{(}\mathit{A}\mathit{F}\mathrm{)}$ , so ${st}_{\mathit{S}}\mathrm{(}\mathit{StrAF}\mathrm{)}\subseteq st\mathrm{(}\mathit{A}\mathit{F}\mathrm{)}$ .

We have proven that $st\mathrm{(}\mathit{A}\mathit{F}\mathrm{)}={st}_{\mathit{S}}\mathrm{(}\mathit{StrAF}\mathrm{)}$ , which means that $st\mathrm{(}\mathit{A}\mathit{F}\mathrm{)}\ne \varnothing$ if and only if ${st}_{\mathit{S}}\mathrm{(}\mathit{StrAF}\mathrm{)}\ne \varnothing$ . And it is known that verifying whether an argumentation framework has at least one stable extension is a NP-hard problem [39]. So we can conclude that verifying whether a symmetric StrAF has at least one strong stable extension is a NP-hard problem. The result also holds for weak stable semantics, since weak and strong semantics coincide for symmetric StrAFs. □

While verifying the existence of at least one (strong or weak) stable extension is generally hard, even for symmetric StrAFs, we show that this problem is trivial in the case of irreflexive symmetric StrAFs, i.e. symmetric StrAFs where no self-attack appear. Indeed, Algorithm 2 is a simple (non-deterministic) polynomial time procedure that returns a strong stable extension of the irreflexive symmetric StrAF given as input. This algorithm proves the existence of strong, and therefore weak as well, stable extensions for every irreflexive symmetric StrAF.

Proposition 9 (Termination and Correctness for Symmetric StrAFs).

Algorithm  2 compute-symmetric-extension always terminates. Any set E returned by the algorithm is a strong (and weak) stable extension of the irreflexive symmetric $\mathit{StrAF}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{S}⟩$ with respect to coval.

Proof.

Let us first prove that the algorithm always terminates. For any $\mathit{StrAF}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{S}⟩$ , since $\forall \mathit{a}\in \mathcal{A}$ , $\mathcal{S}\mathrm{(}\mathit{a}\mathrm{)}\in \mathbb{N}$ , there is at least one argument such that $\mathcal{S}\mathrm{(}\mathit{a}\mathrm{)}$ is maximal. Exactly one of these arguments is selected at step 3, added to E, and removed from $\mathcal{A}$ at step 5. This means that every iteration of the while loop strictly decreases the size of $\mathcal{A}$ , thus the algorithm terminates in at most $|\mathcal{A}|$ iterations.

Algorithm 2:

Algorithm compute-symmetric-extension( $⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{S}⟩\mathrm{,}coval$ )

Now let us prove that the algorithm is correct. Let E be the set returned by some execution of Algorithm 2compute-symmetric-extension. Let us now suppose that E is not a strong stable extension of the input symmetric $\mathit{StrAF}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{S}⟩$ . According to Definition 11, we can have two cases. Case 1

E is not strongly conflict free. That means $\exists \mathit{a}\mathrm{,}\mathit{b}\in \mathit{E}$ such that $\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in \mathcal{R}$ . This is impossible: without loss of generality, let us suppose that a has been added to E before b. Then, b is removed from $\mathcal{A}$ at step 5, and it will never be added to E at the following iterations of the loop. Since the graph is symmetric, $\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in \mathcal{R}$ implies $\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}\in \mathcal{R}$ , so we observe the same situation if b is added in E before a.

Case 2

There exists an argument $\mathit{b}\in \mathcal{A}\setminus \mathit{E}$ that is not defeated by an accrual in E, i.e. $\forall \mathit{\kappa }\subseteq \mathit{E}$ , $\mathit{\kappa }⋫\mathit{b}$ . There are again several possible situations.

b is not attacked by E, i.e. $\forall \mathit{a}\in \mathit{E}$ , $\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\notin \mathcal{R}$ . Then b is never removed from $\mathcal{A}$ at step 5, this implies that b will be added to E. This is a contradiction with the assumption that $\mathit{b}\in \mathcal{A}\setminus \mathit{E}$ .

There are attacks from some arguments ${\mathit{a}}_1\mathrm{,}\dots \mathrm{,}{\mathit{a}}_{\mathit{k}}\in \mathit{E}$ towards b, such that $coval\mathrm{(}\mathit{\kappa }\mathrm{)}\ngeqq \mathcal{S}\mathrm{(}\mathit{b}\mathrm{)}$ , with $\mathit{\kappa }=\{{\mathit{a}}_1\mathrm{,}\dots \mathrm{,}{\mathit{a}}_{\mathit{k}}\}$ . If $\exists {\mathit{a}}_{\mathit{i}}\in \mathit{\kappa }$ such that $\mathcal{S}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}⩾\mathcal{S}\mathrm{(}\mathit{b}\mathrm{)}$ , then ${\mathit{\kappa }}^{\prime }=\{{\mathit{a}}_{\mathit{i}}\}$ is an accrual that defeats b, that is a contradiction with the assumption. So we can ensure that $\forall {\mathit{a}}_{\mathit{i}}\in \mathit{\kappa }$ , $\mathcal{S}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}\mathrm{<}\mathcal{S}\mathrm{(}\mathit{b}\mathrm{)}$ . In such a situation, b should have been selected and added to E before any argument ${\mathit{a}}_{\mathit{i}}$ . This is again a contradiction with the assumption that $\mathit{b}\in \mathcal{A}\setminus \mathit{E}$ .

Thus E is a strong stable extension, and therefore a weak stable extension. □

5.3. General complexity

Now we investigate the complexity of reasoning with general StrAFs. We first prove that verifying whether a set of arguments is a (strong or weak) stable extension is polynomial.

Proposition 10 (Extension Verification).

Let $\mathit{StrAF}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{S}⟩$ be a StrAF and coval an aggregation function. For $\mathit{E}\subseteq \mathcal{A}$ , checking whether $\mathit{E}\in {st}_{\mathit{X}}^{coval}\mathrm{(}\mathit{StrAF}\mathrm{)}$ , with $\mathit{X}\in \{\mathit{S}\mathrm{,}\mathit{W}\}$ , is polynomial.

Proof.

For $\mathit{E}\subseteq \mathcal{A}$ , we have to check whether E is strongly (or weakly) conflict-free.

For the case of strong conflict-freeness, we have to check that for any two $\mathit{a}\mathrm{,}\mathit{b}\in \mathit{E}$ , it holds that $\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\notin \mathcal{R}$ . This is polynomial and corresponds to checking conflict-freeness in Dung’s framework.

Weak conflict-freeness is verified by first computing the set ${\mathrm{\Gamma }}^{-}\mathrm{(}\mathit{a}\mathrm{)}=\{\mathit{b}\mid \mathit{b}\in \mathit{E}\text{ such that }\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}\in \mathcal{R}\}$ for each $\mathit{a}\in \mathit{E}$ , and then checking that it is not the case that $coval\mathrm{(}{\mathrm{\Gamma }}^{-}\mathrm{(}\mathit{a}\mathrm{)}\mathrm{)}⩾\mathcal{S}\mathrm{(}\mathit{a}\mathrm{)}$ . Since coval is assumed to satisfy the Accrual property (see Definition 7), $coval\mathrm{(}{\mathrm{\Gamma }}^{-}\mathrm{(}\mathit{a}\mathrm{)}\mathrm{)}\mathrm{<}\mathcal{S}\mathrm{(}\mathit{a}\mathrm{)}$ implies that for any accrual $\mathit{\kappa }\subseteq \mathit{E}$ that attacks a, $coval\mathrm{(}\mathit{\kappa }\mathrm{)}⩽coval\mathrm{(}{\mathrm{\Gamma }}^{-}\mathrm{(}\mathit{a}\mathrm{)}\mathrm{)}\mathrm{<}\mathcal{S}\mathrm{(}\mathit{a}\mathrm{)}$ , so $\mathit{\kappa }⋫\mathit{a}$ . All the above tests can be carried out in polynomial time.

Finally, for both weak and strong semantics the following check is needed. For every $\mathit{a}\notin \mathit{E}$ , the set ${\mathrm{\Gamma }}^{-}\mathrm{(}\mathit{a}\mathrm{)}=\{\mathit{b}\mid \mathit{b}\in \mathit{E}\text{ such that }\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}\in \mathcal{R}\}$ is computed. Then for each such a it is verified that $coval\mathrm{(}{\mathrm{\Gamma }}^{-}\mathrm{(}\mathit{a}\mathrm{)}\mathrm{)}⩾\mathcal{S}\mathrm{(}\mathit{a}\mathrm{)}$ . Again, these tests are computable in polynomial time. □

Computing stable extensions is a central problem in argumentation. Similar to the case of Dung’s theories, this problem is intractable for StrAFs. However, its complexity does not increase for StrAFs.

Proposition 11 (Extension Existence).

Given $\mathit{StrAF}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{S}⟩$ a StrAF and coval an aggregation function, checking whether ${st}_{\mathit{X}}^{coval}\mathrm{(}\mathit{StrAF}\mathrm{)}\ne \varnothing$ isNP-complete, with $\mathit{X}\in \{\mathit{S}\mathrm{,}\mathit{W}\}$ .

Proof.

It is known that verifying whether a Dung’s AF has at least one stable extension is NP-complete [39]. From Proposition 2 and Corollary 1, we know that any AF can be associated with a StrAF that has exactly the same set of (strong or weak) extensions. We can deduce that checking the existence of (strong or weak) stable extensions of a StrAF is at least as hard as checking the existence of stable extensions of an AF. So we conclude that it is NP-hard.

NP-membership follows from the polynomial complexity of Verification (see Proposition 10). □

Finally, we show that, likewise Dung’s AFs, credulous and skeptical acceptance are at the first level of the polynomial hierarchy.

Proposition 12 (Argument Acceptance).

Let $\mathit{StrAF}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{S}⟩$ be a StrAF and coval an aggregation function. Given $\mathit{a}\in \mathcal{A}$ ,

deciding whether $\exists \mathit{E}\in {st}_{\mathit{X}}\mathrm{(}\mathit{StrAF}\mathrm{)}$ such that $\mathit{a}\in \mathit{E}$ is NP -complete.

deciding whether $\forall \mathit{E}\in {st}_{\mathit{X}}\mathrm{(}\mathit{StrAF}\mathrm{)}$ , $\mathit{a}\in \mathit{E}$ is coNP -complete.

Proof.

Since credulous (respectively skeptical) argument acceptance is NP-hard (respectively coNP-hard) for the specific case of symmetric StrAFs (see Proposition 7), it is also NP-hard (respectively coNP-hard) in the general case.

For NP-membership of credulous acceptance, let $\mathit{E}\subseteq \mathcal{A}$ be a set of arguments such that $\mathit{a}\in \mathit{E}$ . Verifying whether E is a strong (or weak) stable extension is polynomial (Proposition 10); the conclusion follows.

For coNP-membership of skeptical acceptance, let $\mathit{E}\subseteq \mathcal{A}$ be a set of arguments such that $\mathit{a}\notin \mathit{E}$ . Again, verifying whether E is a strong (or weak) stable extension is polynomial; this concludes the proof. □

Computing the stable extensions of a StrAF is a challenging problem even when the aggregation function is $coval=\sum$ . The rest of this section presents an algorithm that finds the stable extensions of $\mathit{StrAF}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{S}⟩$ , with ∑ as the aggregation function, by translating their computation into a pseudo-Boolean constraint satisfaction problem.

A pseudo-Boolean constraint is an inequality of the form ${\sum }_{\mathit{i}}{\mathit{w}}_{\mathit{i}}{\mathit{v}}_{\mathit{i}}⩾\mathit{k}$ , where ${\mathit{w}}_{\mathit{i}}$ and k are positive integers, and ${\mathit{v}}_{\mathit{i}}$ is a variable that may assume the values 0 and 1. Nowadays, there are several systems that can solve pseudo-Boolean constraint satisfaction problems (e.g.SAT4J [47], OpenWBO [52], RoundingSat [41]), many of which draw on the power of efficient SAT solving techniques.

Weak semantics. We start with weak stable semantics. Given $\mathit{StrAF}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{S}⟩$ and $coval=\sum$ , we associate a pseudo-Boolean constraint satisfaction problem $\mathit{C}{\mathit{S}}_{\mathit{W}}\mathrm{(}\mathit{StrAF}\mathrm{)}=\mathrm{(}\mathit{X}\mathrm{,}\mathit{C}\mathrm{)}$ , defined as follows:

• with each argument ${\mathit{a}}_{\mathit{i}}\in \mathcal{A}$ we associate a Boolean variable ${\mathit{x}}_{\mathit{i}}\in \mathit{X}$ ;

• the set of constraints C is as follows:

Intuitively, ${\mathit{x}}_{\mathit{i}}$ is true means that the corresponding argument ${\mathit{a}}_{\mathit{i}}$ belongs to an extension. Each solution of the problem corresponds then to one extension of the StrAF.

The value ${\mathit{M}}^{\mathit{a}}$ that is associated with an argument $\mathit{a}\in \mathcal{A}$ in constraint (1) is an integer such that ${\mathit{M}}^{\mathit{a}}\mathrm{>}{\sum }_{{\mathit{a}}_{\mathit{i}}\in {\mathrm{\Gamma }}^{-}\mathrm{(}\mathit{a}\mathrm{)}}\mathcal{S}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}$ . The purpose that ${\mathit{M}}^{\mathit{a}}$ serves is to “neutralize” constraint (1) when the variable x receives the value 0. Indeed, depending on the value of x, constraint (1) can be understood as follows.

if $\mathit{x}=0$ , the constraint becomes ${\sum }_{{\mathit{a}}_{\mathit{i}}\in {\mathrm{\Gamma }}^{-}\mathrm{(}\mathit{a}\mathrm{)}}\mathcal{S}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}\times {\mathit{x}}_{\mathit{i}}\mathrm{<}{\mathit{M}}^{\mathit{a}}$ , which is satisfied regardless of the values assigned to the variables ${\mathit{x}}_{\mathit{i}}$ , since ${\sum }_{{\mathit{a}}_{\mathit{i}}\in {\mathrm{\Gamma }}^{-}\mathrm{(}\mathit{a}\mathrm{)}}\mathcal{S}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}\times {\mathit{x}}_{\mathit{i}}⩽{\sum }_{{\mathit{a}}_{\mathit{i}}\in {\mathrm{\Gamma }}^{-}\mathrm{(}\mathit{a}\mathrm{)}}\mathcal{S}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}$ and by construction ${\sum }_{{\mathit{a}}_{\mathit{i}}\in {\mathrm{\Gamma }}^{-}\mathrm{(}\mathit{a}\mathrm{)}}\mathcal{S}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}\mathrm{<}{\mathit{M}}^{\mathit{a}}$ . Therefore, in this case constraint (1) is inactive.

if $\mathit{x}=1$ , the constraint becomes ${\sum }_{{\mathit{a}}_{\mathit{i}}\in {\mathrm{\Gamma }}^{-}\mathrm{(}\mathit{a}\mathrm{)}}\mathcal{S}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}\times {\mathit{x}}_{\mathit{i}}\mathrm{<}\mathcal{S}\mathrm{(}\mathit{a}\mathrm{)}$ , requiring that $coval\mathrm{(}{\mathrm{\Gamma }}^{-}\mathrm{(}\mathit{a}\mathrm{)}\mathrm{)}\mathrm{<}\mathcal{S}\mathrm{(}\mathit{a}\mathrm{)}$ .

In other words, constraint (1) means that we can accept a only if it is stronger than its accepted attackers; roughly speaking, these attackers form an accrual that attacks a but cannot defeat it even collectively.

Constraint (2) can be understood as follows:

if $\mathit{x}=0$ , the constraint becomes $\mathcal{S}\mathrm{(}{\mathit{a}}_1\mathrm{)}\times {\mathit{x}}_1+\mathcal{S}\mathrm{(}{\mathit{a}}_2\mathrm{)}\times {\mathit{x}}_2+\cdots +\mathcal{S}\mathrm{(}{\mathit{a}}_{\mathit{n}}\mathrm{)}\times {\mathit{x}}_{\mathit{n}}⩾\mathcal{S}\mathrm{(}\mathit{a}\mathrm{)}$ , i.e. $coval\mathrm{(}{\mathrm{\Gamma }}^{-}\mathrm{(}\mathit{a}\mathrm{)}\mathrm{)}⩾\mathcal{S}\mathrm{(}\mathit{a}\mathrm{)}$ .

if $\mathit{x}=1$ , the constraint becomes $\mathcal{S}\mathrm{(}{\mathit{a}}_1\mathrm{)}\times {\mathit{x}}_1+\mathcal{S}\mathrm{(}{\mathit{a}}_2\mathrm{)}\times {\mathit{x}}_2+\cdots +\mathcal{S}\mathrm{(}{\mathit{a}}_{\mathit{n}}\mathrm{)}\times {\mathit{x}}_{\mathit{n}}⩾0$ , that is trivially satisfied; the constraint is inactive in this case.

Intuitively, this constraint can be interpreted as the fact that we can reject a only if its accepted attackers can join their respective strength to collectively overtake the strength of a. Roughly speaking, this means that there exists an accrual that defeats a.

Note that, when a has no attacker, constraint (2) becomes $0⩾\mathrm{(}1-\mathit{x}\mathrm{)}\times \mathcal{S}\mathrm{(}\mathit{a}\mathrm{)}$ , that can be rewritten into $\mathit{x}⩾1$ . This means that non-attacked arguments must be accepted.

The next proposition shows a direct correspondence between weak stable extensions of $\mathit{StrAF}$ and the solutions of the problem $\mathit{C}{\mathit{S}}_{\mathit{W}}\mathrm{(}\mathit{StrAF}\mathrm{)}$ .

Definition 13.

Given a set of arguments $\mathit{E}\subseteq \mathcal{A}$ , the Boolean assignment ${\mathit{\omega }}_{\mathit{E}}$ is defined, $\forall {\mathit{x}}_{\mathit{i}}\in \mathit{X}$ , by ${\mathit{\omega }}_{\mathit{E}}\mathrm{(}{\mathit{x}}_{\mathit{i}}\mathrm{)}=1$ if and only if ${\mathit{a}}_{\mathit{i}}\in \mathit{E}$ .

Proposition 13 (Computation for Weak Stable Semantics).

A set $\mathit{E}\subseteq \mathcal{A}$ is a weak stable extension of $\mathit{StrAF}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{S}⟩$ with respect to ∑ if and only if the assignment ${\mathit{\omega }}_{\mathit{E}}$ is a solution for $\mathit{C}{\mathit{S}}_{\mathit{W}}\mathrm{(}\mathit{StrAF}\mathrm{)}$ .

Example 9.

Consider ${\mathit{StrAF}}_{\mathrm{weak}}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{S}⟩$ described at Fig. 6(a). The numerical values close to the nodes represent the strength of arguments i.e. the function $\mathcal{S}\mathrm{(}·\mathrm{)}$ . We observe that this StrAF does not admit a strong stable extension, but weak stable extensions can be computed as follows.

If we set ${\mathit{M}}^{\mathit{a}}$ to 5 in all the constraints for simplicity, we obtain the following set of constraints: $$\begin{array}{l}3\times {\mathit{x}}_3\mathrm{<}1\times {\mathit{x}}_1+\mathrm{(}1-{\mathit{x}}_1\mathrm{)}\times 5\\ 1\times {\mathit{x}}_1\mathrm{<}2\times {\mathit{x}}_2+\mathrm{(}1-{\mathit{x}}_2\mathrm{)}\times 5\\ 1\times {\mathit{x}}_1+2\times {\mathit{x}}_2\mathrm{<}3\times {\mathit{x}}_3+\mathrm{(}1-{\mathit{x}}_3\mathrm{)}\times 5\\ 2\times {\mathit{x}}_2\mathrm{<}2\times {\mathit{x}}_4+\mathrm{(}1-{\mathit{x}}_4\mathrm{)}\times 5\\ 3\times {\mathit{x}}_3⩾\mathrm{(}1-{\mathit{x}}_1\mathrm{)}\times 1\\ 1\times {\mathit{x}}_1⩾\mathrm{(}1-{\mathit{x}}_2\mathrm{)}\times 2\\ 1\times {\mathit{x}}_1+2\times {\mathit{x}}_2⩾\mathrm{(}1-{\mathit{x}}_3\mathrm{)}\times 3\\ 2\times {\mathit{x}}_2+⩾\mathrm{(}1-{\mathit{x}}_4\mathrm{)}\times 2\end{array}$$ The above set of constraints has the solutions ${\mathit{S}}_1=\{{\mathit{x}}_1=1\mathrm{,}{\mathit{x}}_2=1\mathrm{,}{\mathit{x}}_3=0\mathrm{,}{\mathit{x}}_4=0\}$ , and ${\mathit{S}}_2=\{{\mathit{x}}_1=0\mathrm{,}{\mathit{x}}_2=1\mathrm{,}{\mathit{x}}_3=1\mathrm{,}{\mathit{x}}_4=0\}$ that correspond to ${st}_{\mathit{W}}^{\mathrm{\Sigma }}\mathrm{(}\mathit{StrA}{F}_{weak}\mathrm{)}=\{\{{\mathit{a}}_1\mathrm{,}{\mathit{a}}_2\}\mathrm{,}\{{\mathit{a}}_2\mathrm{,}{\mathit{a}}_3\}\}$ .

Fig. 6.

Two examples of StrAFs.

Strong semantics. For strong stable semantics, we use the encoding for weak stable semantics as a starting point. We only need to add a constraint for enforcing the strong conflict-freeness. Given $\mathit{StrAF}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{S}⟩$ and $coval=\sum$ , we associate a pseudo-boolean constraint satisfaction problem $\mathit{C}{\mathit{S}}_{\mathit{S}}\mathrm{(}\mathit{StrAF}\mathrm{)}=\mathrm{(}\mathit{X}\mathrm{,}\mathit{C}\mathrm{)}$ as follows:

• with each argument ${\mathit{a}}_{\mathit{i}}\in \mathcal{A}$ we associate a Boolean variable ${\mathit{x}}_{\mathit{i}}\in \mathit{X}$ ;

• the set of constraints C is as follows:

Constraints (1) and (2) have already be explained. Constraint (3) means that two conflicting arguments cannot be jointly accepted: this enforces (strong) conflict-freeness.

The next proposition shows that there is a direct correspondence between strong stable extensions of $\mathit{StrAF}$ and the solutions of the problem $\mathit{C}{\mathit{S}}_{\mathit{S}}\mathrm{(}\mathit{StrAF}\mathrm{)}$ .

Proposition 14 (Computation for Strong Stable Semantics).

A set $\mathit{E}\subseteq \mathcal{A}$ is strong stable extension of $\mathit{StrAF}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{S}⟩$ with respect to ∑ if and only if the assignment ${\mathit{\omega }}_{\mathit{E}}$ is a solution of $\mathit{C}{\mathit{S}}_{\mathit{S}}\mathrm{(}\mathit{StrAF}\mathrm{)}$ .

Example 10.

Consider ${\mathit{StrAF}}_{\mathrm{strong}}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{S}⟩$ described at Fig. 6(b). We observe that if we use the classical defeat-based semantics, neither ${\mathit{a}}_1$ nor ${\mathit{a}}_3$ can defeat ${\mathit{a}}_2$ , while our semantics sensitive to accruals give a different result. The computation of strong stable extensions is made as follows. We translate the StrAF into a set of pseudo-boolean constraints.

The three columns correspond respectively to constraints (1), (2) and (3). The only solution of this set of constraints is $\mathit{S}=\{{\mathit{x}}_1={\mathit{x}}_3={\mathit{x}}_4=1\mathrm{,}{\mathit{x}}_2=0\}$ , that corresponds to the unique strong stable extension $\mathit{E}=\{{\mathit{a}}_1\mathrm{,}{\mathit{a}}_3\mathrm{,}{\mathit{a}}_4\}$ .

We notice that ${\mathit{StrAF}}_{\mathrm{weak}}$ from Example 9 does not have any strong stable extension. Indeed, none of the solutions ${\mathit{S}}_1$ and ${\mathit{S}}_2$ that we exhibited previously satisfies the strong conflict-freeness constraint.

6. Related work

Several approaches have been proposed in the AI literature to model the accrual of arguments. Especially, in structured argumentation setting, [44,49,50,62,63] deal with accruals by adding a new argument that represents the accrual; these works consider that the arguments members of an accrual should not be taken into consideration on their own. On the other hand, [66] defines a formalism in which accruals are explicitly given, since conflicts are defined in terms of sets of arguments attacking other (sets of) arguments. The notions introduced in these works strongly rely on the internal structure of the arguments, whereas in abstract argumentation, which is the subject matter of our study, this structure is unknown.

Collective attacks have also been studied in abstract argumentation. In [42,57] the authors proposed a generalization of Dung’s abstract framework by presenting an abstract attack relation between sets of arguments and by extending the associated semantics. Similarly, in [23], n-ary conflicts are defined between sets of arguments that cannot be jointly accepted, while no explicit conflicts exist between these arguments. Besides, [19] defines collective argumentation frameworks where sets of arguments attacks sets of arguments. In [43,67], combined attacks (i.e. several arguments attacking a same target) are modelled through notions of joint attack or accrual patterns. In these works there is no notion of arguments strength (and thus, defeat relation) and then compensation as we do here.

In all the works cited previously (in both fields of structured and abstract argumentation) accruals of arguments need to be explicitly elicited as an input of the reasoning process. In other words, each existing accruals must be clearly identified before the reasoning step of the process, and all combinations of arguments must be taken into account when a new argument is provided to the system. On the contrary, in our work accruals appear as an output of the system, and are computed only from the attack relation and the arguments strength. Moreover, since in our work the elicitation of all accruals and preferences between sets of arguments is not necessary, our framework is more modular. Indeed, when new arguments are added to the framework or agents preferences are updated, the generation of new accruals or the loss of old ones is automatically handled by the behaviour of our semantics.

Another framework representing synergies of arguments is proposed in [45]. This framework proposes an extension of the value-based argumentation framework [10] by defining a defeat relation with varied strength. The strength of defeat of a subset A of arguments over another subset B of arguments depends then on the values promoted by A and B. This framework is also different to ours as in our framework the strength is associated with arguments and the collective strength of an accrual is computed through an aggregation operator that aggregates according to different ways the strengths of the individual arguments forming the accrual. Then this collective strength is used in the definition of a collective defeat relation that is used between subsets of arguments.

Abstract Dialectical Frameworks (ADFs) [21] associate to each abstract node x (called statement) an acceptance formula ${\mathit{\varphi }}_{\mathit{x}}$ built on variables that correspond to the parents of the node x in the graph. Such an acceptance formula can model collective attacks, e.g. a and b collectively attack c is modelled by ${\mathit{\varphi }}_{\mathit{c}}=\neg \mathit{a}\vee \neg \mathit{b}$ : if both a and b are accepted, then c is rejected (because ${\mathit{\varphi }}_{\mathit{c}}$ is false), otherwise c is accepted. However, ADFs cannot represent the notion of compensation between weak and strong arguments as we do. Moreover, the problem of explicit elicitation of collective defeats is the same as previously described. Although [22] extends ADFs by adding a notion of weight, it does not at all correspond to the strength of the arguments, but rather to the computation of a degree of acceptance for statements (in the spirit of gradual semantics [24]).

The idea of “collective support” between arguments is also explored in [26], where arguments participating in a coalition support (or help) each other against attacks from other arguments. However, this idea of an accrual of arguments with other arguments, especially when related to the notion of support, is quite different from our idea of “accrual” and “collective attack”. In our work, we consider that an accrual of arguments defends a common position on a matter which is defended individually by each of the participating arguments (by expressing a different point of view). The motivation of an accrual is not to create a mutual support among the participating arguments. We consider that this is rather closer to the notion of “extension”. In our work, arguments form an accrual in order to defeat a common adversary that none of them can defeat alone. Thus, the accrual forms a compound unified attack incorporating different points of view (or dimensions) against a single argument or a set of arguments defending a conflicting position.

We have mentioned previously that several works attach a weight to arguments (see e.g. [2,8,9,48,55,61]). The meaning of these weights can be the votes of users, some notion of trust, or the certainty about the arguments premises. However, all these works strongly differ from ours since they intend to define a ranking or an acceptance degree of arguments. They focus on the individual acceptance of arguments, while the extension-based semantics that we define in this paper correspond to a notion of joint acceptance. Moreover, these works do not study collective defeat and accrual of arguments.

Recently, in [30,31,37] the authors investigated aggregation of weights in weighted argumentation systems. However, in this framework weights are associated with attack relations and are not involved in the definition of a defeat relation applied for accruals like in our framework. Moreover, none of the above works has investigated in depth the theoretical and computational properties of the proposed approaches for compound attacks. Similarly to both papers cited above, [51] defines attacks of different strength. The paper generalizes the notion of defense by setting conditions about the relative strength of attackers and defenders in order to generalize Dung’s semantics. The concepts of collective attacks or accrual of arguments are not studied there. Finally, [16] defines a notion of collective attack by the aggregation of weights associated with these attacks. In this framework, if both a and b attack an argument c, respectively with strength m and n, then the strength of the collective attack from $\{\mathit{a}\mathrm{,}\mathit{b}\}$ to c is the result of aggregating m and n (e.g. $\mathit{m}+\mathit{n}$ ). Nevertheless, this notion of collective attack is there used to relax the notion of defence, and this work does not address the notion of individual/collective attack/defeat like our approach.

7. Conclusion and future work

In this paper, we have proposed an intuitive framework for representing strength of arguments called Strength-based Argumentation Framework. We use the numerical strength of arguments to define extension-based semantics based on a defeat relation, that is the combination of the initial attacks between arguments and the comparison of their respective strengths. We have shown how quantitative strengths can be aggregated when several arguments attack a same target, making an accrual of arguments. The definition of collective defeat has allowed us to define new semantics that lead to interesting extensions that cannot be obtained when the usual Dung’s AFs or individual defeat are used.

We have established the complexity of several reasoning problems for special cases (acyclic and symmetric graphs) as well as general StrAFs. Surprisingly, we notice that, while our framework can model situations that are not captured by Dung’s AFs without a blow up of the framework size, the complexity of reasoning does not increase. Table 2 summarizes our results for (strong and weak) stable semantics. P stands for polynomial, while X-c means X-complete where X is either NP or coNP. We say that a problem is trivial when the answer is straightforwardly “yes”. We recall that all these results hold under the assumption that coval can be computed in polynomial time.

Table 2

Summary of complexity results for (strong and weak) stable semantics

	Acyclic		Symmetric		General
	Strong	Weak	Strong	Weak	Strong	Weak
Verification	P	P	P	P	P	P
Existence	P	Trivial	NP-c	NP-c	NP-c	NP-c
Credulous	P	P	NP-c	NP-c	NP-c	NP-c
Skeptical	P	P	coNP-c	coNP-c	coNP-c	coNP-c

Our complexity results only concern the (strong and weak) stable semantics. For the case of weak semantics, they remind the complexity results for AFs with collective attacks [40]. We plan to deepen this investigation and consider other semantics as well, especially for the strong versions since the weak versions can be deduced from [40]. Moreover, regarding symmetric StrAFs, we have proven that extension existence is a trivial problem if we only consider irreflexive attack relations, i.e. no self-attacking arguments belong to the StrAF. It is known that reasoning with irreflexive symmetric AFs is polynomial [28]. We will investigate this question for irreflexive StrAFs, and determine whether self-attacks are the source of NP (or coNP) hardness for symmetric StrAFs, as they are in the case of symmetric AFs.

Weak extensions make sense for applications where conflicts are expected between pieces of information, but these pieces of information appear to be not strong enough to actually exclude each other. In other words, evaluation of these conflicts does not lead to reject some of the involved pieces of information which thus can be accepted together. However, in the case of logic-based argumentation, the loss of (strong) conflict-freeness may lead to problems with the inference defined from the argumentation framework if two arguments belong to the same extension while one of them undercuts the other one. We plan to refine the notion of weak conflict-freeness according to this idea, similarly to the refinement of Preference-based AFs [5].

In Section 5.1, we have stated that acyclic StrAFs have exactly one (strong or weak) stable extension. This is reminiscent to known results for classical AFs [35], or argumentation frameworks with weighted attacks [17,18]. These papers prove that (in these frameworks) the four classical semantics introduced by Dung (namely grounded, complete, preferred and stable) coincide for well-founded frameworks. The formal definition and study of the relations between these semantics in our framework is a promising track for future research.

We plan to study the logical properties of our accrual-based semantics with respect to the properties of coval operators. Different properties may be suited to different applications scenarios, thus indicating which coval operators to choose depending on the application domain or the nature of arguments.

As mentioned in Section 4.1, we have focused in this work on situations where arguments strengths are commensurable from an argument to another. Again, this assumption allows to directly compare strengths associated with different arguments, and it thus makes sense to then aggregate them to compute the strength associated with an accrual. However, this assumption may appear to be too strong for many interesting real-world applications, for example when weights represent subjective opinions or judgments, or when they are provided by different sources which do not share the meaning they associate with weights. We will investigate strategies adapted to applications where such commensurability assumption over strengths associated with arguments is dropped.

Lastly, frameworks where arguments are built from logical formulas or rules have received a lot of attention [13,36,46]. On the other hands, some logical frameworks allow representation of weighted pieces of information [34,58]. A natural question is then the generation of structured arguments from such weighted logics, and then whether and how such structured arguments can be combined in accruals.