You are viewing a javascript disabled version of the site. Please enable Javascript for this site to function properly.
Go to headerGo to navigationGo to searchGo to contentsGo to footer
In content section. Select this link to jump to navigation

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 A,R, where A is a set of arguments, and RA×A is an attack relation. The relation a attacks b, or b is attacked by a, is denoted by (a,b)R. We focus on finite argumentation frameworks, i.e. AFs such that 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

Definition 1(Defence/Conflict-freeness).

Let AF=A,R be an argumentation system. Let SA.

  • S is conflict-free if and only if ∄ a,bS s.t (a,b) R.

  • S defends aA if and only if ∀ bA, if (b,a)R, then cS such that (c,b)R.

The set of all conflict-free sets of AF is denoted cf(AF).

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

Definition 2(Acceptability semantics).

Let AF=A,R be an AF and Scf(AF).

  • 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 AS.

The sets of admissible, preferred and stable extensions are respectively denoted by ad(AF), pr(AF) and st(AF).

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 AFjohn 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 AFjohn2 (Fig. 1(b)).

The extensions of AFjohn and AFjohn2 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.

Both versions of John’s garden situation.
Table 1

Extensions of AFjohn and AFjohn2

σσ(AFjohn)
cf, ad, {A}, {B}, {C}, {D}, {E}, {F}, {A,C}, {A,D}, {A,E}, {A,F},
{B,C}, {B,D}, {B,E}, {B,F}, {C,E}, {C,F}, {D,E}, {D,F}
{A,C,E}, {A,C,F}, {A,D,E}, {A,D,F}, {B,C,E}, {B,C,F}, {B,D,E}, {B,D,F}
pr, st{A,C,E}, {A,C,F}, {A,D,E}, {A,D,F}, {B,C,E}, {B,C,F}, {B,D,E}, {B,D,F}
σσ(AFjohn2)
cf, ad, {A}, {B}, {C}, {D}, {E}, {F}, {A,E}, {B,E}, {C,E}, {D,E},{A,F}, {B,F}, {C,F}, {D,F},
{A,C}, {A,D}, {B,D}, {C,D},{A,C,E}, {A,D,E}, {B,D,E}, {C,D,E},
{A,C,F}, {A,D,F}, {B,D,F}, {C,D,F}, {A,C,D}, {A,C,D,E}, {A,C,D,F}
pr, st{A,C,D,E}, {A,C,D,F}, {B,D,E}, {B,D,F}

Notice that cf(AFjohn)=ad(AFjohn) and pr(AFjohn)=st(AFjohn) (and similarly for AFjohn2). This comes from the fact that these AFs are symmetric [28]. This is not the case in general, but it is well-known that AF, st(AF)pr(AF)ad(AF)cf(AF). 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

Definition 3(Strength-based Argumentation Framework).

A Strength-based Argumentation Framework (StrAF) is a triple A,R,S where A and R are respectively arguments and attacks, and S:AN 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 AFjohn and AFjohn2, we can define StrAFs StrAFjohn=Ajohn,Rjohn,Sjohn and StrAFjohn2=Ajohn,Rjohn2,Sjohn described at Fig. 2, where S(A)=S(C)=S(E)=40, S(B)=S(F)=60 and S(D)=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.

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

Definition 4(Defeat Relation and Extension Semantics).

Given StrAF=A,R,S a StrAF, the defeat relation Def is defined by Def={(a,b)RS(b)S(a)}.

Extension-based semantics of StrAF can be defined by considering the extensions of the classical AF DefAF=A,Def, i.e. σ(StrAF)=σ(DefAF) for σ{cf,ad,pr,st}.1

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 StrAFjohn and StrAFjohn2, we describe below the graphs corresponding to the defeat relation.

