Labellings and Games for Extended Argumentation Frameworks

1 Introduction

Argumentation theory has a wide range of application in Artificial Intelligence [Bench-Capon and Dunne, 2007], including formalisation of non-monotonic reasoning, decision making over action, and negotiation and persuasion dialogues. Much of this work builds on Dung's seminal theory of argumentation [Dung, 1995]. A Dung argumentation framework (DF) is a directed graph consisting of a set of arguments A related by a binary conflict based attack relation R. The extensions, and so the justified status of their contained arguments, are then defined under different semantics. Extensions are defined based on the acceptability of arguments w.r.t sets of arguments; argument x is acceptable w.r.t S ⊆ A if any y that attacks x is itself attacked by some z ∈ S. Thus, the core admissible semantics defines an admissible extension as a subset S of A, all of whose contained arguments are acceptable w.r.t. S, and an extension under the preferred semantics is a set inclusion maximal admissible extension.

The widespread influence of Dung's work can be attributed to its abstract nature. The underlying logic, and definition of the logic's constructed arguments A and relation R is left unspecified, thus enabling instantiation of a framework by various logical formalisms. A theory's inferences are then defined as the claims of the justified arguments constructed from the theory (an argument essentially being a proof of a candidate inference - the argument's claim - in the underlying logic). Dung's theory thus provides a general framework for non-monotonic reasoning, and indeed, many logic programming formalisms and non-monotonic logics (e.g. default, auto-epistemic, and defeasible logics) have been shown to conform to Dung's semantics (e.g., in [Dung, 1995]).

Dung's extensional semantics may yield multiple extensions, raising the problem of how to choose between conflicting arguments in different extensions. The problem has been addressed by applying preferences to determine the success of attacks. For example, if x and y attack each other, then each is contained in a distinct preferred extension. However, given a preference for x over y, then y's attack on x does not succeed and we are left with x asymmetrically attacking y, and so {x} is the unique preferred extension. Thus, Dung's framework has been augmented with a preference ordering on arguments [Amgoud and Cayrol, 2002], and in value based argumentation [Bench-Capon, 2003], y's attack on x does not succeed if the value promoted by x is ranked higher than y's value, according to some given value ordering. However, one often needs to reason, and indeed argue about, as well as with, defeasible and possibly conflicting preference information. Hence, [Modgil, 2009] has recently extended Dung's theory to integrate 'metalevel' argumentation about preferences between arguments. The extended theory preserves the abstract nature of Dung's approach; no assumptions are made about the structure of arguments expressing preferences, and application of preferences is abstractly characterised, by defining a new attack relation that originates from a preference argument, and that attacks an attack between the arguments that are the subject of the preference claim. A new notion of acceptability is defined for the extended theory, and the extensions of an Extended Argumentation Framework (EAF) are then defined in the same way as for Dung frameworks.

The extensions of a DF can equivalently be defined in terms of labellings assigned to arguments [Caminada, 2007; Verheij, 2007], and this approach had led to development of algorithms for computing the extensions of a DF [Caminada, 2007]. The inherently dialectical nature of argumentation has also led to formulation of argument game proof theories, in which a proponent attempts to show that an argument is justified by countering attacking arguments moved by an opponent (e.g., [Cayrol et al., 2003; Modgil and Caminada, 2009]). This work has also underpinned algorithm development [Vreeswijk, 2006], and development of general frameworks for conflict resolution and persuasion dialogues [Prakken, 2005].

This paper formalises labellings and argument games for EAFs, and thus establishes foundations for development of algorithms for EAFs. In Section 2 we review Dung's argumentation theory and the extended theory. Sections 3, 4 and 5 then describe the three main contributions of this paper: 1) Section 3 defines the admissible, preferred and stable labellings of an EAF, and states soundness and completeness results with the acceptability based definitions. Our approach builds on the work of [Caminada, 2007] by additionally assigning labels to attacks; 2) Section 4 defines a dialectical framework for argument games for the extended theory. The framework generalises existing frameworks for argument games (e.g. [Cayrol et al., 2003]) to additionally allow players to move arguments that attack attacks; 3) Section 5 defines a specific game for deciding membership of admissible and preferred extensions of an EAF. Finally, Section 6 concludes and discusses future work.

