Modelling Well-Structured Argumentation Lines

1 Introduction

Different formal systems of defeasible argumentation have been defined as forms of representing interesting characteristics of practical or common sense reasoning. The central idea in these systems is that a proposition will be accepted if there exists an argument that supports it, and this argument is regarded as acceptable with respect to an analysis performed considering all the available counterarguments. Therefore, in the set of arguments of the system, some of them will be acceptable or justified or warranted arguments, while others will be not. In this manner, defeasible argumentation allows reasoning with incomplete and uncertain information and is suitable to handle inconsistency in knowledge-based systems.

Abstract argumentation systems [Dung, 1993; Jakobovits, 1999; Vreeswijk, 1997; Kowalski and Toni, 1996; BenchCapon, 2002] are formalisms for defeasible reasoning where some components remain unspecified, being the structure of arguments the main abstraction. In this type of systems, the emphasis is put on elucidating semantic questions, such as finding the set of accepted arguments. Most of them are based on the single abstract notion of attack represented as a relation among the set of available arguments. If (A, B) are in the attack relation then in order to accept B it is necessary to find out if A is accepted or not, but not the other way around. From that relation, several argument extensions are defined as sets of possible accepted arguments. This primitive notion of defeat between arguments is the basis of the study of argumentation semantic, but a more detailed model will be useful to capture specific behaviour of concrete systems and to model well-structured argumentation processes.

Defeat between arguments must be defined over two basic elements: a notion of conflict and a comparison criterion for arguments. Finding a preferred argument is essential to determine a defeat relation [Simari and Loui, 1992; Prakken and Sartor, 1996; Amgoud, 1998; Stolzenburg et al., 2003]. However, the task of comparing arguments to establish a preference is not always successful. In this case, the classic abstract attack relation is no longer useful as a modelling tool.

In the dialectical process carried out to identify accepted arguments in the system, some controversial situations may be found. These situations are related to the reintroduction of arguments in this process, causing a circularity that must be avoided in order to prevent an infinite analysis. Consider for example three arguments A, B and C such that A is a defeater of B, B is a defeater of C and C is a defeater of A. In order to decide the acceptance of A, the acceptance of its defeaters must be analyzed first, including A itself.

An argumentation line is a sequence of defeating arguments, such as [A, B] or [A, B, C,A]. Whenever an argument A is encountered while analyzing arguments for and against A, a circularity occurs. Some systems apply a single restriction to argumentation lines: no previously considered argument is reintroduced in the process. In [Simari et al., 1994], the relation between circularity in argumentation and the comparison criteria used in the system is established. Arguments in such situations are called fallacious arguments and the circularity itself is called a fallacy. In somes systems such as [Jakobovits, 1999; Jakobovits and Vermeir, 1999], these arguments are classified as undecided arguments: they are not accepted nor rejected.

In this work, we show that a more specific restriction needs to be applied, other than to the prohibit reintroduction of previous arguments in argumentation lines. In the next section, we define the extended abstract framework, where conflicts and preference between arguments are considered, in order to characterize progressive argumentation lines.

2 Abstract Argumentation Framework

Our argumentation framework is formed by four elements: a set of arguments, and three basic relations between arguments.

Definition 1 An abstract argumentation framework (AF) is a quartet 〈AR,⊑,C,R〉, where AR is a finite set of arguments, ⊑ is the subargument relation, C is a symmetric and anti-reflexive binary conflict relation between arguments, C ⊆ AR × AR, and R is a preference relation among arguments.

Here, arguments are abstract entities [Dung, 1993] that will be denoted using calligraphic uppercase letters. No reference to the underlying logic is needed since we are abstracting the structure of the arguments. The symbol ⊑ denotes subargument relation: A ⊑ B means "A is a subargument of B". Any argument A is considered a superargument and a subargument of itself. Any subargument B ⊑ A such that B ̸= A is said to be a non-trivial subargument, denoted by symbol ⊏. The following notation will be also used: given an argument A then A- will represent a subargument of A, and A+ will represent a superargument of A. When no confusion may arise, subscript index will be used for distinguishing different subarguments or superarguments of A.

