## Thursday, 22 March 2007

### 10.1, Acceptability of Arguments

Notes taken from ‘On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games’, by Phan Minh Dung (1995)

1.1, Argumentation Frameworks

1, An argumentation framework is a pair AF = (AR, attacks) where AR is a set of arguments, and attacks is a binary relation on AR.

2, A set of arguments is said to be conflict-free if there are no arguments A, B in S such that A attacks B.

3, (1) An argument A is acceptable wrt a set S of arguments iff for each argument B: if B attacks A then B is attacked by S. (2) A conflict-free set of arguments S is admissible iff each argument in S is acceptable wrt S.

The (credulous) semantics of an argumentation framework is defined by the notion of preferred extension.

4, A preferred extension of an argumentation framework AF is a maximal (wrt set inclusion) admissible set of AF.

(Corollary 2) Every argumentation framework possesses at least one preferred extension. Hence, preferred extension semantics is always defined for any argumentation framework.

5, A conflict-free set of arguments S is called a stable extension iff S attacks each argument which does not belong to S.

(Lemma 3) S is a stable extension iff S = { A | A is not attacked by S}

(Lemma 4) Every stable extension is a preferred extension, but not vice versa.

1.2, Fixpoint Semantics and Grounded (Sceptical) Semantics

6, The characteristic function, denoted by F, of an argumentation framework AF is defined as follows: F(S) = {A | A is acceptable wrt S}

(Lemma 5) A conflict-free set S of arguments is admissible iff S is a subset of F(S).

It is easy to see that if an argument A is acceptable wrt S then A is also acceptable wrt any superset of S. Thus, it follows immediately that (Lemma 6) F is monotonic (wrt set inclusion).

The sceptical semantic of argumentation frameworks is defined by the notion of grounded extension:

7, The grounded extension of an argumentation framework AF, denoted by GE, is the least fixed-point of F.

8, An admissible set S of arguments is called a complete extension iff each argument which is acceptable wrt S, belongs to S.

Intuitively, the notion of complete extensions captures the kind of confident rational agent who believes in everything he can defend.

(Lemma 7) A conflict-free set of arguments E is a complete extension iff E = F(E).

The relations between preferred extensions, grounded extensions and complete extensions is as follows (Theorem 2):
(1) Each preferred extensions is a complete extension, but not vice-versa.
(2) The grounded extension is the least (wrt set inclusion) complete extension.
(3) …

In general, the intersection of all preferred extensions does not coincide with the grounded extension.

9, An argumentation framework AF = (AR, attacks) is finitary iff for each argument A, there are only finitely many arguments in AR which attack A.

1.3, Sufficient Conditions for Coincidence between Different Semantics

10, An argumentation framework is well-founded iff there exists no infinite sequence A0, A1, …, An, … such that for each i, Ai+1 attacks Ai. (Note: This eliminates cycles.)

(Theorem 3) Every well-founded argumentation framework has exactly one complete extension which is grounded, preferred and stable.

11, (1) An argumentation framework AF is said to be coherent if each preferred extension of AF is stable. (2) We say that an argumentation framework AF is relatively grounded if its grounded extension coincides with the intersection of all preferred extensions.

It follows directly from the definition that there exists at least one stable extension in a coherent argumentation framework.

An argument B indirectly attacks A if there exists a finite sequence A0, …, A2n+1 such that (1) A = A0 and B = A2n+1, and (2) for each i, 0<=i<=2n, Ai+1 attacks Ai.

An argument B indirectly defends A if there exists a finite sequence A0, …, A2n such that (1) A = A0 and B = A2n, and (2) for each i, 0<=i<=2n, Ai+1 attacks Ai.

An argument B is said to be controversial wrt A if B indirectly attacks A and indirectly defends A.

An argument is controversial if it is controversial wrt some argument A.

1.12, (1) An argumentation framework is uncontroversial if none of its arguments is controversial. (2) An argumentation framework is limited controversial if there exists no infinite sequence of arguments A0, …, An, … such that Ai+1 is controversial wrt Ai.

(Theorem 4) (1) Every limited controversial argumentation framework is coherent. (2) Every uncontroversial argumentation framework is coherent and relatively grounded.

An argument A is said to be a threat to a set of arguments S if A attacks S and A is not attacked by S. A set of arguments D is called a defence of a set of arguments S if D attacks each threat to S.

(Lemma 9) Let AF be a limited controversial argumentation framework. Then there exists at least one nonempty complete extension E of AF.

(Lemma 10) Let AF be an uncontroversial argumentation framework, and A be an argument such that A is not attacked by the grounded extension GE of AF and A is not in GE. Then (1) There exists a complete extension E1 such that A is in E1, and (2) There exists a complete extension E2 such that E2 attacks A.

(Corollary 11) Every limited controversial argumentation framework possesses at least one stable extension.