2 Extended Argumentation Frameworks

A Dung argumentation framework (DF) [Dung, 1995] is a tuple (A, R), where R ⊆ A × A is an attack relation on the arguments in A. An argument x ∈ A is then said to be acceptable w.r.t. some S ⊆ A iff ∀y s.t. (y, x) ∈ R implies ∃z ∈ S s.t. (z, y) ∈ R (i.e., z reinstates x). We now recall Dung's definition of extensions under the admissible, preferred and stable semantics 1 , in which we refer to a set of arguments as conflict free iff ∀x, y ∈ S, (x, y), (y, x) /∈ R:

Definition 1 Let (A, R) be a DF, and S a conflict free subset of A. Then:

• S is an admissible extension iff every argument in S is acceptable w.r.t. S
• S is a preferred extension iff it is a set inclusion maximal admissible extension
• S is a stable extension iff ∀y /∈ S, ∃x ∈ S such that (x, y) ∈ R

An argument is sceptically preferred (stable) justified if it belongs to all preferred (stable) extensions, and only credulously preferred (stable) justified if it belongs to at least one, but not all, preferred (stable) extensions.

We now recall the extended argumentation theory [Modgil, 2009]. By way of motivation, consider individuals P and O exchanging arguments a, b . . . about the weather forecast:

P : "Today will be dry since the BBC forecast sunshine" = a

O : "Today will be wet since CNN forecast rain" = b

• P : "But the BBC are more trustworthy than CNN" = c

1 Grounded semantics for Dung's and the extended theory will be discussed in Section 6

O : "However, statistics show that CNN are more accurate than the BBC" = d

O : "And a statistical comparison is more rational than a comparison based on instincts about relative trustworthiness" = e Arguments a and b symmetrically attack ((a, b),(b, a) ∈ R), yielding the admissible and preferred extensions {a} and {b}. To choose amongst the two credulously justified arguments, so that one is sceptically justified at the expense of the other, one can incorporate 'metalevel' arguments expressing preferences over other arguments. Thus, c is an argument claiming that a is preferred to b. Intuitively, c is an argument for a's repulsion of b's attack on a, i.e., c attacks b's attack on a2 so that b's attack on a does not succeed and we are left only with a successfully attacking b (see Figure 1i) in which we introduce the notation y ⇀ x for an attack, and z ↠ (y ⇀ x) for an attack on an attack). Now {c, a} is the only preferred extension and so a is sceptically justified. d claims b is preferred to a and so attacks a's attack on b. Now {c, a} and {d, b} are preferred since the choice between a and b is unresolved given that c and d claim contradictory preferences and so c and d attack each other (Figure 1ii)). However e then attacks the attack from c to d (Figure 1iii)), and so d successfully attacks c, b successfully attacks a, and the discussion concludes in favour of b ({e, d, b} is the single preferred extension). Extended Argumentation Frameworks (EAFs) thus extend Dung frameworks with a second attack relation D from arguments to attacks. If (z, (x, y)) ∈ D then z is an argument for preferring y to x, and if any two such preference arguments express contradictory preferences, then they attack each other.

Definition 2 An Extended Argumentation Framework is a tuple (A, R, D), where A is a set of arguments, R ⊆ A×A, and:

• D ⊆ A×R
• If (z, (x, y)), (z′ , (y, x)) ∈ D then (z, z′ ), (z′ , z) ∈ R

The notion of a successful attack, from hereon referred to as a defeat, is then parameterised w.r.t. preferences specified by some given set S of arguments:

2 [Modgil, 2009] discusses why it is not appropriate to consider c as directly attacking b.

Definition 3 y defeatsS x, denoted y →S x, iff (y, x) ∈ R and ¬∃z ∈ S s.t. (z,(y, x)) ∈ S.

In the weather example, a defeats∅ b but does not defeat{d} b.

A conflict free set of arguments is then defined to account for the case where y asymmetrically attacks x, but given a preference for x over y, both may appear in a conflict free set and hence an extension (as in citeBC03). Notice that a conflict free set does not admit arguments that symmetrically attack, irrespective of the preference arguments contained.