The conflict relation between two arguments A and B denotes the fact that these arguments cannot be accepted simultaneously since they contradict each other. For example, two arguments A and B that support complementary conclusions l and ¬l cannot be accepted together. The set of all pairs of arguments in conflict on the AF is denoted by C. Given a set of arguments S, an argument A ∈ S is said to be in conflict in S if there is an argument B ∈ S such that (A, B) ∈ C. The set Conf (A) is the set of all arguments X ∈ AR such that (A, X) ∈ C.

As stated by the following axiom, conflict relations have to be propagated to superarguments.

Axiom 1 (Conflict inheritance) Let Φ =〈AR,⊑,C,R〉 be an AF, and let A and B be two arguments in AR. If (A, B) ∈ C, then (A, B+) ∈ C, (A+, B) ∈ C, and (A+, B+) ∈ C, for any superargument A+ of A and B+ of B.

The constraints imposed by the conflict relation lead to several sets of possible accepted arguments. For example, if AR = {A, B} and (A, B) ∈ C, then {A} is a set of possible accepted arguments, and so is {B}. Therefore, some way of deciding among all the possible outcomes must be devised. In order to accomplish this task, the relation R is introduced in the framework and it will be used to evaluate arguments, modelling a preference criterion based on a measure of strength.

Definition 2 Given a set of arguments AR, an argument comparison criterion R is a binary relation on AR. If ARB but not BRA then A is preferred to B, denoted A ≻ B. If ARB and BRA then A and B are arguments with equal relative preference, denoted A ≡ B. If neither ARB or BRA then A and B are incomparable arguments, denoted A ▷◁ B.

As the comparison criterion is treated abstractly, we do not assume any property of R. Any concrete framework may establish additional rationality requirements for decision making.

Example 1 Φ = 〈AR,⊑,C,R〉 where AR = {A, B, C,D, E}, C = {{A, B}, {B, C}, {C,D}}, {C, E}}1 and A ≻ B, B ≻ C, E ▷◁ C and C ≡ D is an AF according to definition 1.

For two arguments A and B in AR, such that the pair (A, B) belongs to C the relation R is considered. If a concrete preference is made (A ≻ B or B ≻ A), then a defeat relation is established. It is said that the preferred argument is a proper defeater of the non-preferred argument. If the arguments are indifferent according to R, then they have the same relative conclusive force. For example, if the preference criterion establishes that smaller arguments are preferred, then two arguments of the same size are indifferent. On the other hand, arguments may be incomparable. For example, if the preference criterion states that argument A is preferred to B whenever the premises of A are included in the premises of B, then arguments with disjoint sets of premises are incomparable. This situation must be understood as a natural behaviour.

When two conflictive arguments are indifferent or incomparable according to R, the conflict between these two arguments remains unresolved. Due to this situation and to the fact that the conflict relation is a symmetric relation, each of the arguments is blocking the other one and it is said that both of them are blocking defeaters [Pollock, 1987; Simari and Loui, 1992]. An argument B is said to be a defeater of an argument A if B is a blocking or a proper defeater of A. In example 1, argument A is a proper defeater of argument B, while C is a blocking defeater of D and vice versa, D is a blocking defeater of C.

Abstract frameworks can be depicted as graphs, with different types of arcs. We use the arc ( · ) to denote the subargument relation. An arrow ( d47d47) is used to denote proper defeaters and a double-pointed arrow ( d111d111 d47d47) connects blocking defeaters. In figure 1, a simple framework is shown. Argument C is a subargument of A. Argument B is a proper defeater of C and D is a blocking defeater of B and viceversa.

Some authors leave the preference criteria unspecified, even when it is one of the most important components in the system. However, in many cases it is sufficient to establish a set of properties that the criteria must exhibit. A very reasonable one states that an argument is as strong as its weakest subargument [Vreeswijk, 1997]. We formalize this idea in the next definition.

Definition 3 (Monotonic preference relation) A preference relation R is said to be monotonic if, given A ≻ B, then A ≻ C, for any argument B ⊑ C.

1 When describing elements of C, we write {A, B} as an abbreviation for {(A, B), (B, A)}, for any arguments A and B in AR.