In the case of DefAFjohn (Fig. 3(a)), we observe that using the defeat relation leads to an intuitive result: for any semantics σ{ad,pr,st} as introduced in Definition 2, the single extension is {B,D,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 σ{ad,pr,st} gives σ(AFjohn2)={B,D,F}; this option is worth 200 Euros and is not optimal (indeed {A,C,D,F} is an extension of AFjohn2, and is worth 220 Euros).

Fig. 3.

Defeat graphs for John’s garden situation.

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 DefAFjohn2. 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 StrAF=A,R,S be a StrAF. A set of arguments κA is called accrual if and only if cA such that ∀ aκ, (a,c)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 StrAFjohn2 describing John’s situation (see Example 2), there is (for instance) an accrual κ={A,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 κ if and only if there exists an argument in κ such that all arguments of κ attack this argument. Formally:

Definition 6.

Let StrAF=A,R,S be a StrAF, and κA, κA two accruals. Then, κ attacks κ if and only if aκ such that κ attacks a.

We then define the collective strength associated with an accrual κ, denoted by coval(κ), as the combination of values associated with arguments. Formally:

Definition 7.

Let StrAF=A,R,S be a StrAF and κ={a1,,an}A be an accrual. Then the collective strength associated with κ is:

coval(κ)=coval(S(a1),,S(an))
where coval is an aggregation operator, i.e. a mapping from a vector of integers to an integer that satisfies:

(non-decreasingness)

if xixi, then coval(x1,,xi,,xn)coval(x1,,xi,,xn);

(minimality)

coval(x1,,xn)=0 if and only if x1==xn=0;

(identity)

coval(x)=x;

(accrual)

coval(x1,,xn)coval(x1,,xn,y).

These properties are quite natural for defining the strength of an accrual. Non-decreasingness means that, if aκ and bκ, then the accrual κ{a} is stronger than the accrual κ{b} when a is stronger than b. Minimality states that the accumulation of arguments “without” strength (i.e. S(ai)=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,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 StrAF=A,R,S be a StrAF, aA, and coval an aggregation operator. Then, an accrual κ defeats a with respect to coval, denoted by κcovala, if and only if

  • κA is an accrual that attacks a;

  • coval(κ)S(a).

If coval is clear from the context, we use κa instead of κcovala.

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

Definition 9.

Let StrAF=A,R,S be a StrAF, coval an aggregation operator and κA, κA two accruals. Then κ defeats κ, denoted by κκ, if and only if there exists aκ such that κ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 S of arguments is defined as the aggregation of strengths associated with all the attacks from any argument in S to any argument in S. 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 S. 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=, 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 StrAFjohn2, the accruals κ1={B} and κ2={A,C} defeat each other. Indeed, coval(κ1)=S(B)=60S(A), while coval(κ2)=S(A)+S(C)=80S(B).

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.

The StrAF that describes the situation of Joe and Jack.

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

  • A1: “Joe does not like Jack”;

  • A2: “There is a nail in Jack’s antique coffee table”;

  • A3: “Joe hammered a nail into Jack’s antique coffee table”;

  • A4: “Joe plays golf, so Joe has full use of his arms”;

  • A5: “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 A5 directly attacks (and thus defeats) the argument A3, whereas arguments A3 and A4 directly attack (and also defeat) the argument A5.

On another hand, authors in [57] discuss that arguments A1 and A2 attack the argument A5 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, A1 and A2 may constitute a stronger argument that defeats A5. These examples of attacks are illustrated by Fig. 4.

In our framework, let xi be the strength associated with the argument Ai, for i{1,,5}. Let us assume that x3=x5 (since A3 and A5 defeat each other), and x4x5 (since A4 defeat A5). Several cases are then possible:

  • either strengths associated with arguments are such that either x1x5 or x2x5: in this case, either the argument A1 or the argument A2 is considered solid enough to individually defeat the argument A5;

  • either strengths associated with arguments are such that x1<x5, x2<x5 and x1+x2x5: in this case arguments A1 and A2 are too weak to defeat individually argument A5 but form an accrual to collectively defeat it;

  • or finally strengths associated with arguments are such that x1<x5, x2<x5 and x1+x2<x5: in this case arguments A1 and A2 cannot defeat A5 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 A1, A2 and A5, A1 and A2 can individually or collectively defeat A5 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

Definition 10(Defence/Conflict-freeness).

Let StrAF=A,R,S be a StrAF, coval an aggregation operator, and SA.

  • S is strongly conflict-free if and only if a,bS such that (a,b)R.

  • S is weakly conflict-free if and only if there are no accruals κ1S and κ2S such that κ1covalκ2.

  • S defends an element aA if and only if for all accruals κ1A, if κ1covala, then there exists an accrual κ2S such that κ2covalκ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

Definition 11(Acceptability semantics).

Let StrAF=A,R,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 aAS, there is an accrual κS such that κa.

For any semantics σ{cf,ad,pr,st}, the set of strong (respectively weak) σ extension of StrAF=A,R,S with respect to coval is denoted by σScoval(StrAF) (respectively σWcoval(StrAF)). 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 σS(StrAF)σW(StrAF) for any semantics σ.

We also remark a relation between weak semantics of StrAFs and semantics of AFs with collective attacks [57]. Indeed, if κ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

Proposition 1(Semantics Inclusion).

Let StrAF=A,R,S be a StrAF and coval an aggregation operator. For X{S,W}, stX(StrAF)prX(StrAF)adX(StrAF).

Proof.

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

Let EA be a strong (respectively weak) stable extension of StrAF=A,R,S with respect to coval, i.e. aAS, there is an accrual κE such that κa.

First we prove that E is a strong (respectively weak) admissible extension. Let κA be an accrual such that κa, with aE. There are two cases.

Case 1

κE implies that E is neither strongly nor weakly conflict-free, this is a contradiction.

Case 2

κE implies that bκE, and since E is a strong (respectively weak) stable extension, Eb holds. Thus Eκ, 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 EA a strong (respectively weak) admissible extension such that EE. So aEE. We have previously established that κEE is such that κa, so E is not weakly conflict-free, and therefore not strongly conflict-free. This is a contradiction with the fact that E 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 StrAFjohn and StrAFjohn2, with coval=. It is easy to see that stSΣ(StrAFjohn)={{B,D,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 stSΣ(StrAFjohn2)={{A,C,D,F},{B,D,F}}. We observe that the optimal solution {A,C,D,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 AF=A,R, the StrAF associated with AF is StrAFAF=A,R,S with S(a)=1, aA and coval=.

Lemma 1.

Let AF=A,R be a Dung’s AF, and StrAFAF=A,R,S its associated StrAF. The set SA is conflict-free in AF if and only if it is strongly conflict-free in StrAFAF.

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

Lemma 2.

Let AF=A,R be a Dung’s AF, and StrAFAF=A,R,S its associated StrAF. The set SA defends the argument aA in AF if and only if SA defends the argument aA in StrAFAF.

Proof.

Let us suppose that SA defends the argument aA in AF. This means that for each bA such that (b,a)R, cS such that (c,b)R.

Now, let us consider an accrual κ1A such that κ1a. As established previously, bκ1, cS such that (c,b)R, i.e. κ2={c}S such that κ2 attacks b. Since coval(κ2)=S(c)=1=S(b), κ2b and thus κ2κ1. So S defends the argument a in StrAFAF.

Now we suppose that SA defends the argument aA in StrAFAF, i.e. for all accruals κ1 that defeat a, κ2S such that κ2κ1. Since all arguments strengths are equal to 1, every argument bA attacking a corresponds to an accrual κ1={b} defeating a. So κ2S such that κ2κ1={b}, and thus cκ2S such that (c,b)R. So we conclude that S defends the argument a in AF. □

Proposition 2

Proposition 2(Dung Compatibility).

Let AF=A,R be a Dung’s AF, and StrAFAF=A,R,S, with coval=, its associated StrAF. For σ{cf,ad,pr,st}, σ(AF)=σS(StrAFAF).

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 AF, the notions of strong and weak conflict-freeness coincide, we easily obtain the following corollary.

Corollary 1.

Let AF be a Dung’s AF, and StrAFAF its associated StrAF. For σ{cf,ad,pr,st}, σ(AF)=σW(StrAFAF).

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 StrAF=A,R,S is acyclic if the relation 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 StrAF=A,R,S be a StrAF with A={a,b}, R={(a,b)}, S(a)=1, S(b)=2. For coval=, we have stSΣ(StrAF)=, whereas stWΣ(StrAF)={{a,b}}.

In fact, we prove the existence of a weak stable extension for every acyclic StrAF, by providing Algorithm 1. Given StrAF=A,R,S and an argument aA, the set of attackers of a, denoted by ΓStrAF(a), is defined as ΓStrAF(a)={bbA and (b,a)R}. When StrAF is clear from the context we write simply Γ(a).

Algorithm 1:

Algorithm compute-acyclic-extension(A,R,S, coval)

Algorithm compute-acyclic-extension(⟨A,R,S⟩, coval)
Proposition 3

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 StrAF=A,R,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 E (step 3). This implies that each iteration of the loop strictly decreases the size of A. After at most |A| iterations, 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 1 compute-acyclic-extension. Let us now suppose that E is not a weak stable extension of the input acyclic StrAF=A,R,S with respect to coval. According to Definition 11, we can have two cases.

Case 1

E is not weakly conflict free. That means κE an accrual and bE such that κb. This is impossible: since b is defeated, it implies that Γ(b), thus b is not added to the sets E and E (steps 3 and 4). Then, steps 5 and 6 exclude from A the argument b, so it will never be added to E at the following iterations of the while loop.

Case 2

There exists an argument aAE such that κE, κa. However, by construction, such an argument a is never added to A (step 5), so it is not removed from A at step 6. At some point, all its attackers must have been removed, so Γ(a)=; 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 aAE.

Thus E is a weak stable extension.

Now let us prove that E is the unique weak stable extension. Let us suppose that EstWcoval(StrAF) such that EE. We show iteratively that such an extension E 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 StrAF is such that UE and UE. 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 E. At this step, we observe that the set of arguments D that are defeated by any accrual κU cannot belong to E, since these arguments are defeated by some accrual in E. These arguments are exactly the ones that are put aside from E by step 5 and 6 of Algorithm 1.

Since 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 E since they are defended by E 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 A is finite and StrAF is acyclic. One can observe that, at each step of this process, arguments added to E by Algorithm 1 must be in E, and conversely arguments set aside by Algorithm 1 cannot belong to E. We thus finally obtain that E=E which contradicts our assumption, and so E is the unique weak stable extension. □

Algorithm 1 is a polynomial time procedure when the set A can be computed in polynomial time.

Proposition 4

Proposition 4(Extension Computation for Acyclic StrAFs).

Let StrAF=A,R,S be an acyclic StrAF and coval an aggregation operator. Computing a weak stable extension of 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 |A|. Determining the set E 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 A 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

Proposition 5(Extension Existence for Acyclic StrAFs).

Let StrAF=A,R,S be an acyclic StrAF and coval an aggregation operator. Deciding whether StrAF has a strong stable extension is polynomial.

Proof.

We know that if StrAF admits a strong stable extension, then it is also a weak stable extension. Since 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 aAE. 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 (a,b)R if and only if (b,a)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

Proposition 6(Weak/Strong Coincidence).

Let StrAF=A,R,S be a symmetric StrAF and coval an aggregation operator. cfScoval(StrAF)=cfWcoval(StrAF).

Proof.

We already know that cfScoval(StrAF)cfWcoval(StrAF) (straightforward from the definition of strong and weak conflict-freeness). Now, let us prove the opposite inclusion, using reductio ad absurdum. We suppose that EcfWcoval(StrAF) such that EcfScoval(StrAF). This means that a,bE such that (a,b)R. Since StrAF is symmetric, we know that (b,a)R also holds. Now, if S(a)S(b) then {a}covalb, otherwise S(b)>S(a) and then {b}covala. Whatever the situation, E is not weakly conflict-free, which is a contradiction. So we deduce that cfWcoval(StrAF)cfScoval(StrAF), and we conclude cfScoval(StrAF)=cfWcoval(StrAF). □

Proposition 6 implies that adScoval(StrAF)=adWcoval(StrAF), prScoval(StrAF)=prWcoval(StrAF) and stScoval(StrAF)=stWcoval(StrAF), for any symmetric 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

Proposition 7(Argument Acceptance for Symmetric StrAFs).

Let StrAF=A,R,S be a symmetric StrAF and coval an aggregation function. Given aA and X{S,W},

  • deciding whether EstX(StrAF) such that aE is NP-complete.

  • deciding whether EstX(StrAF), aE 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 AF=A,R and aA, we can define a symmetric StrAF such that its (weak or strong) stable extensions correspond to the stable extensions of AF. So, a is credulously (respectively skeptically) accepted in AF with respect to the stable semantics if and only if a is credulously (respectively skeptically) accepted in 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

Proposition 8(Extension Existence for Symmetric StrAFs).

Given StrAF=A,R,S a symmetric StrAF and coval an aggregation function, checking whether stXcoval(StrAF) is NP-complete, with X{S,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 AF=A,R. We define a symmetric StrAF such that its (weak or strong) stable extensions exactly coincide with the stable extensions of AF. Formally, StrAF=A,R,S with:

  • A=AA, where A={xxA}, i.e. for any argument xA, we create x a copy of x;

  • R=R1R2R3R4, where

    • R1={(a,b),(b,a)(a,b)R}, i.e. all the attacks from AF are made symmetric;

    • R2={(a,a),(a,a)aA}, i.e. each argument from AF attacks (and is attacked by) its copy;

    • R3={(a,b),(b,a)(a,b)R}, i.e. if a attacks b in AF, then a attacks (and is attacked by) the copy of b;

    • R4={(a,a)aA}, i.e. each copy is a self-attacking argument.

  • if bA such that (a,b)R, then S(a)=M, with M an arbitrary large number (M|A|), otherwise S(a)=1.

Figure 5 illustrates the reduction from an AF to its corresponding symmetric StrAF.

Fig. 5.

An example of our reduction from AF to StrAF.

An example of our reduction from AF to StrAF.

Let us prove that st(AF)=stS(StrAF). We start by the proof that st(AF)stS(StrAF). Let Est(AF) be a stable extension of AF. By definition, E is conflict-free in AF. Moreover, by the definition of StrAF, a,bA, if (a,b)R and (b,a)R, then (a,b)R and (b,a)R: the construction of the StrAF makes the attacks in AF symmetrical, but no new conflicts are created. So E is strongly conflict-free in StrAF.

Now, we need to prove that each argument aAE is defeated by an accrual κE. Let us consider such an argument aAE.

  • If aAE (i.e. a is an argument that belongs to AF, not a copy), then (since E is a stable extension of AF) bE such that (b,a)R. This implies that S(b)=M, so whatever the strength of a, S(b)S(a). This means that {b}a, where {b} is an accrual included in E.

  • Otherwise, aA. This means that a=x, for some xA. Moreover, by definition of StrAF, S(a)=1.

    • If xE, since (x,x)R, there is an accrual {x}E such that {x}x, i.e. {x}a.

    • If xE, yE such that (y,x)R. This implies that (y,x)R, thus {y}x, i.e. {y}a.

We can conclude that EstS(StrAF), so st(AF)stS(StrAF).

Now, we prove that stS(StrAF)st(AF). Let E be a strong stable extension of StrAF. First, we notice that there can be no argument aA in the extension: each aA attacks itself, so if aE, then E is not strongly conflict-free, and thus E cannot be a strong stable extension. So EA.

Since E is strongly conflict-free in StrAF, we can prove that E is conflict-free in AF. Indeed, the construction of StrAF from AF only adds attacks (by making the conflicts symmetrical). So, if there is no attack between two arguments a,bA in StrAF, it means that there is no attack between them in AF either.

We still have to prove that E attacks each argument bAE in AF. Using reductio ad absurdum, we suppose that bAE such that b is not attacked by E in AF, i.e. aE, (a,b)R. This implies (by definition of StrAF) that, aE, (a,b)R. So κE such that κb: the copy b of b is not attacked, and thus not defeated by E is StrAF. So E is not a strong stable extension of StrAF: this is a contradiction.

We can now conclude that Est(AF), so stS(StrAF)st(AF).

We have proven that st(AF)=stS(StrAF), which means that st(AF) if and only if stS(StrAF). 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

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 StrAF=A,R,S with respect to coval.

Proof.

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

Algorithm 2:

Algorithm compute-symmetric-extension(A,R,S,coval)

Algorithm compute-symmetric-extension(⟨A,R,S⟩,coval)

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

Case 1

E is not strongly conflict free. That means a,bE such that (a,b)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 A at step 5, and it will never be added to E at the following iterations of the loop. Since the graph is symmetric, (a,b)R implies (b,a)R, so we observe the same situation if b is added in E before a.

Case 2

There exists an argument bAE that is not defeated by an accrual in E, i.e. κE, κb. There are again several possible situations.

  • (1) b is not attacked by E, i.e. aE, (a,b)R. Then b is never removed from A at step 5, this implies that b will be added to E. This is a contradiction with the assumption that bAE.

  • (2) There are attacks from some arguments a1,,akE towards b, such that coval(κ)≱S(b), with κ={a1,,ak}. If aiκ such that S(ai)S(b), then κ={ai} is an accrual that defeats b, that is a contradiction with the assumption. So we can ensure that aiκ, S(ai)<S(b). In such a situation, b should have been selected and added to E before any argument ai. This is again a contradiction with the assumption that bAE.

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

Proposition 10(Extension Verification).

Let StrAF=A,R,S be a StrAF and coval an aggregation function. For EA, checking whether EstXcoval(StrAF), with X{S,W}, is polynomial.

Proof.

For EA, 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 a,bE, it holds that (a,b)R. This is polynomial and corresponds to checking conflict-freeness in Dung’s framework.

Weak conflict-freeness is verified by first computing the set Γ(a)={bbE such that (b,a)R} for each aE, and then checking that it is not the case that coval(Γ(a))S(a). Since coval is assumed to satisfy the Accrual property (see Definition 7), coval(Γ(a))<S(a) implies that for any accrual κE that attacks a, coval(κ)coval(Γ(a))<S(a), so κ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 aE, the set Γ(a)={bbE such that (b,a)R} is computed. Then for each such a it is verified that coval(Γ(a))S(a). 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

Proposition 11(Extension Existence).

Given StrAF=A,R,S a StrAF and coval an aggregation function, checking whether stXcoval(StrAF) is NP-complete, with X{S,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

Proposition 12(Argument Acceptance).

Let StrAF=A,R,S be a StrAF and coval an aggregation function. Given aA,

  • deciding whether EstX(StrAF) such that aE is NP-complete.

  • deciding whether EstX(StrAF), aE 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 EA be a set of arguments such that aE. Verifying whether E is a strong (or weak) stable extension is polynomial (Proposition 10); the conclusion follows.

For coNP-membership of skeptical acceptance, let EA be a set of arguments such that aE. 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=. The rest of this section presents an algorithm that finds the stable extensions of StrAF=A,R,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 iwivik, where wi and k are positive integers, and vi 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 StrAF=A,R,S and coval=, we associate a pseudo-Boolean constraint satisfaction problem CSW(StrAF)=(X,C), defined as follows:

  • with each argument aiA we associate a Boolean variable xiX;

  • the set of constraints C is as follows:

    • (1) For each aA with Γ(a)={a1,a2,,an}, add the constraint S(a1)×x1+S(a2)×x2++S(an)×xn<S(a)×x+(1x)×Ma, where x is the variable that corresponds to a, and Ma an integer that is explained below.

    • (2) For each aA with Γ(a)={a1,a2,,an}, add the constraint S(a1)×x1+S(a2)×x2++S(an)×xn(1x)×S(a), where x is the variable that corresponds to a.

Intuitively, xi is true means that the corresponding argument ai belongs to an extension. Each solution of the problem corresponds then to one extension of the StrAF.

The value Ma that is associated with an argument aA in constraint (1) is an integer such that Ma>aiΓ(a)S(ai). The purpose that Ma 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.

  • (1.1) if x=0, the constraint becomes aiΓ(a)S(ai)×xi<Ma, which is satisfied regardless of the values assigned to the variables xi, since aiΓ(a)S(ai)×xiaiΓ(a)S(ai) and by construction aiΓ(a)S(ai)<Ma. Therefore, in this case constraint (1) is inactive.

  • (1.2) if x=1, the constraint becomes aiΓ(a)S(ai)×xi<S(a), requiring that coval(Γ(a))<S(a).

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:

  • (2.1) if x=0, the constraint becomes S(a1)×x1+S(a2)×x2++S(an)×xnS(a), i.e. coval(Γ(a))S(a).

  • (2.2) if x=1, the constraint becomes S(a1)×x1+S(a2)×x2++S(an)×xn0, 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(1x)×S(a), that can be rewritten into x1. This means that non-attacked arguments must be accepted.

The next proposition shows a direct correspondence between weak stable extensions of StrAF and the solutions of the problem CSW(StrAF).

Definition 13.

Given a set of arguments EA, the Boolean assignment ωE is defined, xiX, by ωE(xi)=1 if and only if aiE.

Proposition 13

Proposition 13(Computation for Weak Stable Semantics).

A set EA is a weak stable extension of StrAF=A,R,S with respect toif and only if the assignment ωE is a solution for CSW(StrAF).

Example 9.

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

If we set Ma to 5 in all the constraints for simplicity, we obtain the following set of constraints:

3×x3<1×x1+(1x1)×51×x1<2×x2+(1x2)×51×x1+2×x2<3×x3+(1x3)×52×x2<2×x4+(1x4)×53×x3(1x1)×11×x1(1x2)×21×x1+2×x2(1x3)×32×x2+(1x4)×2
The above set of constraints has the solutions S1={x1=1,x2=1,x3=0,x4=0}, and S2={x1=0,x2=1,x3=1,x4=0} that correspond to stWΣ(StrAFweak)={{a1,a2},{a2,a3}}.

Fig. 6.

Two examples of StrAFs.

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 StrAF=A,R,S and coval=, we associate a pseudo-boolean constraint satisfaction problem CSS(StrAF)=(X,C) as follows:

  • with each argument aiA we associate a Boolean variable xiX;

  • the set of constraints C is as follows:

    • (1) For each aA with Γ(a)={a1,a2,,an}, add the constraint S(a1)×x1+S(a2)×x2++S(an)×xn<S(a)×x+(1x)×Ma, where x is the variable that corresponds to a, and Ma an integer that is explained previously.

    • (2) For each aA with Γ(a)={a1,a2,,an}, add the constraint S(a1)×x1+S(a2)×x2++S(an)×xn(1x)×S(a), where x is the variable that corresponds to a.

    • (3) For each pair of arguments ai,ajA such that (ai,aj)R, add the constraint xi+xj1.

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 StrAF and the solutions of the problem CSS(StrAF).

Proposition 14

Proposition 14(Computation for Strong Stable Semantics).

A set EA is strong stable extension of StrAF=A,R,S with respect toif and only if the assignment ωE is a solution of CSS(StrAF).

Example 10.

Consider StrAFstrong=A,R,S described at Fig. 6(b). We observe that if we use the classical defeat-based semantics, neither a1 nor a3 can defeat a2, 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. aac--1-aac200904-g009.jpg

The three columns correspond respectively to constraints (1), (2) and (3). The only solution of this set of constraints is S={x1=x3=x4=1,x2=0}, that corresponds to the unique strong stable extension E={a1,a3,a4}.

We notice that StrAFweak from Example 9 does not have any strong stable extension. Indeed, none of the solutions S1 and S2 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 ϕ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 ϕc=¬a¬b: if both a and b are accepted, then c is rejected (because ϕ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 {a,b} to c is the result of aggregating m and n (e.g. m+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

AcyclicSymmetricGeneral

StrongWeakStrongWeakStrongWeak
VerificationPPPPPP
ExistencePTrivialNP-cNP-cNP-cNP-c
CredulousPPNP-cNP-cNP-cNP-c
SkepticalPPcoNP-ccoNP-ccoNP-ccoNP-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.

Notes

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

References

[1] 

L. Amgoud, J. Ben-Naim, D. Doder and S. Vesic, Ranking arguments with compensation-based semantics, in: Proceedings of the Fifteenth International Conference on Principles of Knowledge Representation and Reasoning, KR’16, 2016, pp. 12–21.

[2] 

L. Amgoud, J. Ben-Naim, D. Doder and S. Vesic, Acceptability semantics for weighted argumentation frameworks, in: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI’17, 2017, pp. 56–62.

[3] 

L. Amgoud and C. Cayrol, A reasoning model based on the production of acceptable arguments, Annals of Mathematics and Artificial Intelligence 34(1–3) (2002), 197–215. doi:10.1023/A:1014490210693.

[4] 

L. Amgoud and H. Prade, Using arguments for making and explaining decisions, Artificial Intelligence 173(3–4) (2009), 413–436. doi:10.1016/j.artint.2008.11.006.

[5] 

L. Amgoud and S. Vesic, Rich preference-based argumentation frameworks, International Journal of Approximate Reasoning 55(2) (2014), 585–606. doi:10.1016/j.ijar.2013.10.010.

[6] 

S. Arora and B. Barak, Computational Complexity – a Modern Approach, Cambridge University Press, 2009. ISBN 978-0-521-42426-4.

[7] 

P. Baroni, M. Caminada and M. Giacomin, Abstract argumentation frameworks and their semantics, in: Handbook of Formal Argumentation, P. Baroni, D. Gabbay, M. Giacomin and L. van der Torre, eds, College Publications, 2018, pp. 159–236.

[8] 

P. Baroni, A. Rago and F. Toni, How many properties do we need for gradual argumentation? in: Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, AAAI’18, 2018, pp. 1736–1743.

[9] 

P. Baroni, M. Romano, F. Toni, M. Aurisicchio and G. Bertanza, Automatic evaluation of design alternatives with quantitative argumentation, Argument & Computation 6(1) (2015), 24–49. doi:10.1080/19462166.2014.1001791.

[10] 

T.J.M. Bench-Capon, Value-based argumentation frameworks, in: Proceedings of the Ninth International Workshop on Non-monotonic Reasoning, NMR’02, 2002, pp. 443–454.

[11] 

T.J.M. Bench-Capon, H. Prakken and G. Sartor, Argumentation in legal reasoning, in: Argumentation in Artificial Intelligence, 2009, pp. 363–382. doi:10.1007/978-0-387-98197-0_18.

[12] 

S. Benferhat, D. Dubois and H. Prade, Argumentative inference in uncertain and inconsistent knowledge bases, in: Proceedings of the Ninth Annual Conference on Uncertainty in Artificial Intelligence, UAI’93, 1993, pp. 411–419.

[13] 

P. Besnard and A. Hunter, Elements of Argumentation, MIT Press, 2008.

[14] 

S. Bistarelli and F. Gadducci, Enhancing constraints manipulation in semiring-based formalisms, in: Proceedings of the Seventeenth European Conference on Artificial Intelligence, ECAI’06, 2006, pp. 63–67.

[15] 

S. Bistarelli, D. Pirolandi and F. Santini, Solving weighted argumentation frameworks with soft constraints, in: Proceedings of the Twenty-Fifth Italian Conference on Computational Logic, CILC’10, 2010.

[16] 

S. Bistarelli, F. Rossi and F. Santini, A novel weighted defence and its relaxation in abstract argumentation, International Journal of Approximate Reasoning 92 (2018), 66–86. doi:10.1016/j.ijar.2017.10.006.

[17] 

S. Bistarelli and F. Santini, Some thoughts on well-foundedness in weighted abstract argumentation, in: Proceedings of the Sixteenth International Conference on Principles of Knowledge Representation and Reasoning, KR’18, 2018, pp. 623–624.

[18] 

S. Bistarelli and F. Santini, Well-foundedness in weighted argumentation frameworks, in: Proceedings of the Sixteenth European Conference on Logics in Artificial Intelligence, JELIA’19, 2019, pp. 69–84.

[19] 

A. Bochman, Collective argumentation and disjunctive logic programming, Journal of Logic and Computation 13(3) (2003), 405–428. doi:10.1093/logcom/13.3.405.

[20] 

E. Bonzon, J. Delobelle, S. Konieczny and N. Maudet, A comparative study of ranking-based semantics for abstract argumentation, in: Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, AAAI’16, 2016, pp. 914–920.

[21] 

G. Brewka, H. Strass, S. Ellmauthaler, J.P. Wallner and S. Woltran, Abstract dialectical frameworks revisited, in: Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI’13, 2013, pp. 803–809.

[22] 

G. Brewka, H. Strass, J.P. Wallner and S. Woltran, Weighted abstract dialectical frameworks, in: Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, AAAI’18, 2018, pp. 1779–1786.

[23] 

M. Caminada and S. Vesic, On extended conflict-freeness in argumentation, in: Proceedings of the Twenty-Fourth Benelux Conference on Artificial Intelligence, BNAIC’12, 2012.

[24] 

C. Cayrol and M. Lagasquie-Schiex, Graduality in argumentation, Journal of Artificial Intelligence Research 23 (2005), 245–297. doi:10.1613/jair.1411.

[25] 

C. Cayrol and M. Lagasquie-Schiex, On the acceptability of arguments in bipolar argumentation frameworks, in: Proceedings of the Eighth European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, ECSQARU’05, 2005, pp. 378–389. doi:10.1007/11518655_33.

[26] 

C. Cayrol and M.-C. Lagasquie-Schiex, Coalitions of arguments: A tool for handling bipolar argumentation frameworks, International Journal of Intelligent Systems 25(1) (2010), 83–109. doi:10.1002/int.20389.

[27] 

O. Cocarascu, A. Rago and F. Toni, Extracting dialogical explanations for review aggregations with argumentative dialogical agents, in: Proceedings of the Eighteenth International Conference on Autonomous Agents and MultiAgent Systems, AAMAS’19, 2019, pp. 1261–1269.

[28] 

S. Coste-Marquis, C. Devred and P. Marquis, Symmetric argumentation frameworks, in: Proceedings of the Eighth European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, ECSQARU’05, 2005, pp. 317–328. doi:10.1007/11518655_28.

[29] 

S. Coste-Marquis, S. Konieczny, P. Marquis and M.A. Ouali, Weighted attacks in argumentation frameworks, in: Proceedings of the Thirteenth International Conference on Principles of Knowledge Representation and Reasoning, KR’12, 2012.

[30] 

S. Coste-Marquis, S. Konieczny, P. Marquis and M.A. Ouali, Weighted attacks in argumentation frameworks, in: Proceedings of the Thirteenth International Conference on Principles of Knowledge Representation and Reasoning, KR’12, 2012.

[31] 

S. Coste-Marquis, S. Konieczny, P. Marquis and M.A. Ouali, Selecting extensions in weighted argumentation frameworks, in: Proceedings of the Fourth International Conference on Computational Models of Argument, COMMA’12, 2012, pp. 342–349.

[32] 

C. da Costa Pereira, A. Tettamanzi and S. Villata, Changing one’s mind: Erase or rewind? in: Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI’11, 2011, pp. 164–171.

[33] 

Y. Dimopoulos, J.-G. Mailly and P. Moraitis, Argumentation-based negotiation with incomplete opponent profiles, in: Proceedings of the Eighteenth International Conference on Autonomous Agents and MultiAgent Systems, AAMAS’19, 2019, pp. 1252–1260.

[34] 

D. Dubois and H. Prade, Possibilistic logic – an overview, in: Computational Logic, 2014, pp. 283–342. doi:10.1016/B978-0-444-51624-4.50007-1.

[35] 

P.M. Dung, On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games, Artificial Intelligence 77 (1995), 321–357. doi:10.1016/0004-3702(94)00041-X.

[36] 

P.M. Dung, R.A. Kowalski and F. Toni, Assumption-based argumentation, in: Argumentation in Artificial Intelligence, 2009, pp. 199–218. doi:10.1007/978-0-387-98197-0_10.

[37] 

P.E. Dunne, A. Hunter, P. McBurney, S. Parsons and M. Wooldridge, Weighted argument systems: Basic definitions, algorithms, and complexity results, Artificial Intelligence 175(2) (2011), 457–486. doi:10.1016/j.artint.2010.09.005.

[38] 

W. Dvorák, Computational aspects of abstract argumentation, PhD thesis, Technische Universität Wien, 2012.

[39] 

W. Dvorák and P.E. Dunne, Computational problems in formal argumentation and their complexity, in: Handbook of Formal Argumentation, P. Baroni, D. Gabbay, M. Giacomin and L. van der Torre, eds, College Publications, 2018, pp. 631–688.

[40] 

W. Dvorák, A. Greßler and S. Woltran, Evaluating SETAFs via answer-set programming, in: Proceedings of the Second International Workshop on Systems and Algorithms for Formal Argumentation, SAFA’18, 2018, pp. 10–21.

[41] 

J. Elffers and J. Nordström, Divide and conquer: Towards faster pseudo-Boolean solving, in: Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI’18, 2018, pp. 1291–1299.

[42] 

G. Flouris and A. Bikakis, A comprehensive study of argumentation frameworks with sets of attacking arguments, International Journal of Approximate Reasoning 109 (2019), 55–86. doi:10.1016/j.ijar.2019.03.006.

[43] 

D.M. Gabbay, Semantics for higher level attacks in extended argumentation frames Part 1: Overview, Studia Logica 93(2–3) (2009), 357–381. doi:10.1007/s11225-009-9211-4.

[44] 

T. Gordon, Defining argument weighing functions, Journal of Applied Logics – IfCoLog Journal of Logics and their Application 5 (2018), 747–773.

[45] 

S. Kaci and C. Labreuche, Representing synergy among arguments with Choquet integral, in: Proceedings of the Twelfth European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, ECSQARU’13, 2013, pp. 302–314. doi:10.1007/978-3-642-39091-3_26.

[46] 

A.C. Kakas and P. Moraitis, Argumentation based decision making for autonomous agents, in: Proceedings of the Second International Joint Conference on Autonomous Agents & Multiagent Systems, AAMAS’03, 2003, pp. 883–890. doi:10.1145/860575.860717.

[47] 

D. Le Berre and A. Parrain, The Sat4j library, release 2.2, Journal on Satisfiability, Boolean Modeling and Computation 7(2–3) (2010), 59–64.

[48] 

J. Leite and J. Martins, Social abstract argumentation, in: Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI’11, 2011, pp. 2287–2292.

[49] 

M.J.G. Lucero, C.I. Chesñevar and G.R. Simari, On the accrual of arguments in defeasible logic programming, in: Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence, IJCAI’09, 2009, pp. 804–809.

[50] 

M.J.G. Lucero, C.I. Chesñevar and G.R. Simari, Modelling argument accrual with possibilistic uncertainty in a logic programming setting, Information Sciences 228 (2013), 1–25. doi:10.1016/j.ins.2012.11.025.

[51] 

D.C. Martínez, A.J. García and G.R. Simari, An abstract argumentation framework with varied-strength attacks, in: Proceedings of the Eleventh International Conference on Principles of Knowledge Representation and Reasoning, KR’08, 2008, pp. 135–144.

[52] 

R. Martins, V. Manquinho and I. Lynce, Open-WBO: A modular MaxSAT solver, in: Proceedings of the Seventeenth International Conference on Theory and Applications of Satisfiability Testing, SAT’14, 2014, pp. 438–445.

[53] 

P. Matt and F. Toni, A game-theoretic measure of argument strength for abstract argumentation, in: Proceedings of the Eleventh European Conference on Logics in Artificial Intelligence, JELIA’08, 2008, pp. 285–297.

[54] 

P. McBurney, S. Parsons and I. Rahwan (eds), Proceedings of the Eighth International Workshop on Argumentation in Multi-Agent Systems, ArgMAS’11, Lecture Notes in Computer Science, Vol. 7543, Springer, 2012.

[55] 

T. Mossakowski and F. Neuhaus, Modular semantics and characteristics for bipolar weighted argumentation graphs, 2018, CoRR abs/1807.06685.

[56] 

G.S. Nair, How do reasons accrue? in: Weighing Reasons, E. Lord and B. Maguire, eds, Oxford University Press, 2016.

[57] 

S.H. Nielsen and S. Parsons, A generalization of Dung’s abstract framework for argumentation: Arguing with sets of attacking arguments, in: Proceedings of the Third International Workshop on Argumentation in Multi-Agent Systems, ArgMAS’06, 2006, pp. 54–73.

[58] 

G. Pinkas, Reasoning, nonmonotonicity and learning in connectionist networks that capture propositional knowledge, Artificial Intelligence 77(2) (1995), 203–247. doi:10.1016/0004-3702(94)00032-V.

[59] 

J.L. Pollock, A theory of defeasible reasoning, International Journal of Intelligent Systems 6(1) (1991), 33–54. doi:10.1002/int.4550060103.

[60] 

J.L. Pollock, Self-defeating arguments, Minds and Machines 1 (1991), 367–392. doi:10.1007/BF00352916.

[61] 

N. Potyka, Extending modular semantics for bipolar weighted argumentation, in: Proceedings of the Eighteenth International Conference on Autonomous Agents and MultiAgent Systems, AAMAS’19, 2019, pp. 1722–1730.

[62] 

H. Prakken, A study of accrual of arguments, with applications to evidential reasoning, in: Proceedings of the Tenth International Conference on Artificial Intelligence and Law, ICAL’05, 2005, pp. 85–94.

[63] 

H. Prakken, Modelling accrual of arguments in ASPIC+, in, in: Seventeenth International Conference on Artificial Intelligence and Law (ICAIL’19), 2019, pp. 285–297.

[64] 

A. Rago and F. Toni, Quantitative argumentation debates with votes for opinion polling, in: Proceedings of the Twentieth International Conference on Principles and Practice of Multi-Agent Systems, PRIMA’17, 2017, pp. 369–385.

[65] 

Y. Salhi, On an argument-centric persuasion framework, in: Proceedings of the Eighteenth International Conference on Autonomous Agents and MultiAgent Systems, AAMAS’19, 2019, pp. 1279–1287.

[66] 

B. Verheij, Accrual of arguments in defeasible argumentation, in: Proceedings of the Second Dutch/German Workshop on Nonmonotonic Reasoning, 1995, pp. 217–224.

[67] 

S. Villata, G. Boella and L. van der Torre, Argumentation patterns, in: Proceedings of the Eighth International Workshop on Argumentation in Multi-Agent Systems (ArgMAS’11), 2011, pp. 133–150.