The acceptability of an argument x w.r.t. a set S is now defined for an EAF. The basic idea is that for any attacker y of x, a reinstating attack z ⇀ y from z ∈ S, must be reinstated against preference argument attacks on z ⇀ y. The definition is motivated in more detail in [Modgil, 2009] and relates to an intuitive requirement (captured by Dung's fundamental lemma in [Dung, 1995]) on what it means for an argument to be acceptable w.r.t. an admissible set S of arguments: if x is acceptable with respect to S, then S ∪ {x} is admissible. To ensure satisfaction of this requirement, acceptability for EAFs requires the notion of a reinstatement set for a defeat.

Definition 5 Let S ⊆ A in (A, R, D). Let RS = {x1 →S y1, . . . , xn →S yn} where for i = 1 . . . n, xi ∈ S. Then RS is a reinstatement set for a →S b, iff a →S b ∈ RS, and

Definition 6 x is acceptable w.r.t. S ⊆ A iff ∀y s.t. y →S x, ∃z ∈ S s.t. z →S y and there is a reinstatement set for z →S y.

In Figure 1iv), a is acceptable w.r.t. S. We have b →S a, c →S b, and there is a reinstatement set {c →S b, c1 →S b1, c2 →S b2} for c →S b. Note that if we had b3 ↠ (c2 ⇀ b2), and no argument in S defeating b3, there would be no reinstatement set, and a would not be acceptable w.r.t. S.

Given the definitions of conflict free and acceptability for EAFs, admissible, preferred and stable semantics for EAFs are now defined as for DFs in Definition 1 (except that x defeatsS y replaces (x, y) ∈ R). [Modgil, 2009] shows that EAFs inherit many of the fundamental results that hold for DFs; in particular, Dung's fundamental lemma holds, and for each admissible S there exists a preferred extension S′ such that S ⊆ S′ .

Extended argumentation has been proposed as a general framework for non-monotonic logics that accommodate defeasible reasoning about priorities on rules. For example, [Modgil, 2009] shows that the inferences from logic programming theories with defeasible priorities [Prakken and Sartor, 1997] correspond to the grounded extension of the EAFs they instantiate. Furthermore, unlike [Prakken and Sartor, 1997], one can provide a well founded definition of the admissible and preferred extensions of such theories. The extended theory is also proposed as a unifying framework for formalising and extending works augmenting Dung frameworks with preferences and values [Modgil and Bench-Capon, 2008; Modgil, 2009], as a semantics for adaptive agent defeasible reasoning and conflict resolution [Modgil, 2007], and for conflict resolution in normative systems [Modgil and Luck, 2008]. Figure 2i) shows an EAF for argumentation over a course of medical action (logical formalisms for constructing these arguments are described in [Modgil, 2006]). a1 and a2 are arguments for prescribing drugs aspirin and chlopidogrel respectively, given that both realise a treatment goal to reduce blood clotting. b1 and b2 are arguments (based on clinical trials 1 and 2 respectively) expressing the contradictory conclusions that chlopidogrel is more efficacious than aspirin, and aspirin is more efficacious than chlopidogrel. c1 claims that trial 1 is more statistically robust than trial 2. a3 claims that chlopidogrel is costly, and so attacks a2, and b3 expresses that the value of improving patient health (promoted by a2) is greater than a3's value of cost. b4's contradictory value preference for cost over health mutually attacks b3, and finally, c3 is a utilitarian argument preferring b4 to b3 on the grounds that the cost of using chlopidogrel will compromise treatment of other patients. The EAF has a single preferred extension {c1, b1, c2, b4, a3, a1}; aspirin is the preferred choice.

3 Labellings for EAFs

This section builds on the work of [Caminada, 2007], and formalises labellings that characterise the admissible, preferred and stable extensions of an EAF. A labelling assigns exactly one label to each argument; either IN, OUT or UNDEC. The arguments labelled IN constitute an extension E under some given semantics, and the rules for deciding that an argument is legally IN intuitively correspond to deciding the acceptability of these arguments as defined in Section 2. OUT arguments are defeatedE by arguments in E, and an argument is UNDEC if it is neither in the extension or defeatedE by an argument in the extension. For EAFs, attacks on attacks and reinstatement of attacks may decide the acceptability of arguments. Hence, labels must also assigned to attacks in R, so that if (x, y) ∈ R is IN, respectively OUT, then this denotes that the attack (x, y) is successful, respectively unsuccessful. Finally, attacks can also be assigned UNDEC.