We will assume from now on that the criterion R included in the AF is monotonic. This is important because any argument A defeated by another argument B should also be defeated by another argument B+. In figure 1, argument B defeats C, but it should also be a defeater of A, because C is its subargument.

3 Defeat Paths

In [Dung, 1993], several semantic notions are defined. Other forms of clasifying arguments as accepted or rejected can be found in [Jakobovits, 1999; Jakobovits and Vermeir, 1999].

From a procedural point of view, when evaluating the acceptance of an argument, a set of conflict-related arguments are considered. An important structure of this process is captured in the following definition.

Definition 4 (Defeat path) A defeat path λ of an argumentation framework 〈AR,⊑,C,R〉 is a finite sequence of arguments [A1,A2, . . . ,An] such that argument Ai+1 is a defeater of argument Ai for any 0 < i < n. A defeat path for an argument A is any defeat path starting with A.

A defeat path is a sequence of defeating arguments. A maximal defeat path is a path that is not included in other path as a subsequence. The length of the defeat path is important for acceptance purposes, because an argument A defeated by an argument B may be reinstated by another argument C. In this case, it is said that argument C defends A against B. If the length of a defeat path for argument A is odd, then the last argument in the sequence is playing a supporting or defender role. If the length is even, then the last argument is playing an interfering or attacker role [Simari et al., 1994; Garc´ıa and Simari, 2004]. A partner of an argument Ai in the path λ is any argument Aj playing the same role in λ.

The notion of defeat path is very simple and only requires that any argument in the sequence must defeat the previous one. Under this unique constraint, which is the basis of argumentation processes, it is possible to obtain some controversial structures, as shown in the next examples.

Example 2 Let Φ = 〈AR,⊑,C,R〉 an argumentation framework where AR = {A, B, C A1-,A2-}, C={{A1-, B}, {B, C}, {A2-, C}, {A1-, C} . . .} and B ≻ A, C ≻ B, A2- ▷◁ C, A ▷◁ C.

By Axiom 1 if (A1-, B) ∈ C then also (A, B) ∈ C. The same is true for (A, C), due the inclusion of (A1-, C) in C.

The sequence λ1 = [A, B, C,A] is a defeat path in Φ, because B is a proper defeater of A, C is a proper defeater of B and A and C are blocking defeaters of each other. The argument A appears twice in the sequence, as the first and last argument. Note that in order to analyze the acceptance of A, it is necessary to analyze the acceptance of every argument in λ, including A. This is a circular defeat path for A.

The sequence λ2 = [A, B, C,A1-] is also a defeat path, because A1- and C are blocking defeaters of each other. Note that even when no argument is repeated in the sequence, the subargument A1- was already taken into account in the path, as argument B is its defeater. This sequence may be considered another circular defeat path for A.

The sequence λ3 = [A, B, C,A2-] is a defeat path in Φ, because A2- and C are blocking defeaters of each other. In this case, a subargument A2- of A appears in the defeat path for A. However, this is not a controversial situation, as A2was not involved in any previous conflict in the sequence. Argument B is defeating A just because (A1-, B) ∈ C, and is not related to A2-. Defeat path λ3 is correctly structured.

The initial idea of restricting the inclusion of arguments previously considered in the sequence is not enough. Even more, example 2 show that forbidding the inclusion of subarguments is not accurate, because valid argumentation lines (as path λ3) are thrown apart. Two main problematic situations must be taken into account, as shown in figures 2(a) and 2(b). The marked argument is reinserted in the defeat path. In the first case, it appears again as a defeater of C. In the second case, Ai is indirectly reinserted by including a superargument in the sequence.

d31

d31

d31

d31

Figure 2: (a) Direct reinsertion and (b) indirect reinsertion

Both situations are controversial and some well-formed structure must be devised. In the next section we explore these ideas.

4 Progressive Defeat Paths

In this section, we present the concept of progressive defeat paths, a notion related to acceptable argumentation lines defined for a particulary concrete system in [Garc´ıa and Simari, 2004]. First, we formalize the consequences of removing an argument from a set of arguments. This is needed because it is important to identify the set of arguments available for use in evolving defeat paths.

