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.
Argumentation has been a main research topic in artificial intelligence for the last twenty years, with applications in various domains such as decision making , automated negotiation , reasoning with inconsistent knowledge , legal reasoning , and multi-agent systems . A lot of works have been proposed, mainly based on the influential argumentation framework (AF) of Dung . 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 . 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 , or by a relation of preference between the values attached to arguments . 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,  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 . 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 , 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 . 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.
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.
Most of the studies addressed to the literature of argumentation for the last twenty years have been inspired by the work of . This section presents the basics of abstract argumentation frameworks.
An argumentation framework (AF), as introduced by Dung in , is a pair , where is a set of arguments, and is an attack relation. The relation a attacks b, or b is attacked by a, is denoted by . We focus on finite argumentation frameworks, i.e. AFs such that is a finite set.
In , different acceptability semantics have been introduced. These are based on two basic concepts, defence and conflict-freeness, defined as follows:
Let be an argumentation system. Let .
S is conflict-free if and only if ∄ s.t () .
S defends if and only if ∀ , if , then such that .
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 be an AF and .
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 .
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.
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;
The extensions of and for the different aforementioned semantics are given at Table 1. All these sets of extensions can represent reasonable choices of working activities for John.
|cf, ad||∅, , , , , , , , , , ,|
|, , , , , , ,|
|, , , , , , ,|
|pr, st||, , , , , , ,|
|cf, ad||∅, , , , , , , , , , ,, , , ,|
|, , , ,, , , ,|
|, , , , , ,|
|pr, st||, , ,|
Notice that and (and similarly for ). This comes from the fact that these AFs are symmetric . This is not the case in general, but it is well-known that , . 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  mentions “fuzziness, probability or a preference in general”, or a notion of trust about the arguments,  associates the weights to an intrinsic strength, that represents votes given by users , a certainty degree of arguments premises  or trustworthiness of the source of information . A similar intuitive explanation is given in [55,61] for weights associated with arguments, and in  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 . 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)  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  has been used to give a novel method for opinion polling, with arguments base scores corresponding to users votes.
Quantitative Bipolar Argumentation Frameworks (QBAFs)  are a general abstract argumentation framework where arguments are related by both attacks and supports , and they are attached with a base score. Again, the semantics of these frameworks yields a degree of acceptance for each argument. In , 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 , 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 where and are respectively arguments and attacks, and 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:
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 and , we can define StrAFs and described at Fig. 2, where , and . 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.
Definition 4(Defeat Relation and Extension Semantics).
Given a StrAF, the defeat relation Def is defined by .
Extension-based semantics of can be defined by considering the extensions of the classical AF , i.e. for .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  where the concept of defence is refined by taking advantage of weights associated with attack relations.
We continue Example 2. For both and , we describe below the graphs corresponding to the defeat relation.
In the case of (Fig. 3(a)), we observe that using the defeat relation leads to an intuitive result: for any semantics as introduced in Definition 2, the single extension is , 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 gives ; this option is worth 200 Euros and is not optimal (indeed is an extension of , and is worth 220 Euros).
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 . 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:
Let be a StrAF. A set of arguments is called accrual if and only if such that ∀ , . 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:
In describing John’s situation (see Example 2), there is (for instance) an accrual 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:
Let be a StrAF, and , two accruals. Then, κ attacks if and only if such that κ attacks a.
We then define the collective strength associated with an accrual κ, denoted by , as the combination of values associated with arguments. Formally:
Let be a StrAF and be an accrual. Then the collective strength associated with κ is:
if , then ;
if and only if ;
These properties are quite natural for defining the strength of an accrual. Non-decreasingness means that, if and , then the accrual is stronger than the accrual when a is stronger than b. Minimality states that the accumulation of arguments “without” strength (i.e. ) 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 ; 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 . 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.
Let be a StrAF, , and coval an aggregation operator. Then, an accrual κ defeats a with respect to coval, denoted by , if and only if
is an accrual that attacks a;
We can introduce the notion of an accrual that defeats another accrual as follows:
Let be a StrAF, coval an aggregation operator and , two accruals. Then κ defeats , denoted by , if and only if there exists such that .
Roughly speaking, an accrual defeats another accrual if the first accrual induces a defeat against at least one argument of the second accrual.
In , the strength of an attack from a set S to a set of arguments is defined as the aggregation of strengths associated with all the attacks from any argument in S to any argument in . While this may look similar to defeats between accruals, these are actually different concepts. Indeed, since  do not associate strength with arguments, but with attacks, there is no comparison between strength associated respectively with S and . 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.
We continue Example 2. The natural aggregation operator here is , 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 , the accruals and defeat each other. Indeed, , while .
The following example illustrates our approach in a non-symmetrical abstract argumentation context.
Let us consider the example provided in , composed of the following abstract arguments:
: “Joe does not like Jack”;
: “There is a nail in Jack’s antique coffee table”;
: “Joe hammered a nail into Jack’s antique coffee table”;
: “Joe plays golf, so Joe has full use of his arms”;
: “Joe has no arms, so Joe cannot use a hammer, so Joe did not hammer a nail into Jack’s antique coffee table”.
On another hand, authors in  discuss that arguments and attack the argument 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, and may constitute a stronger argument that defeats . These examples of attacks are illustrated by Fig. 4.
In our framework, let be the strength associated with the argument , for . Let us assume that (since and defeat each other), and (since defeat ). Several cases are then possible:
either strengths associated with arguments are such that either or : in this case, either the argument or the argument is considered solid enough to individually defeat the argument ;
either strengths associated with arguments are such that , and : in this case arguments and are too weak to defeat individually argument but form an accrual to collectively defeat it;
or finally strengths associated with arguments are such that , and : in this case arguments and cannot defeat neither individually nor collectively.
4.2.Extension-based semantics for StrAFS
In , 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.
Let be a StrAF, coval an aggregation operator, and .
S is strongly conflict-free if and only if such that .
S is weakly conflict-free if and only if there are no accruals and such that .
S defends an element if and only if for all accruals , if , then there exists an accrual such that .
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 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 , there is an accrual such that .
For any semantics , the set of strong (respectively weak) σ extension of with respect to coval is denoted by (respectively ). 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 for any semantics σ.
We also remark a relation between weak semantics of StrAFs and semantics of AFs with collective attacks . Indeed, if 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 ). 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 be a StrAF and coval an aggregation operator. For , .
The fact that every strong (respectively weak) preferred extension is a strong (respectively weak) admissible extension is straightforward from the definition.
Let be a strong (respectively weak) stable extension of with respect to coval, i.e. , there is an accrual such that .
First we prove that E is a strong (respectively weak) admissible extension. Let be an accrual such that , with . There are two cases.
implies that E is neither strongly nor weakly conflict-free, this is a contradiction.
implies that , and since E is a strong (respectively weak) stable extension, holds. Thus , 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 a strong (respectively weak) admissible extension such that . So . We have previously established that is such that , so is not weakly conflict-free, and therefore not strongly conflict-free. This is a contradiction with the fact that 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. □
Now we give the strong stable extensions of and , with . It is easy to see that 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 . We observe that the optimal solution 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.
Given an argumentation framework , the StrAF associated with AF is with , and .
Let be a Dung’s AF, and its associated StrAF. The set is conflict-free in if and only if it is strongly conflict-free in .
Lemma 1 is obvious from the definition of strong conflict-freeness.
Let be a Dung’s AF, and its associated StrAF. The set defends the argument in if and only if defends the argument in .
Let us suppose that defends the argument in . This means that for each such that , such that .
Now, let us consider an accrual such that . As established previously, , such that , i.e. such that attacks b. Since , and thus . So S defends the argument a in .
Now we suppose that defends the argument in , i.e. for all accruals that defeat a, such that . Since all arguments strengths are equal to 1, every argument attacking a corresponds to an accrual defeating a. So such that , and thus such that . So we conclude that S defends the argument a in . □
Proposition 2(Dung Compatibility).
Let be a Dung’s AF, and , with , its associated StrAF. For , .
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 , the notions of strong and weak conflict-freeness coincide, we easily obtain the following corollary.
Let be a Dung’s AF, and its associated StrAF. For , .
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. .
5.1.Complexity of acyclic frameworks
A is acyclic if the relation 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.
Let be a StrAF with , , , . For , we have , whereas .
In fact, we prove the existence of a weak stable extension for every acyclic StrAF, by providing Algorithm 1. Given and an argument , the set of attackers of a, denoted by , is defined as . When is clear from the context we write simply .
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 with respect to coval.
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 (step 3). This implies that each iteration of the loop strictly decreases the size of . After at most iterations, 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 with respect to coval. According to Definition 11, we can have two cases.
E is not weakly conflict free. That means an accrual and such that . This is impossible: since b is defeated, it implies that , thus b is not added to the sets and E (steps 3 and 4). Then, steps 5 and 6 exclude from the argument b, so it will never be added to at the following iterations of the while loop.
There exists an argument such that , . However, by construction, such an argument a is never added to (step 5), so it is not removed from at step 6. At some point, all its attackers must have been removed, so ; 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 .
Now let us prove that E is the unique weak stable extension. Let us suppose that such that . We show iteratively that such an extension 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 is such that and . 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 . At this step, we observe that the set of arguments D that are defeated by any accrual cannot belong to , since these arguments are defeated by some accrual in . These arguments are exactly the ones that are put aside from E by step 5 and 6 of Algorithm 1.
Since 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 since they are defended by 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 is finite and is acyclic. One can observe that, at each step of this process, arguments added to E by Algorithm 1 must be in , and conversely arguments set aside by Algorithm 1 cannot belong to . We thus finally obtain that which contradicts our assumption, and so E is the unique weak stable extension. □
Algorithm 1 is a polynomial time procedure when the set can be computed in polynomial time.
Proposition 4(Extension Computation for Acyclic StrAFs).
Let be an acyclic StrAF and coval an aggregation operator. Computing a weak stable extension of is polynomial.
As it is explained in the proof of Proposition 3, we know that the number of iterations of the while loop is at most . Determining the set 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 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 be an acyclic StrAF and coval an aggregation operator. Deciding whether has a strong stable extension is polynomial.
We know that if admits a strong stable extension, then it is also a weak stable extension. Since 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 . 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 if and only if . 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 be a symmetric StrAF and coval an aggregation operator. .
We already know that (straightforward from the definition of strong and weak conflict-freeness). Now, let us prove the opposite inclusion, using reductio ad absurdum. We suppose that such that . This means that such that . Since is symmetric, we know that also holds. Now, if then , otherwise and then . Whatever the situation, E is not weakly conflict-free, which is a contradiction. So we deduce that , and we conclude . □
Proposition 6 implies that , and , for any symmetric 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 be a symmetric StrAF and coval an aggregation function. Given and ,
deciding whether such that is NP-complete.
deciding whether , is coNP-complete.
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 and , we can define a symmetric StrAF such that its (weak or strong) stable extensions correspond to the stable extensions of . So, a is credulously (respectively skeptically) accepted in with respect to the stable semantics if and only if a is credulously (respectively skeptically) accepted in 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 a symmetric StrAF and coval an aggregation function, checking whether is NP-complete, with .
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 . Let us consider any . We define a symmetric StrAF such that its (weak or strong) stable extensions exactly coincide with the stable extensions of . Formally, with:
, where , i.e. for any argument , we create a copy of x;
∗ , i.e. all the attacks from are made symmetric;
∗ , i.e. each argument from attacks (and is attacked by) its copy;
∗ , i.e. if a attacks b in , then a attacks (and is attacked by) the copy of b;
∗ , i.e. each copy is a self-attacking argument.
if such that , then , with M an arbitrary large number (), otherwise .
Let us prove that . We start by the proof that . Let be a stable extension of . By definition, E is conflict-free in . Moreover, by the definition of , , if and , then and : the construction of the makes the attacks in symmetrical, but no new conflicts are created. So E is strongly conflict-free in .
Now, we need to prove that each argument is defeated by an accrual . Let us consider such an argument .
If (i.e. a is an argument that belongs to , not a copy), then (since E is a stable extension of ) such that . This implies that , so whatever the strength of a, . This means that , where is an accrual included in E.
Otherwise, . This means that , for some . Moreover, by definition of , .
∗ If , since , there is an accrual such that , i.e. .
∗ If , such that . This implies that , thus , i.e. .
Now, we prove that . Let E be a strong stable extension of . First, we notice that there can be no argument in the extension: each attacks itself, so if , then E is not strongly conflict-free, and thus E cannot be a strong stable extension. So .
Since E is strongly conflict-free in , we can prove that E is conflict-free in . Indeed, the construction of from only adds attacks (by making the conflicts symmetrical). So, if there is no attack between two arguments in , it means that there is no attack between them in either.
We still have to prove that E attacks each argument in . Using reductio ad absurdum, we suppose that such that b is not attacked by E in , i.e. , . This implies (by definition of ) that, , . So such that : the copy of b is not attacked, and thus not defeated by E is . So E is not a strong stable extension of : this is a contradiction.
We can now conclude that , so .
We have proven that , which means that if and only if . And it is known that verifying whether an argumentation framework has at least one stable extension is a NP-hard problem . 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 with respect to coval.
Let us first prove that the algorithm always terminates. For any , since , , there is at least one argument such that is maximal. Exactly one of these arguments is selected at step 3, added to E, and removed from at step 5. This means that every iteration of the while loop strictly decreases the size of , thus the algorithm terminates in at most iterations.
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 . According to Definition 11, we can have two cases.
E is not strongly conflict free. That means such that . This is impossible: without loss of generality, let us suppose that a has been added to E before b. Then, b is removed from at step 5, and it will never be added to E at the following iterations of the loop. Since the graph is symmetric, implies , so we observe the same situation if b is added in E before a.
There exists an argument that is not defeated by an accrual in E, i.e. , . There are again several possible situations.
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 be a StrAF and coval an aggregation function. For , checking whether , with , is polynomial.
For , 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 , it holds that . This is polynomial and corresponds to checking conflict-freeness in Dung’s framework.
Weak conflict-freeness is verified by first computing the set for each , and then checking that it is not the case that . Since coval is assumed to satisfy the Accrual property (see Definition 7), implies that for any accrual that attacks a, , so . 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 , the set is computed. Then for each such a it is verified that . 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 a StrAF and coval an aggregation function, checking whether is NP-complete, with .
It is known that verifying whether a Dung’s AF has at least one stable extension is NP-complete . 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 be a StrAF and coval an aggregation function. Given ,
deciding whether such that is NP-complete.
deciding whether , is coNP-complete.
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 be a set of arguments such that . Verifying whether E is a strong (or weak) stable extension is polynomial (Proposition 10); the conclusion follows.
For coNP-membership of skeptical acceptance, let be a set of arguments such that . 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 . The rest of this section presents an algorithm that finds the stable extensions of , 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 , where and k are positive integers, and 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 , OpenWBO , RoundingSat ), many of which draw on the power of efficient SAT solving techniques.
Weak semantics. We start with weak stable semantics. Given and , we associate a pseudo-Boolean constraint satisfaction problem , defined as follows:
with each argument we associate a Boolean variable ;
the set of constraints C is as follows:
(1) For each with , add the constraint , where x is the variable that corresponds to a, and an integer that is explained below.
(2) For each with , add the constraint , where x is the variable that corresponds to a.
Intuitively, is true means that the corresponding argument belongs to an extension. Each solution of the problem corresponds then to one extension of the StrAF.
The value that is associated with an argument in constraint (1) is an integer such that . The purpose that 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 , the constraint becomes , which is satisfied regardless of the values assigned to the variables , since and by construction . Therefore, in this case constraint (1) is inactive.
(1.2) if , the constraint becomes , requiring that .
Constraint (2) can be understood as follows:
(2.1) if , the constraint becomes , i.e. .
(2.2) if , the constraint becomes , that is trivially satisfied; the constraint is inactive in this case.
Note that, when a has no attacker, constraint (2) becomes , that can be rewritten into . This means that non-attacked arguments must be accepted.
The next proposition shows a direct correspondence between weak stable extensions of and the solutions of the problem .
Given a set of arguments , the Boolean assignment is defined, , by if and only if .
Proposition 13(Computation for Weak Stable Semantics).
A set is a weak stable extension of with respect to ∑ if and only if the assignment is a solution for .
Consider described at Fig. 6(a). The numerical values close to the nodes represent the strength of arguments i.e. the function . We observe that this StrAF does not admit a strong stable extension, but weak stable extensions can be computed as follows.
If we set to 5 in all the constraints for simplicity, we obtain the following set of constraints:
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 and , we associate a pseudo-boolean constraint satisfaction problem as follows:
with each argument we associate a Boolean variable ;
the set of constraints C is as follows:
(1) For each with , add the constraint , where x is the variable that corresponds to a, and an integer that is explained previously.
(2) For each with , add the constraint , where x is the variable that corresponds to a.
(3) For each pair of arguments such that , add the constraint .
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 and the solutions of the problem .
Proposition 14(Computation for Strong Stable Semantics).
A set is strong stable extension of with respect to ∑ if and only if the assignment is a solution of .
Consider described at Fig. 6(b). We observe that if we use the classical defeat-based semantics, neither nor can defeat , 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 , that corresponds to the unique strong stable extension .
We notice that from Example 9 does not have any strong stable extension. Indeed, none of the solutions and that we exhibited previously satisfies the strong conflict-freeness constraint.
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,  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 , n-ary conflicts are defined between sets of arguments that cannot be jointly accepted, while no explicit conflicts exist between these arguments. Besides,  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 . This framework proposes an extension of the value-based argumentation framework  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)  associate to each abstract node x (called statement) an acceptance formula 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 : if both a and b are accepted, then c is rejected (because 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  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 ).
The idea of “collective support” between arguments is also explored in , 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,  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,  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 to c is the result of aggregating m and n (e.g. ). 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.
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 . 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 . 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 . 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 .
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 , 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.
1 Of course, the same mechanism can be applied to other semantics that are not considered in this paper.
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.
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.
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.
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.
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.
S. Arora and B. Barak, Computational Complexity – a Modern Approach, Cambridge University Press, 2009. ISBN 978-0-521-42426-4.
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.
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.
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.
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.
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.
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.
P. Besnard and A. Hunter, Elements of Argumentation, MIT Press, 2008.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
C. Cayrol and M. Lagasquie-Schiex, Graduality in argumentation, Journal of Artificial Intelligence Research 23 (2005), 245–297. doi:10.1613/jair.1411.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
W. Dvorák, Computational aspects of abstract argumentation, PhD thesis, Technische Universität Wien, 2012.
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.
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.
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.
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.
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.
T. Gordon, Defining argument weighing functions, Journal of Applied Logics – IfCoLog Journal of Logics and their Application 5 (2018), 747–773.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
T. Mossakowski and F. Neuhaus, Modular semantics and characteristics for bipolar weighted argumentation graphs, 2018, CoRR abs/1807.06685.
G.S. Nair, How do reasons accrue? in: Weighing Reasons, E. Lord and B. Maguire, eds, Oxford University Press, 2016.
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.
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.
J.L. Pollock, A theory of defeasible reasoning, International Journal of Intelligent Systems 6(1) (1991), 33–54. doi:10.1002/int.4550060103.
J.L. Pollock, Self-defeating arguments, Minds and Machines 1 (1991), 367–392. doi:10.1007/BF00352916.
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.
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.
H. Prakken, Modelling accrual of arguments in ASPIC+, in, in: Seventeenth International Conference on Artificial Intelligence and Law (ICAIL’19), 2019, pp. 285–297.
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.
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.
B. Verheij, Accrual of arguments in defeasible argumentation, in: Proceedings of the Second Dutch/German Workshop on Nonmonotonic Reasoning, 1995, pp. 217–224.
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.