Definition 7 A labelling for an EAF(A,R,D) is a pair of total functions (LA,LR) such that:

1. LA : A ↦→ {IN, OUT, UNDEC}
2. LR : R ↦→ {IN, OUT, UNDEC}

We now define the notion of a legal labelling:

Definition 8 Let L = (LA, LR) be a labelling for (A, R, D). ∀x ∈ A:

1. x ∈ out(LA) is legally OUT iff ∃(y, x) ∈ R s.t. LA(y) = IN and LR((y, x)) = IN.
2. x ∈ in(LA) is legally IN iff ∀(y, x) ∈ R, either LA(y) = OUT or LR((y, x)) = OUT.
3. x ∈ undec(LA) is legally UNDEC iff:
4. (a) ¬∃(y, x) ∈ R such that LA(y) = IN and LR((y, x)) = IN, and;
5. (b) it is not the case that: ∀y ∈ A, (y, x) ∈ R implies LA(y) = OUT or LR((y, x)) = OUT

∀(y, x) ∈ R:

1. (y, x) ∈ out(LR) is legally OUT iff ∃ (z,(y, x)) ∈ D s.t. LA(z) = IN
2. (y, x) ∈ in(LR) is legally IN iff ∀ (z,(y, x)) ∈ D, LA(z) = OUT
3. (y, x) ∈ undec(LR) is legally UNDEC iff
4. (a) ¬∃ (z,(y, x)) ∈ D s.t. LA(z) = IN
5. (b) it is not the case that: ∀z ∈ A, (z,(y, x)) ∈ D implies LA(z) = OUT

For S ∈ {IN, OUT, UNDEC}:

• An argument x is said to be illegally S iff x ∈ s(LA), and it is not legally S.
• An attack (y, x) is said to be illegally S iff (y, x) ∈ s(LR), and it is not legally S.

Note, it is straightforward to show that LA and LR assign exactly one label to each argument, respectively attack. Also observe, that by definition, an argument or attack that is not attacked cannot be legally UNDEC. Also, Definition 8 implies that an attack (y, x) is legally UNDEC iff there exists at least one UNDEC labelled argument z that attacks (y, x), and no z′ attacking (y, x) is labelled IN. Similarly, an argument x is legally UNDEC iff there exists at least one (y, x) ∈ R such that y or (y, x) are UNDEC, and there is no (y, x) such that y and (y, x) are IN.

We now define admissible, preferred and stable EAF labellings and state a correspondence with the extensions as defined in Section 2.

Definition 9 Let L = (LA, LR) be a labelling for (A, R, D).

• L is admissible iff :
• no x ∈ A is illegally IN or illegally OUT
• no (y, x) ∈ R is illegally IN or illegally OUT
• ∀x, y ∈ in(LA), it is not the case that (y, x) ∈ R and (x, y) ∈ R
• L is prefered iff L is admissible and there does not exist an admissible L′ such that in(L′A) ⊃ in(LA)
• L is stable iff L is admissible, and undec(LA) = ∅, undec(LR) = ∅.

Theorem 1 Let Δ = (A, R, D) be an EAF, and E ⊆ A. For m ∈ {admissible, preferred, stable}:

E is an m extension of Δ iff there exists an m labelling (LA, LR) with in(LA) = E

Consider the preferred labelling identifying the preferred extension for the medical example EAF in Figure 2i). Consider also the labelled EAF in Figure 2ii). It is easy to verify that none of the arguments in the odd loop f ⇀ d ⇀ e ⇀ f can be legally assigned IN or OUT. The undecided status of these arguments 'contaminates' the attack a ⇀ b, so that only {a} is admissible and preferred, and there does not exist a stable extension. Notice the requirement that admissible labellings require that attacks are legally labelled IN (OUT). Suppose this were not the case, so that a ⇀ b was illegally labelled IN. Then b would be legally OUT and c legally IN. However, {a, c} is not admissible since c is not acceptable w.r.t. {a, c} (there is no reinstatement set for a →{a,c} b).

4 A dialectical framework for EAF games