Suppose S is a set of available arguments used to construct a defeat path λ. If an argument A in S is going to be discarded in that process (i. e., its information content is not taken into account), then every argument that includes A as a subargument should be discarded too. Let S be a set of arguments and A an argument in S. The operator △ is defined as S △ A = S - Sp(A) where Sp(A) is the set of all superarguments of A.

As stated in Axiom 1, conflict relations are propagated through superarguments: if A and B are in conflict, then A+ and B are also conflictive arguments. On the other hand, whenever two arguments are in conflict, it is always possible to identify conflictive subarguments. This notion can be extended to defeat relations. Let A and B be two arguments such that B is a defeater of A. Then both arguments are in conflict and A ̸≻ B. By axiom 1, there may exist a subargument Ai ⊏ A such that (B,Ai) ∈ C. It is clear, as R is

d31

d31

d31

d31

d31

d31

d31

d31

monotonic, that Ai ̸≻ B, and therefore B is also a defeater of Ai. Thus, for any pair of conflictive arguments (A, B) there is always a pair of conflictive arguments (C, D) where C ⊑ A and D ⊑ B. Note that possibly C or D are trivial subarguments, that is the reason for the existence of the pair to be assured.

Definition 5 (Core conflict) Let A and B be two arguments such that B is a defeater of A. A core conflict of A and B is a pair of arguments (Ai, B) where (i) Ai ⊑ A, (ii) B is a defeater of Ai and (iii) there is no other argument Aj ⊏ Ai such that Aj is defeated by B.

The core conflict is the underlying cause of a conflict relation between two arguments, due to the inheritance property. Observe that the core conflict is not necessarily unique.

It is possible to identify the real disputed subargument, which is causing other arguments to fall in conflict. In figure 1, argument B defeats A because it is defeating one of its subarguments C. The core conflict of A and B is C. In this case the defeat arc between the superarguments may not be drawn.

Definition 6 (Disputed subargument) Let A and B be two arguments such that B is a defeater of A. A subargument Ai ⊑ A is said to be a disputed subargument of A with respect to B if Ai is a core conflict of A and B.

The notion of disputed subargument is very important in the construction of defeat paths in dialectical processes. Suppose argument B is a defeater of argument A. It is possible to construct a defeat path λ = [A, B]. If there is a defeater of B, say C, then [A, B, C] is also a defeat path. However, C should not be a disputed argument of A with respect to B, as circularity is introduced in the path. Even more, C should not be an argument that includes that disputed argument, because that path can always be extended by adding B again.

The set of arguments available to be used in the construction of a defeat path is formalized in the following definition. Definition 7 (Defeat domain) Let Φ = 〈AR,⊑,C,R〉 be an AF and let λ = [A1,A2, . . . ,An] be a defeat path in Φ. The function Di (λ) is defined as

• D1 (λ) = AR
• Dk (λ) = Dk-1 (λ) △ Bn, where Bn is the disputed subargument of Ak-1 with respect to Ak in the sequence, with 2 ≤ k ≤ n.

The defeat domain discards controversial arguments for a given path. The function Dk (λ) denotes the set of arguments that can be used to extend the defeat path λ at stage k, i. e., to defeat the argument Ak. Choosing an argument fromDk (λ) avoids the introduction of previous disputed arguments in the sequence. It is important to remark that if an argument including a previous disputed subargument is reintroduced in the defeat path, it is always possible to reintroduce its original defeater.

Therefore, in order to avoid controversial situations, any argument Ai of a defeat path λ should be in Di-1 (λ). Selecting an argument outside this set implies the repetition of previously disputed information. The following definition characterizes well structured sequences of arguments, called progressive defeat paths.

Definition 8 (Progressive defeat path) Let 〈AR,⊑,C,R〉 be an argumentation framework. A progressive defeat path is defined recursively in the following way:

• [A] is a progressive defeat path, for any A ∈ AR.
• If λ = [A1,A2, . . . ,An], n ≥ 1 is a progressive defeat path, then for any defeater B of An such that B ∈Dn (λ), and B is not defeated by a partner in λ, λ′ = [A1,A2, . . . ,An, B] is a progressive defeat path.

Progressive defeat paths are free of circular situations and guarantees progressive argumentation, as desired on every dialectical process. Note that it is possible to include a subargument of previous arguments in the sequence, as long as it is not a disputed subargument.

