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.
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
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
S is conflict-free if and only if ∄
S defends
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
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.
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;
The extensions of
Fig. 1.
Both versions of John’s garden situation.
Table 1
Extensions of
| σ | |
| cf, ad | ∅, |
| pr, st | |
| σ | |
| cf, ad | ∅, |
| pr, st |
Notice that
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
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
Fig. 2.
Both versions of John’s garden situation.
Now, we adapt Dung-style semantics to StrAFs. To do so, we borrow the notion of defeat relation from Preference-based AFs and Value-based AFs [3,10].
Definition 4
Definition 4(Defeat Relation and Extension Semantics).
Given
Extension-based semantics of
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
In the case of
Fig. 3.
Defeat graphs for John’s garden situation.
These defeat-based semantics are relevant when the strength associated with an argument is individual and independent from other arguments, likewise the behavior of Preference-based AFs. In our case, the semantics may produce an extension which is not the most desirable outcome, like it is the case with
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
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
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
Definition 6.
Let
We then define the collective strength associated with an accrual κ, denoted by
Definition 7.
Let
(non-decreasingness) | if |
(minimality) | |
(identity) | |
(accrual) |
These properties are quite natural for defining the strength of an accrual. Non-decreasingness means that, if
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
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
We can introduce the notion of an accrual that defeats another accrual as follows:
Definition 9.
Let
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
Let us illustrate the notion of collective attacks with our running example.
Example 5.
We continue Example 2. The natural aggregation operator here is
The following example illustrates our approach in a non-symmetrical abstract argumentation context.
Example 6.
Fig. 4.
The StrAF that describes the situation of Joe and Jack.
Let us consider the example provided in [57], composed of the following abstract arguments:
On another hand, authors in [57] discuss that arguments
In our framework, let
either strengths associated with arguments are such that either
either strengths associated with arguments are such that
or finally strengths associated with arguments are such that
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
S is strongly conflict-free if and only if
S is weakly conflict-free if and only if there are no accruals
S defends an element
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
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
For any semantics
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
We also remark a relation between weak semantics of StrAFs and semantics of AFs with collective attacks [57]. Indeed, if
We show that the usual relationship between semantics also holds for StrAFs.
Proposition 1
Proposition 1(Semantics Inclusion).
Let
Proof.
The fact that every strong (respectively weak) preferred extension is a strong (respectively weak) admissible extension is straightforward from the definition.
Let
First we prove that E is a strong (respectively weak) admissible extension. Let
Case 1 | |
Case 2 |
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
Example 7.
Now we give the strong stable extensions of
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
Lemma 1.
Let
Lemma 1 is obvious from the definition of strong conflict-freeness.
Lemma 2.
Let
Proof.
Let us suppose that
Now, let us consider an accrual
Now we suppose that
Proposition 2
Proposition 2(Dung Compatibility).
Let
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
Corollary 1.
Let
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
Example 8.
Let
In fact, we prove the existence of a weak stable extension for every acyclic StrAF, by providing Algorithm 1. Given
Algorithm 1:
Algorithm compute-acyclic-extension(
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
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
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
Case 1 | E is not weakly conflict free. That means |
Case 2 | There exists an argument |
Now let us prove that E is the unique weak stable extension. Let us suppose that
First, we observe that the non-empty set U of arguments that are unattacked in
Since
This process then repeats iteratively until it terminates since
Algorithm 1 is a polynomial time procedure when the set
Proposition 4
Proposition 4(Extension Computation for Acyclic StrAFs).
Let
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
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
Proof.
We know that if
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
First, we prove that strong and weak semantics coincide for symmetric StrAFs.
Proposition 6
Proposition 6(Weak/Strong Coincidence).
Let
Proof.
We already know that
Proposition 6 implies that
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
deciding whether
deciding whether
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
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
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
∗
∗
∗
∗
if
Fig. 5.
An example of our reduction from
Let us prove that
Now, we need to prove that each argument
If
Otherwise,
∗ If
∗ If
Now, we prove that
Since E is strongly conflict-free in
We still have to prove that E attacks each argument
We can now conclude that
We have proven that
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
Proof.
Let us first prove that the algorithm always terminates. For any
Algorithm 2:
Algorithm compute-symmetric-extension(
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
Case 1 | E is not strongly conflict free. That means |
Case 2 | There exists an argument
|
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
Proof.
For
For the case of strong conflict-freeness, we have to check that for any two
Weak conflict-freeness is verified by first computing the set
Finally, for both weak and strong semantics the following check is needed. For every
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
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
deciding whether
deciding whether
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
For coNP-membership of skeptical acceptance, let
Computing the stable extensions of a StrAF is a challenging problem even when the aggregation function is
A pseudo-Boolean constraint is an inequality of the form
Weak semantics. We start with weak stable semantics. Given
with each argument
the set of constraints C is as follows:
(1) For each
(2) For each
Intuitively,
The value
(1.1) if
(1.2) if
Constraint (2) can be understood as follows:
(2.1) if
(2.2) if
Note that, when a has no attacker, constraint (2) becomes
The next proposition shows a direct correspondence between weak stable extensions of
Definition 13.
Given a set of arguments
Proposition 13
Proposition 13(Computation for Weak Stable Semantics).
A set
Example 9.
Consider
If we set
Fig. 6.
Two examples of StrAFs.
Strong semantics. For strong stable semantics, we use the encoding for weak stable semantics as a starting point. We only need to add a constraint for enforcing the strong conflict-freeness. Given
with each argument
the set of constraints C is as follows:
(1) For each
(2) For each
(3) For each pair of arguments
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
Proposition 14
Proposition 14(Computation for Strong Stable Semantics).
A set
Example 10.
Consider 
The three columns correspond respectively to constraints (1), (2) and (3). The only solution of this set of constraints is
We notice that
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
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
7.Conclusion and future work
In this paper, we have proposed an intuitive framework for representing strength of arguments called Strength-based Argumentation Framework. We use the numerical strength of arguments to define extension-based semantics based on a defeat relation, that is the combination of the initial attacks between arguments and the comparison of their respective strengths. We have shown how quantitative strengths can be aggregated when several arguments attack a same target, making an accrual of arguments. The definition of collective defeat has allowed us to define new semantics that lead to interesting extensions that cannot be obtained when the usual Dung’s AFs or individual defeat are used.
We have established the complexity of several reasoning problems for special cases (acyclic and symmetric graphs) as well as general StrAFs. Surprisingly, we notice that, while our framework can model situations that are not captured by Dung’s AFs without a blow up of the framework size, the complexity of reasoning does not increase. Table 2 summarizes our results for (strong and weak) stable semantics. P stands for polynomial, while X-c means X-complete where X is either NP or coNP. We say that a problem is trivial when the answer is straightforwardly “yes”. We recall that all these results hold under the assumption that coval can be computed in polynomial time.
Table 2
Summary of complexity results for (strong and weak) stable semantics
| Acyclic | Symmetric | General | ||||
| Strong | Weak | Strong | Weak | Strong | Weak | |
| Verification | P | P | P | P | P | P |
| Existence | P | Trivial | NP-c | NP-c | NP-c | NP-c |
| Credulous | P | P | NP-c | NP-c | NP-c | NP-c |
| Skeptical | P | P | coNP-c | coNP-c | coNP-c | coNP-c |
Our complexity results only concern the (strong and weak) stable semantics. For the case of weak semantics, they remind the complexity results for AFs with collective attacks [40]. We plan to deepen this investigation and consider other semantics as well, especially for the strong versions since the weak versions can be deduced from [40]. Moreover, regarding symmetric StrAFs, we have proven that extension existence is a trivial problem if we only consider irreflexive attack relations, i.e. no self-attacking arguments belong to the StrAF. It is known that reasoning with irreflexive symmetric AFs is polynomial [28]. We will investigate this question for irreflexive StrAFs, and determine whether self-attacks are the source of NP (or coNP) hardness for symmetric StrAFs, as they are in the case of symmetric AFs.
Weak extensions make sense for applications where conflicts are expected between pieces of information, but these pieces of information appear to be not strong enough to actually exclude each other. In other words, evaluation of these conflicts does not lead to reject some of the involved pieces of information which thus can be accepted together. However, in the case of logic-based argumentation, the loss of (strong) conflict-freeness may lead to problems with the inference defined from the argumentation framework if two arguments belong to the same extension while one of them undercuts the other one. We plan to refine the notion of weak conflict-freeness according to this idea, similarly to the refinement of Preference-based AFs [5].
In Section 5.1, we have stated that acyclic StrAFs have exactly one (strong or weak) stable extension. This is reminiscent to known results for classical AFs [35], or argumentation frameworks with weighted attacks [17,18]. These papers prove that (in these frameworks) the four classical semantics introduced by Dung (namely grounded, complete, preferred and stable) coincide for well-founded frameworks. The formal definition and study of the relations between these semantics in our framework is a promising track for future research.
We plan to study the logical properties of our accrual-based semantics with respect to the properties of coval operators. Different properties may be suited to different applications scenarios, thus indicating which coval operators to choose depending on the application domain or the nature of arguments.
As mentioned in Section 4.1, we have focused in this work on situations where arguments strengths are commensurable from an argument to another. Again, this assumption allows to directly compare strengths associated with different arguments, and it thus makes sense to then aggregate them to compute the strength associated with an accrual. However, this assumption may appear to be too strong for many interesting real-world applications, for example when weights represent subjective opinions or judgments, or when they are provided by different sources which do not share the meaning they associate with weights. We will investigate strategies adapted to applications where such commensurability assumption over strengths associated with arguments is dropped.
Lastly, frameworks where arguments are built from logical formulas or rules have received a lot of attention [13,36,46]. On the other hands, some logical frameworks allow representation of weighted pieces of information [34,58]. A natural question is then the generation of structured arguments from such weighted logics, and then whether and how such structured arguments can be combined in accruals.
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. |