Argument game proof theories establish the justified status of an argument to be tested, and provide a basis for algorithm development. In this section we define a dialectical framework for EAF game proof theories played as dialogues between two players - P (for "proponent") and O (for "opponent") - each of which are referred to as the other's 'counterpart'. We will from hereon assume finite EAFs that contain a finite number of arguments. A game begins with P moving an initial argument x to be tested. O and P then take turns in moving arguments that attack their counterpart's last move, where unlike games defined for Dung frameworks, a player can attack either an argument or an attack moved by its counterpart.

Definition 10 Let (A,R,D) be an EAF. A dialogue d is a possibly infinite sequence of moves m0,m1, . . . such that:

• d∅ denotes the empty sequence, m0 the 'initial move'
• each mi is of the form xPl where x ∈ A is the argument moved in mi, denoted by arg(mi), and Pl ∈ {P, O} is the player of mi, denoted pl(mi).
• pl(m0) = P, and pl(mi) ̸= pl(mi+1).
• m1 attack replies m0, and for ∀i > 1, either - mi attack replies mi-1 (denoted mi-1 ↼ mi), or - mi pref attack replies mi-1 (denoted mi-1 ↞ mi), and mi does not both attack and pref attack reply mi-1, where:
• mi attack replies mi-1 iff (arg(mi), arg(mi-1)) ∈ R
• ·mi pref attack replies mi-1 iff (arg(mi), (arg(mi-1), arg(mi-2)) ∈ D

A finite dialogue d = mo -m1 - . . . -mn is said to be won by Pl if pl(mn) = Pl (note that from hereon, if we write mi-1 -mi then '-' denotes either ↼ or ↞).

The rules of the game encode restrictions on the legality of a player's attack on its counterpart's previously moved argument or attack. Different sets of rules capture the different semantics under which justification of the argument moved by P in the initial move is to be shown, by effectively establishing when O or P run out of legal moves, and thus which player wins the dialogue. In what follows, we will refer to a generic legal move function φ that places restrictions on players' moves, and dialogues played according to φ as φdialogues.

In general, a player can backtrack to a counterpart's previous move and initiate a new dialogue. Consider the dialogue aP ↼ bO ↼ cP ↞ dO ↼ eP ↼ fO won by O (xPl denotes argument x moved by player Pl). P must then try and backtrack to move an argument against either O's move of b, or the attack b ⇀ a, or d, and so try and establish an alternative P winning dialogue (i.e., 'line of defense') for a. Suppose such a dialogue aP ↼ bO ↼ gP. Then O can backtrack and try an alternative O winning dialogue (i.e., 'line of attack') moving h against a, so that P must now try and win the newly initiated dialogue aP ↼ hO.

Thus, a φ game that establishes whether x is justified, is a tree of φ-dialogues whose root is P's initial move of x, and such that O fully fulfills its burden of attack by moving all φ legally allowed replies to each argument and attack moved by P, and P fully fulfills its burden of defense by moving at least one φ legally allowed reply to each argument or the associated attack moved by O. If every dialogue in such a game is won by P, then x is shown to be justified. Such a game is defined below as a winning strategy, in which we refer to the notion of a sub-dialogue d′ of a dialogue d, which is any sub-sequence of d that starts with the same initial move as d.

Definition 11 Let (A, R, D) be an EAF and T a non-empty finite set of finite φ-dialogues with initial move xP. Then T is a φ winning strategy for x iff:

1. Each dialogue in T is won by P.
2. ∀d ∈ T, ∀d′ such that d′ = m0 - . . . -m is some subdialogue of d and pl(m) = P, then if O can φ legally reply to m with m′ , there is a d′′ ∈ T such that d′ -m′ is a sub-dialogue of d′′ .

We now define notation that will be of use when specifying legal move functions:

Notation 1 Let d be a dialogue. For Pl ∈ {O, P}:

• PlA(d) = {x|arg(m) = x, pl(m) = Pl, m is a move in d} is the set of arguments moved by Pl in d.
• PlR(d) = {(x, y)|arg(m) = x, arg(m′ ) = y, pl(m) = Pl,m attack replies m′ in d} is the set of attacks moved by Pl in d.
• PlD(d) = {(z, (x, y)) | arg(m) = z, arg(m′ ) = x, pl(m) = Pl,m pref attack replies m′ in d} is the set of pref attacks moved by Pl in d.

5 An argument game for the credulous preferred semantics

In this section we define a legal move function φPC for the preferred credulous game. Since every admissible extension of an EAF is a subset of a preferred extension, it suffices to show membership of an admissible extension in order to show membership of a preferred extension.

The function φPC prevents O from moving arguments and attacks that have already been attacked by P in a dialogue, since P will have already fulfilled its burden of defense with respect to these arguments / attacks. One need only consider the framework x ⇌ y. Without the restriction on O, P's attempt to show that x is in the admissible {x} will result in an infinite dialogue xP ↼ yO ↼ xP ↼ yO . . . . Since every admissible extension is conflict free, φPC also prevents P from introducing a conflict into the arguments it has already moved in a dialogue. That is to say, P can only move an argument x in d if: 1) x does not attack itself, and; 2) no argument y, and attack (y, x) or (x, y) has been moved by P, and; 3) x does not symmetrically attack some y moved by P.

Definition 12 Given (A,R,D), and a dialogue d, then conflict(d) = {x|(x, x) ∈ R} ∪ {x|∃y ∈ PA(d), (x, y), (y, x) ∈ R} ∪ {x|∃y ∈ PA(d), (x, y) ∈ PR(d) or (y, x) ∈ PR(d)}

Definition 13 Given (A,R,D), and a dialogue d, then φPC is a legal move function such that:

• φPC(d∅) = A - {x|(x, x) ∈ R} (the initial move by P)
• If d is of odd length (next move is by O), then: if d = xP, then φPC(d) = {y | (y, x) ∈ R}, else if d = d′ - zO - xP then φPC(d) = {y | (y, x) ∈ R, (x′ , y) /∈ PR(d), (x′ , (y, x)) /∈ PD(d) } ∪{y | (y, (x, z)) ∈ D, (x′ , y) /∈ PR(d) }
• If d = d′ -zP -xO is of even length (next move is by P), then φPC(d) =
• {y | (y, x) ∈ R or (y,(x, z)) ∈ D, and y /∈ conflict(d) }

One can then show that the following holds:

Theorem 2 Given an EAF Δ = (A, R, D), x ∈ A is in an admissible extension of Δ iff there exists a φPC winning strategy T for x such that ⋃d∈T (PA(d)) is conflict free 3 .

3 [Modgil and Caminada, 2009] discuss why checks for conflict freeness of winning strategies are required

Figure 3 shows an EAF, and φPC winning strategy for a in which moves are individuated by numerical indicies indicating the order in which they are played. a is in the admissible and preferred extension {a, d, c}. Notice that P can move c at 3, since although c is attacked by P's previously moved a, the attack by a on c has not been moved by P. Indeed, cP3 forces O to move the attack of a on c, exposing this attack to P's pref attack with d at 5. Finally, the reader can easily verify that there is a φPC winning strategy for a1, and no φPC winning strategy for a2, for the EAF in Figure 2i).