C -

In figure 3 a controversial abstract framework is shown. For space reasons we do not provide the formal specification, although it can be deduced from the graph. There are seven arguments A1,A2,A-, B, B-, C, C-. There exists an infinite defeat path [A1, B, C,A2, B, C..] which is not progressive. Lets construct a progressive defeat path λ for argument A1. We start with λ = [A1]. The pool of arguments used to select a defeater of A1 is D1 (λ) = {A2, A-, B, B-, C, C -}. The only defeater belonging to D1 (λ) is B, with disputed subargument A-, so we add it to λ. Now λ = [A1, B] and the pool of available arguments is D2 (λ) = {B, B-, C, C -}, where A- and its superarguments were removed. C ∈ D2 (λ) is a defeater of B so we add it to the path and now λ = [A1, B, C]. The potential defeater arguments are now in D3 (λ) = {C, C -}. As there are no defeaters of C in D3 (λ), then the path can not be extended. Thus, the resulting sequence [A1, B, C] is a progressive defeat path.

5 Progressively acceptable arguments

In Dung's approach [Dung, 1993] several semantic notions are defined as argument extensions. The set of accepted arguments is characterized using the concept of acceptability. An argument A ∈ AR is acceptable with respect to a set of arguments S if and only if every argument B attacking A is attacked by an argument in S. It is also said that S is defending A against its attackers, and this is a central notion on argumentation. A set R of arguments is a complete extension if R defends every argument in R. A set of arguments G is a grounded extension if and only if it is the least (with respect to set inclusion) complete extension. The grounded extension is also the least fixpoint of a simple monotonic function:

The framework of figure 3 may be completed with inherited defeat relations. For example, an arc fromB to A1 can be drawn, as shown in figure 4 (argument positions are relocated in order to simplify the graph). A cycle is produced involving arguments B, C and A2. According to a skeptical point of view, the grounded extension of the completed framework is the empty set, and no argument is accepted. Other notions as stable or preferred extensions may be applied to this framework. However, as a non-conflictive relation is present, a new premise must be stated: if an argument is accepted, then all of its subarguments are accepted. Therefore, any extension including, for example, argument A1 should also include argument A-.

When considering subarguments, new semantic extensions can be introduced in order to capture sets of possible accepted arguments.

We will focus here in the impact of progressive defeat paths in the acceptance of arguments.

Definition 9 (Dialectical space) Let 〈AR,⊑,C,R〉 be an AF. The dialectical space of an argument A ∈ AR is the set SPA = {λ|λ is a defeat path for A}.

The dialectical space for a given argument is formed by all of the defeat paths for that argument.

Example 3 In the simple argumentation framework of figure 5, SPA = {[A, B], [A, C, D, E]} and SPB = {[B]}.

The dialectical space may be infinite, if cycles are present. In figure 3 every argument has an infinite set of defeat paths. Consider the path [B, C,A2]. Because of the cycle, [B, C,A2, B] is also a defeat path. Therefore, defeat paths of any lenght may be constructed. In fact, every dialectical space in this framework is infinite.

Cycles of defeaters are very common in argumentation, usually called fallacies. The status of fallacious arguments cannot be determined, although they are not considered accepted as they are controversial in the framework. In many cases, using skeptical semantic concepts [Dung, 1993], an argument that is not taking part of a cycle cannot be accepted due to a fallacy. This is the case of argument A1 in figure 4. A credulous semantic may be defined using progressive defeat paths.

Several definitions are needed. We consider only progressive argumentation in order to evaluate the acceptance of an argument. Maximality of paths is important because all possible arguments must be taken into account.

Definition 10 (Progressive dialectical space) Let A be an argument. The progressive reduction of SPA, denoted SP R A , is the set of all maximal progressive defeat paths for A.

A notion of acceptability analogous to [Dung, 1993] may be defined, using a progressive dialectical space. As usual, an argument A is said to be defended by a set of arguments S if every defeater of A is defeated by an element of S. The defense of A by S occurs in a path λ = [A1, . . . , An] if A = Ai, 1 ≤ i ≤ n and the defender argument Ai+2 is in S.