6 Conclusions

In this paper we have built on the labelling approach of [Caminada, 2007] in order to formalise a labelling based characterisation of the admissible, preferred and stable extensions of EAFs, and thus provided foundations for future development of algorithms for computing extensions of EAFs. Future work will also formalise a labelling based characterisation of the grounded extension of an EAF. The grounded extension of a Dung framework (DF) is the least fixed point of a characteristic function F that takes as input a set S of arguments and returns the set S′ of arguments acceptable w.r.t. S. The characteristic function G for EAFs is not monotonic, so that a least fixed point cannot be guaranteed. Hence the grounded extension of an EAF is defined constructively, by iteration of G, beginning with the empty set (analogous to construction of a DF's grounded extension). This in turn means that the grounded extension of an EAF cannot be readily characterised by a labelling that adapts the grounded labellings defined by [Caminada, 2007] for DFs 4 .

In this paper we have defined a dialectical framework for EAF argument game proof theories that determine the justified status of arguments. We have defined a specific game within the framework for the credulous preferred semantics, and future work will focus on specifying a game for the grounded semantics. An advantage of dialectical games is that they relate formal entailment to something most people are familiar with in everyday life: debates and discussions. These games will thus not only provide guidelines for the design of algorithms for computing the justified arguments of an EAF, but will also inform development of frameworks for argumentation based negotiation, deliberation and persuasion dialogues in which participants can debate preferences.