Definition 11 (Defense) Given an argument A, a set P of defeat paths and a set of arguments S, A is said to be acceptable with respect to S in P if for every defeater B of A, S defends A against B in at least one element of P .

If A is defended against B in at least one defeat path in P then argument B is no longer a threat for A, no matter what is the situation in other defeat paths. In the framework of figure 5, argument C is defended by {E} in the defeat path [A, C, D, E] and therefore C is acceptable with respect to {E} in P = {[A, C,D, E]}. This fact cannot be changed adding new defeaters for D. Argument A, however, is not acceptable in SP R A , because it cannot be defended in [A, B].

Definition 12 (Grounded extension) Let P be a set of defeat paths. The grounded extension of P is the least fixpoint of the function FP (S) = {A : A is acceptable wrt S in P}.

The grounded extension for a set of defeat paths is analogous to the Dung's grounded extension for basic argumentation frameworks. In the framework of figure 3, SP R A1 = {[A1, B, C]}. In this set, F(∅) = {C}, F({C}) = {C,A1} and F({C,A1}) = {C,A1}. Then, the grounded extension of SP R A1 is {C,A1}.

Definition 13 (Warranted extension) Let Φ = 〈AR, ⊑, C, R〉 be an argumentation framework. A set of arguments S ⊆ AR is said to be a warranted extension, if every argument X in S belongs to the grounded extension of SP R X . Every argument of S is said to be warranted in Φ.

In the framework of figure 3, {A1,A-, B-, C -} is the warranted extension, as all of those arguments are in the grounded extension of its own progressive dialectical space.

6 RelatedWork

Since the introduction of Dung's seminal work [Dung, 1993] on the semantics of argumentation this area has been extremely active. This approach begins by defining an abstract framework in order to characterize the set of accepted arguments independently of the underlying logic. We followed this line in this work. In Dung's presentation no explicit preference relation is included, and the basic interaction between arguments is the binary, non-symmetric, attack relation. This style of argument attack is used in a number of different abstract frameworks, but none of them separates the notion of preference criteria from the conflict relation, as it is usually done in concrete systems. The classic attack relation allows the definition of mutual defeaters: two arguments attacking each other. This is not very realistic, as there is not an attack situation (in the sense of being conflictive and preferred to the opponent) but a controversial situation due to the lack of decision in the system. In our framework, this leads to blocking defeaters.

Several frameworks do include a preference relation. Vreeswijk, in [Vreeswijk, 1997], defines a popular abstract framework, making important considerations on comparison criterions. Other frameworks that consider the issue of preference relations are introduced in [Amgoud, 1998], [Amgoud and Cayrol, 1998] and in [Amgoud and Perrussel, 2000]. In these frameworks the basic interaction between agents is the classic attack relation, and the preference order is used as a defense against conflictive arguments. The defeat relation arises when the preferences agree with the attack. A similar situation occurs in [Bench-Capon, 2002], where a framework that includes a way to compare arguments is defined. A set of values related to arguments is defined in the framework. The defeat occurs when the value promoted by the attacked argument is not preferred to the value promoted by the attacker. Again, the preference order is used to check if the attacker argument is preferred, not to elucidate symmetric conflicts as it is used in our framework.

None of these proposals consider the subargument relation.

7 Conclusions

Abstract argumentation systems are formalisms for argumentation, where some components remains unspecified, usually the structure of arguments. In the dialectical process carried out to identify accepted arguments in the system, some controversial situations may be found, related to the reintroduction of arguments in this process, causing a circularity that must be treated in order to avoid an infinite analysis process. Some systems apply a single restriction to argumentation lines: no previously considered argument is reintroduced in the process. In this work, we have shown that a more specific restriction needs to be applied, taking subarguments into account in the context of an extended argumentation framework. We introduced an extended argumentation framework and a new definition of progressive defeat path, based on the concept of defeat domain, where superarguments of previously disputed arguments are discarded. We finally defined a credulous semantic for the proposed framework.

8 Acknowledgments

This paper was partially supported by the Dept. of Computer Science and Engineering, SECYT, U.N.Sur, the CONICET, Agencia Nacional de Promoci´on Cient´ıfica y Tecnol´ogica (PICT 13096, PICT 15043 and PAV076), Argentina.