Sage Journals: Discover world-class research

Abstract

In this document, we describe the concepts of ideal semantics and stage semantics for abstract argumentation in terms of argument labellings. The difference between the traditional extensions approach and the labelling approach is that where the former only identifies the sets of accepted arguments, the latter also identifies the rejected arguments as well as the arguments that are neither accepted nor rejected. So far, the labellings approach has been successfully applied to complete, grounded, preferred, stable and semi-stable semantics, as well as to the concept of admissibility. In the current paper, we continue this line of research by showing that ideal semantics and stage semantics can also be described in terms of argument labellings.

Keywords

formal models of argumentation argumentation frameworks argumentation semantics

1. Introduction

Formal argumentation has become a popular approach for purposes varying from non-monotonic reasoning (Amgoud et al. 2006; Caminada and Amgoud 2007), multi-agent communication (Amgoud, Maudet, and Parsons 2000) and reasoning in the semantic web (Rahwan, Zablith, and Reed 2007). Although some research on formal argumentation can be traced back to the early 1990s (like, for instance, the work of Vreeswijk 1993 and of Simari and Loui 1992), the topic really started to take off with Dung's theory of abstract argumentation (Dung 1995). Here, arguments are seen as abstract entities (although they can be instantiated using approaches like Caminada and Amgoud 2007 and Prakken and Sartor 1997) among which an attack relationship is defined. The thus-formed argumentation framework can be represented as a directed graph in which the arguments serve as nodes and the attack relation as the arrows.

Given such a graph, an interesting question is which sets of nodes can reasonably be accepted? Several criteria of acceptance have been stated, including Dung's original approaches of grounded, complete, preferred and stable semantics (Dung 1995), as well as other approaches like semi-stable semantics1

1
Semi-stable semantics was described in terms of admissible stage extensions in Verheij (1996).
(Verheij 1996; Caminada 2006c) and ideal semantics (Dung 2007).

The concepts of admissibility, as well as that of complete, grounded, preferred, stable or semi-stable semantics were originally stated in terms of sets of arguments. It is equally well possible, however, to express these concepts using argument labellings. This approach was pioneered by Pollock (1995) and has subsequently been applied by Verheij (1996), Jakobovits and Vermeir (1999), Caminada (2006a, 2007), Caminada and Gabbay (2009) and Vreeswijk (2006). In this paper, we follow the approach of Caminada (2006a, 2007) and Caminada and Gabbay (2009) where each argument is assigned a label, which can either be in, out or $undec$ . The label in indicates that the argument is explicitly accepted, the label out indicates that the argument is explicitly rejected and the label $undec$ indicates that the status of the argument is undecided, meaning that one abstains from an explicit judgment whether the argument is in or out.

An advantage of the labellings approach is that it becomes possible to describe complete, preferred, grounded, stable and semi-stable semantics without having to refer to technical concepts like admissibility or fixpoints of the characteristic function F, as explained in Caminada (2006a) and Caminada and Gabbay (2009). Moreover, the labelling approach has also been used for defining argumentation-based algorithms, for instance for algorithms that, given an argumentation framework, compute its stable, semi-stable or preferred labellings (Caminada 2007; Modgil and Caminada 2009) (of which the sets of in-labelled arguments correspond to the stable, semi-stable and grounded extensions, respectively). Another recent application of argument labellings is in the field of judgement aggregation. In essence, a (complete) labelling can be seen as a reasonable position an agent can take in the presence of the conflicting information expressed in the argumentation framework. The question then becomes how several such positions can be aggregated to a collective opinion. This has been the topic of work of Caminada and Pigozzi (2009), as well as of Rahwan and Tohmé (2010).

In previous work (Caminada 2006a,b; Caminada and Gabbay 2009) labellings have been specified for complete, stable, semi-stable, preferred and grounded semantics. The key concept is that of a complete labelling, which is shown to implement complete semantics (Caminada 2006a; Caminada and Gabbay 2009). The other semantics can then be described in terms of complete labellings in which the occurrence of a particular type of label is maximised or minimised. A preferred labelling, for instance, can be described as a complete labelling in which the set of in-labelled arguments is maximal (w.r.t. set-inclusion). Similarly, a grounded labelling can be described as a complete labelling in which the set of in-labelled arguments is minimal, and a semi-stable labelling as a complete labelling in which the set of $undec$ -labelled arguments is minimal. In the present paper, we apply the labellings approach to two additional semantics: ideal (Dung et al. (2007) and stage (Verheij 1996). Although these semantics cannot be described by simply maximising or minimising the occurrence of a particular type of label using complete labellings (as is the case for grounded, preferred and semi-stable semantics), we show that the labelling approach can nevertheless be meaningfully applied. We show that ideal semantics can be described in terms of judgement aggregation. In particular, we show that the ideal labelling is the most committed admissible (or complete) labelling that is compatible with each admissible, complete or preferred labelling. Where the key concept of ideal semantics is that of compatibility with other labellings (Section 3), the key concept of stage semantics is that of maximal consistency (Section 4). In essence, a stage labelling is a stable labelling of a maximal subgraph of the argumentation framework that has at least one stable labelling, augmented by labelling all arguments $undec$ that are outside of the subgraph. However, before being able to explain ideal and stage labellings in more detail, we first provide some formal preliminaries in Section 2.
2. Formal preliminaries

An argumentation framework (Dung 1995) consists of a set of arguments and an attack relation on these arguments. In order to simplify the discussion, we consider only finite argumentation frameworks.

Definition 2.1
An argumentation framework is a pair $(Ar, att)$ , where Ar is a set of arguments and $att \subseteq Ar \times Ar$ .

We say that (1) an argument A attacks an argument B iff $(A, B) \in att$ , (2) an argument A attacks a set of arguments $A rgs$ iff A attacks an argument in $A rgs$ , (3) a set of arguments attacks an argument A iff an argument in $A rgs$ attacks A and (4) a set of argument $A {rgs}_{1}$ attacks a set of arguments $A {rgs}_{2}$ iff an argument in $A {rgs}_{1}$ attacks an argument in $A {rgs}_{2}$ .

The shorthand notation A⁺ and A⁻ stands for, respectively, the set of arguments attacked by argument A and the set of arguments that attack argument A. Likewise, if $A rgs$ is a set of arguments, then we write $A {rgs}^{+}$ for the set of arguments that are attacked by at least one argument in $A rgs$ , and $A {rgs}^{-}$ for the set of arguments that attack at least one argument in $A rgs$ . In the definition below, $F (A rgs)$ stands for the set of arguments that are acceptable in the sense of Dung (1995).
Definition 2.2 defence/conflict-free

Let $(Ar, att)$ be an argumentation framework, $A \in Ar$ and $A rgs \subseteq Ar$ . We define A⁺as ${B ∣ A att B}$ and $A {rgs}^{+}$ as ${B ∣ A att B$ for some $A \in A rgs}$ . We define A⁻as ${B ∣ B att A}$ and $A {rgs}^{-}$ as ${B ∣ B att A$ for some $A \in A rgs}$ . $A rgs$ is conflict-free iff $A rgs \cap A {rgs}^{+} = \emptyset$ . $A rgs$ defends an argument A iff $A^{-} \subseteq A {rgs}^{+}$ . We define the function $F : 2^{Ar} \to 2^{Ar}$ as $F (A rgs) = {A ∣ A$ is defended by $A rgs}$ .

In the definition below, notions of grounded, preferred and stable semantics are described in terms of complete semantics. These descriptions are not literally the same as those provided by Dung (1995), but as was stated in Caminada (2006a), these are in fact equivalent to Dung's original versions of grounded, preferred and stable semantics.

Definition 2.3 acceptability semantics

Let $(Ar, att)$ be an argumentation framework and let $A rgs \subseteq Ar$ be a conflict-free set of arguments.

$A rgs$ is admissible iff $A rgs \subseteq F (A rgs)$ .

$A rgs$ is a complete extension iff $A rgs = F (A rgs)$ .

$A rgs$ is a grounded extension iff $A rgs$ is the minimal (w.r.t. set-inclusion) complete extension.

$A rgs$ is a preferred extension iff $A rgs$ is a maximal (w.r.t. set-inclusion) complete extension.

$A rgs$ is a stable extension iff $A rgs$ is a complete extension that attacks every argument in $Ar ∖ A rgs$ .

$A rgs$ is a semi-stable extension iff $A rgs$ is a complete extension where $A rgs \cup A {rgs}^{+}$ is maximal (w.r.t. set-inclusion).

In Caminada (2006a) and Caminada and Gabbay (2009) it is described how the concepts of complete, grounded, preferred, stable and semi-stable semantics, as well as the concept of admissibility, can be characterised in terms of argument labellings.

Definition 2.4
Let $(Ar, att)$ be an argumentation framework. A labelling is a total function $L ab : Ar \to {in, out, undec}$ .

We write $in (L ab)$ for ${A ∣ L ab (A) = in}$ , $out (L ab)$ for ${A ∣ L ab (A) = out}$ and $undec (L ab)$ for ${A ∣ L ab (A) = undec}$ . Sometimes, we write a labelling $L ab$ as a triple $(A {rgs}_{1}, A {rgs}_{2}, A {rgs}_{3})$ where $A {rgs}_{1} = in (L ab)$ , $A {rgs}_{2} = out (L ab)$ and $A {rgs}_{3} = undec (L ab)$ .

We introduce two functions ( $Lab 2 Ext$ and $Ext 2 Lab$ ) that allow one to convert a labelling to an extension, and an extension to a labelling. When converting a labelling to an extension, one basically selects the set of in-labelled arguments. That is, $Lab 2 Ext (L ab) = in (L ab)$ . When converting an extension to a labelling, one labels the arguments of the extension in, the arguments attacked by the extension out and the other arguments $undec$ . That is, $Ext 2 Lab (A rgs) = (A rgs, A {rgs}^{+}, Ar ∖ (A rgs \cup A {rgs}^{+}))$ , where Ar is the set of all arguments in the argumentation framework. Notice that although $Lab 2 Ext$ is defined for any labelling, $Ext 2 Lab$ is defined only for sets of arguments that are conflict-free (otherwise the result would not be a correct labelling).
Definition 2.5
Let $(Ar, att)$ be an argumentation framework. An admissible labelling is a labelling such that for every $A \in Ar$ it holds that:
if A is labelled in, then all attackers of A are labelled out

if A is labelled out, then A has an attacker that is labelled in

Admissible labellings correspond to admissible sets, although the relationship is not one-to-one.2 2
For instance, in the argumentation framework of Figure 2, both $({A}, \emptyset, {B, C})$ and $({A}, {B}, {C})$ are admissible labellings that are associated with the same admissible set {A}.

Theorem 2.6
Let $AF = (Ar, att)$ be an argumentation framework. It holds that:
if $A rgs$ is an admissible set of AF, then $Ext 2 Lab (A rgs)$ is an admissible labelling of AF, and

if $L ab$ is an admissible labelling of AF, then $Lab 2 Ext (L ab)$ is an admissible set of AF.

Definition 2.7
Let $(Ar, att)$ be an argumentation framework. A complete labelling is a labelling such that for every $A \in Ar$ it holds that:
if A is labelled in, then all attackers of A are labelled out

if A is labelled out, then A has an attacker that is labelled in

if A is labelled $undec$ , then not all attackers of A are labelled out and A does not have an attacker that is labelled in

Notice that the first two conditions of a complete labelling are the same conditions as of an admissible labelling. Whereas an admissible labelling requires one to be able to explain why an argument is labelled in and why an argument is labelled out, a complete labelling also requires one to explain why an argument is labelled $undec$ .

It is also possible to describe a complete labelling in a different way.
Proposition 2.8 Caminada and Pigozzi 2009

Let $L ab$ be a labelling of an argumentation framework $AF = (Ar, att)$ . $L ab$ is a complete labelling iff for each argument $A \in Ar$ it holds that:

A is labelled in iff all its attackers are labelled out, and

A is labelled out iff it has at least one attacker that is labelled in.

The difference between Definition 2.7 and Proposition 2.8 is that the former describes a complete labelling using three if-statements, and the latter describes it using two iff-statements. Although the latter description does not explicitly mention the $undec$ label, it follows that for an argument to be labelled $undec$ , it cannot have all its attackers labelled out (otherwise it would have to be labelled in according to point 1 of Proposition 2.8). Similarly, it cannot have an attacker that labelled in (otherwise it would have to be labelled out according to point 2 of Proposition 2.8). These two observations, when put together, are equivalent with point 3 of Definition 2.7. Hence, the description of complete labellings of Proposition 2.8 puts restrictions on the use of the $undec$ label, even without explicitly referring to it.

Lemma 2.9 Caminada and Pigozzi 2009

Let $L {ab}_{1}$ and $L {ab}_{2}$ be complete labellings of argumentation framework $AF = (Ar, att)$ . It holds that:

$in (L {ab}_{1}) \subseteq in (L {ab}_{2})$ iff $out (L {ab}_{1}) \subseteq out (L {ab}_{2})$ ,

$in (L {ab}_{1}) ⊊ in (L {ab}_{2})$ iff $out (L {ab}_{1}) ⊊ out (L {ab}_{2})$ and

$in (L {ab}_{1}) = in (L {ab}_{2})$ iff $out (L {ab}_{1}) = out (L {ab}_{2})$ .

Complete labellings correspond to complete extensions, as is stated by the following theorem.

Theorem 2.10
Let $AF = (Ar, att)$ be an argumentation framework. It holds that:
if $A rgs$ is a complete extension of AF, then $Ext 2 Lab (A rgs)$ is a complete labelling of AF, and

if $L ab$ is a complete labelling of AF, then $Lab 2 Ext (L ab)$ is a complete extension of AF.

In Caminada and Pigozzi (2009), it is also proved that the relationship between complete labellings and complete extensions is one-to-one. That is, each complete labelling is associated to exactly one complete extension and vice versa. This property can be seen as a result of Lemma 2.9.

Using the concept of complete labellings, one can then also describe the concept of grounded, preferred, stable and semi-stable semantics in terms of argument labellings, as has been done in Caminada and Pigozzi (2009). A summary is provided in the following definition.
Definition 2.11
Let $L ab$ be a complete labelling of argumentation framework $AF = (Ar, att)$ .
$L ab$ is a preferred labelling iff $in (L ab)$ is maximal w.r.t. set-inclusion among all complete labellings.

$L ab$ is the grounded labelling iff $in (L ab)$ is minimal w.r.t. set-inclusion among all complete labellings.

$L ab$ is a semi-stable labelling iff $undec (L ab)$ is minimal w.r.t. set-inclusion among all complete labellings.

$L ab$ is a stable labelling iff $undec (L ab) = \emptyset$ .

Preferred, grounded, semi-stable and stable labellings correspond to preferred, grounded, semi-stable and stable extensions, respectively, as stated in the following theorem.
Theorem 2.12
Let $AF = (Ar, att)$ be an argumentation framework. It holds that:
if $A rgs$ is a preferred extension of AF then $Ext 2 Lab (A rgs)$ is a preferred labelling of AF, and if $L ab$ is a preferred labelling of AF, then $Lab 2 Ext (L ab)$ is a preferred extension of AF.

if $A rgs$ is the grounded extension of AF then $Ext 2 Lab (A rgs)$ is the grounded labelling of AF, and if $L ab$ is the grounded labelling of AF, then $Lab 2 Ext (L ab)$ is the grounded extension of AF.

if $A rgs$ is a semi-stable extension of AF then $Ext 2 Lab (A rgs)$ is a semi-stable labelling of AF, and if $L ab$ is a semi-stable labelling of AF, then $Lab 2 Ext (L ab)$ is a semi-stable extension of AF.

if $A rgs$ is a stable extension of AF then $Ext 2 Lab (A rgs)$ is a stable labelling of AF, and if $L ab$ is a stable labelling of AF, then $Lab 2 Ext (L ab)$ is a stable extension of AF.

Since for complete semantics, the relation between labellings and extensions is one-to-one, it follows that for preferred, grounded, stable and semi-stable semantics the relation between labellings and extensions is also one-to-one.

It turns out that there are different ways to describe the concepts of preferred, grounded, semi-stable and stable labellings. For instance, a preferred labelling can also be described as a complete labelling where the set of out-labelled arguments is maximal. Similarly, the grounded labelling can also be described as the complete labelling where the set of out-labelled arguments is minimal, or where the set of $undec$ -labelled arguments is maximal.

Table 1, taken from Caminada (2006a) and Caminada and Gabbay (2009), examines what happens when one focuses on complete labellings in which one particular label has been maximised or minimised. It turns out that in all but one case, one obtains a correspondence with one of the semantics described in Dung (1995). The only exception is when one minimises $undec$ , in which one obtains correspondence with a semantics that was introduced in Caminada (2006c).

Although Table 1 nicely shows how the traditional semantics of Dung (1995) plus the one from Caminada (2006c) fit together, it only treats semantics that can be expressed using maximality or minimality of one of the labels. In the current paper, we will therefore treat two other semantics that are not defined using maximality or minimality conditions of complete labellings: ideal semantics and stage semantics. We show that the labelling approach is nevertheless capable not only of capturing these semantics, but also in contributing to understanding what these semantics are essentially all about.

Table 1.
Argument labellings and Dung-style semantics (Caminada and Gabbay 2009).

Restriction complete labellings Dung-style semantics

No restrictions Complete semantics

Empty $undec$ Stable semantics

Maximal in Preferred semantics

Maximal out Preferred semantics

Maximal $undec$ Grounded semantics

Minimal in Grounded semantics

Minimal out Grounded semantics

Minimal $undec$ Semi-stable semantics

3. Ideal semantics

Restriction complete labellings	Dung-style semantics
No restrictions	Complete semantics
Empty $undec$	Stable semantics
Maximal in	Preferred semantics
Maximal out	Preferred semantics
Maximal $undec$	Grounded semantics
Minimal in	Grounded semantics
Minimal out	Grounded semantics
Minimal $undec$	Semi-stable semantics

The intuition behind ideal semantics 3

3
Please notice that we do not intend to give any value judgement by adopting the term “ideal semantics”.
(Dung et al. 2007) can perhaps be best explained as a form of judgement aggregation (Caminada and Pigozzi 2009), where a set of judgements (labellings) is combined to reach an aggregated judgement (labelling). The idea is to start with a group of people who individually try to accept as much as possible. The process of judgment aggregation then examines what they all agree on and whether the aggregated judgment (labelling) is still reasonable (admissible). If not, then some argument that were accepted (in) or rejected (out) are abstained from having an opinion about (that is, they are relabelled to $undec$ ). This process is repeated until the resulting overall judgment (labelling) is reasonable (admissible). The result is the ideal labelling.

In order to formally define the concept of the ideal labelling, we first need to treat some preliminaries from Caminada and Pigozzi (2009).
Definition 3.1 Caminada and Pigozzi 2009

Let $L {ab}_{1}$ and $L {ab}_{2}$ be labellings of argumentation framework $AF = (Ar, att)$ . We say that $L {ab}_{2}$ is more or equally committed than $L {ab}_{1}$ (written as $L {ab}_{1} ⊑ L {ab}_{2}$ ) iff $in (L {ab}_{1}) \subseteq in (L {ab}_{2})$ and $out (L {ab}_{1}) \subseteq out (L {ab}_{2})$ . We say that $L {ab}_{2}$ is compatible with $L {ab}_{1}$ (written as $L {ab}_{1} \approx L {ab}_{2}$ ) iff $in (L {ab}_{1}) \cap out (L {ab}_{2}) = \emptyset$ and $out (L {ab}_{1}) \cap in (L {ab}_{2}) = \emptyset$ .

It holds that “⊑” defines a partial order (reflexive, anti-symmetric, transitive) on the labellings of an argumentation framework. We can therefore talk about a labelling being “bigger” or “smaller” than another labelling with respect to “⊑”. The relation “≈”, although reflexive and symmetric, is not an equivalence relation, since it does not satisfy transitivity.4

4
As a counterexample, consider an argumentation framework $AF = ({A, B}, {(A, B), (B, A)})$ . Let $L {ab}_{1} = ({A}, {B}, \emptyset)$ , $L {ab}_{2} = (\emptyset, \emptyset, {A, B})$ and $L {ab}_{3} = ({B}, {A}, \emptyset)$ . It holds that $L {ab}_{1} \approx L {ab}_{2}$ and $L {ab}_{2} \approx L {ab}_{3}$ but $L {ab}_{1} ≉ L {ab}_{3}$ .
It holds that “⊑” is at least as strong as “≈”; that is, if $L {ab}_{1} ⊑ L {ab}_{2}$ then $L {ab}_{1} \approx L {ab}_{2}$ .5 5
This is because $L {ab}_{1} \approx L {ab}_{2}$ iff $in (L {ab}_{1}) \subseteq in (L {ab}_{2}) \cup undec (L {ab}_{2})$ and $out (L {ab}_{1}) \subseteq out (L {ab}_{2}) \cup undec (L {ab}_{2})$ .

The idea of “⊑” is to define what it means for a labelling to be more committed than another labelling. For instance, the grounded labelling is the least committed labelling among all complete labellings. The idea of “≈” is to define when a labelling of one person might still be acceptable to another person. To see this, first consider that by requiring that $in (L {ab}_{1}) \cap out (L {ab}_{2}) = \emptyset$ and $out (L {ab}_{1}) \cap in (L {ab}_{2}) = \emptyset$ , the relation “≈” does not allow for conflicts between in and out. That is, if there is an argument that is accepted by agent A but rejected by agent B (or vice versa), then their labellings are not compatible. However, there is no problem in having conflicts between in and $undec$ , or between out and $undec$ . Thus, the idea of compatibility is to provide an indication of how easy or difficult it is to have to defend a position that is not one's own. It is easier to do this for a labelling that is compatible than for a labelling that is not compatible. In the former case, the worst that can happen is that one has to abstain from something one accepts or rejects (or have to accept or reject something where one did not have an explicit opinion about). In the latter case, however, one has to make statements that go directly against one's private position.

To come back to the informal description of ideal semantics, we assume a meeting in which every preferred labelling is represented. The meeting then discusses each argument, one by one, with the aim to define an initial labelling. If everybody agrees that the argument is labelled in (that is, the argument is labelled in in every preferred labelling), then the argument is also labelled in in the initial labelling. If everybody agrees that the argument is labelled out (that is, the argument is labelled out in every preferred labelling), then the argument is labelled out in the initial labelling. In all other cases, the argument is labelled $undec$ in the initial labelling. After this process is over, and the initial labelling has been finished, the meeting goes to the second phase, in which the initial labelling is “watered down” in order to become an admissible labelling. This is done by iteratively relabelling each argument that is illegally in or illegally out to $undec$ . When there are no more arguments left that are illegally in or illegally out, the result is the ideal labelling. It was proved in Caminada and Pigozzi (2009) that this process results in constructing the most committed (“biggest”) labelling that is less or equally committed to each preferred labelling. This leads to the following definition of ideal semantics.
Definition 3.2
Let $AF = (Ar, att)$ be an argumentation framework. The ideal labelling is the biggest admissible labelling that is smaller or equal to each preferred labelling.

The uniqueness of the ideal labelling has been proved in Caminada and Pigozzi (2009).6 6
The idea is to perform the sceptical judgment aggregation procedure of Caminada and Pigozzi (2009) on all preferred labellings.
It also holds that the ideal labelling is a complete labelling (Caminada and Pigozzi 2009). Since the grounded labelling is the smallest complete labelling (w.r.t. “≈”) it directly follows that the ideal labelling is bigger or equal to the grounded labelling.
Proposition 3.3
Let $(Ar, att)$ be an argumentation framework, let $L {ab}_{grounded}$ be its grounded extension and $L {ab}_{ideal}$ be its ideal extension. It holds that $L {ab}_{grounded} ⊑ L {ab}_{ideal}$ .

In the current paper, we extend the results of Caminada and Pigozzi (2009) by proving that the ideal labelling is also the biggest admissible labelling that is compatible with each admissible/complete/preferred labelling.
Theorem 3.4
Let $L ab$ be a labelling of argumentation framework $AF = (Ar, att)$ . The following statements are equivalent:
$L ab$ is the biggest admissible labelling that is smaller or equal to each preferred labelling (that is, $L ab$ is the ideal labelling).

$L ab$ is the biggest admissible labelling that is compatible with each admissible labelling.

$L ab$ is the biggest admissible labelling that is compatible with each complete labelling.

$L ab$ is the biggest admissible labelling that is compatible with each preferred labelling.

Proof
From 1 to 2: Let $L ab$ be the biggest admissible labelling that is smaller or equal to each preferred labelling. Then $A rgs = in (L ab)$ is the biggest admissible set that is a subset of each preferred extension. This can be seen as follows. First of all, $A rgs$ is an admissible set that is a subset of each preferred extension (this is because from $L ab ⊑ L {ab}^{'}$ it follows that $in (L ab) \subseteq in (L {ab}^{'})$ ). We now prove that $A rgs$ is also the biggest admissible set that is a subset of each preferred extension. Let $A {rgs}^{'}$ be an admissible set that is a subset of each preferred extension. Then $L {ab}^{'} = Ext 2 Lab (A {rgs}^{'})$ is an admissible labelling that is smaller or equal to each preferred labelling (this follows from Lemma 2.9). So $L {ab}^{'} ⊑ L ab$ (this is because $L ab$ is the biggest admissible labelling that is smaller or equal to each preferred labelling). So $in (L {ab}^{'}) \subseteq in (L ab)$ so $A {rgs}^{'} \subseteq A rgs$ . So $A rgs$ is indeed the biggest (w.r.t. set-inclusion) admissible set that is a subset of each preferred extension. We can then apply the results from (Dung et al. 2007, Theorem 3.3): If $A rgs$ is the biggest admissible set that is a subset of each preferred extension, then $A rgs$ is the biggest admissible set that is not attacked by any admissible set. We now prove that $L ab$ is an admissible labelling that is compatible with each admissible labelling. Let $L {ab}_{adm}$ be an arbitrary admissible labelling and let $A {rgs}_{adm} = in (L {ab}_{adm})$ . We now prove the following.
$in (L ab) \cap out (L {ab}_{adm}) = \emptyset$

This follows from the fact that $A {rgs}_{adm}$ does not attack $A rgs$ .

$out (L ab) \cap in (L {ab}_{adm}) = \emptyset$

This follows from the fact that for admissible sets the attack relation is symmetrical.7 7
That is, if $A {rgs}_{1}$ and $A {rgs}_{2}$ are admissible sets and $A {rgs}_{1}$ attacks $A {rgs}_{2}$ then $A {rgs}_{2}$ also attacks $A {rgs}_{1}$ .
So from the fact that $A {rgs}_{adm}$ does not attack $A rgs$ , it follows that $A rgs$ does not attack $A {rgs}_{adm}$ .
We now prove that $L ab$ is also the biggest admissible labelling that is compatible with each admissible labelling. Let $L {ab}^{'}$ be an admissible labelling that is compatible with each admissible labelling. Then $A {rgs}^{'} = in (L {ab}^{'})$ is an admissible set that is not attacked by any admissible set. So $A {rgs}^{'} \subseteq A rgs$ . It then follows that also $L {ab}^{'} ⊑ L ab$ . This can be seen as follows.
$in (L {ab}^{'}) \subseteq in (L ab)$

This is because $A {rgs}^{'} \subseteq A rgs$ and $in (L {ab}^{'}) = A {rgs}^{'}$ and $in (L ab) = A rgs$

$out (L {ab}^{'}) \subseteq out (L ab)$

Let $A \in out (L {ab}^{'})$ . Then there is an argument $B \in in (L {ab}^{'})$ that attacks A. From the fact that $in (L {ab}^{'}) \subseteq in (L ab)$ , it follows that $B \in in (L ab)$ . From the fact that $L ab$ is a complete labelling (see Caminada and Pigozzi 2009), it follows that $A \in out (L ab)$ .
So $L ab$ is the biggest admissible labelling that is compatible with each admissible labelling. From 2 to 1: Let $L ab$ be the biggest admissible labelling that is compatible with each admissible labelling. Let $L {ab}^{'}$ be the biggest admissible labelling that is smaller or equal to each preferred labelling. It then follows (“from 1 to 2”) that $L {ab}^{'}$ is also the biggest admissible labelling that is compatible with each admissible labelling. From the uniqueness of the biggest admissible labelling that is compatible with each admissible labelling (which is basically the biggest element of a partially ordered set) it then follows that $L {ab}^{'} = L ab$ . From 2 to 3: Let $L ab$ be the biggest admissible labelling that is compatible with each admissible labelling. From the fact that each complete labelling is also an admissible labelling, it follows that $L ab$ is also compatible with each complete labelling. We now prove that $L ab$ is also the biggest admissible labelling that is compatible with each complete labelling. Let $L {ab}^{'}$ be an arbitrary admissible labelling that is compatible with each complete labelling. We will now prove that $L {ab}^{'} ⊑ L ab$ . We do this by proving that $L {ab}^{'}$ is compatible with each admissible labelling. Let $L {ab}^{″}$ be an arbitrary admissible labelling. Let $L {ab}^{‴}$ be the up-complete labelling of $L {ab}^{″}$ , as defined in Caminada and Pigozzi (2009). It then holds that $L {ab}^{‴}$ is a complete labelling with $L {ab}^{″} ⊑ L {ab}^{‴}$ Caminada and Pigozzi (2009). From the fact that $L {ab}^{'}$ is compatible with each complete labelling it then follows that $L {ab}^{'}$ is compatible with $L {ab}^{‴}$ . From this, together with the fact that $L {ab}^{″} ⊑ L {ab}^{‴}$ , it follows that $L {ab}^{'}$ is compatible with $L {ab}^{″}$ . Since this holds for any arbitrary admissible labelling $L {ab}^{″}$ , it follows that $L {ab}^{'}$ is compatible with each admissible labelling. Since $L ab$ is the biggest admissible labelling that is compatible with each admissible labelling, it then follows that $L {ab}^{'} ⊑ L ab$ . From 3 to 2: This follows from “from 2 to 3” together with the uniqueness of 3. The proof is similar to the proof of “from 2 to 1”. From 3 to 4: Let $L ab$ be the biggest admissible labelling that is compatible with each complete labelling. From the fact that each preferred labelling is a complete labelling, it follows that $L ab$ is also compatible with each preferred labelling. We now prove that $L ab$ is also the biggest admissible labelling that is compatible with each preferred labelling. Let $L {ab}^{'}$ be an arbitrary admissible labelling that is compatible with each preferred labelling. We will now prove that $L {ab}^{'} ⊑ L ab$ . We do this by proving that $L {ab}^{'}$ is compatible with each complete labelling. Let $L {ab}^{″}$ be an arbitrary complete labelling. Let $L {ab}^{‴}$ be a preferred labelling such that $L {ab}^{″} ⊑ L {ab}^{‴}$ (the existence of such a $L {ab}^{‴}$ follows from the fact that for every complete extension E″ there exists a preferred extension E″′ with $E^{″} \subseteq E^{‴}$ (Dung 1995), which together with Lemma 2.9 implies that $Ext 2 Lab (E^{″}) ⊑ Ext 2 Lab (E^{‴})$ ). From this, together with the fact that $L {ab}^{'}$ is compatible with $L {ab}^{‴}$ (because $L {ab}^{'}$ is compatible with each preferred labelling) it follows that $L {ab}^{'}$ is compatible with $L {ab}^{″}$ . Since this holds for any arbitrary complete labelling $L {ab}^{″}$ , it follows that $L {ab}^{'}$ is compatible with each complete labelling. Since $L ab$ is the biggest admissible labelling that is compatible with each complete labelling, it then follows that $L {ab}^{'} ⊑ L ab$ . From 4 to 3: This follows from “from 3 to 4” together with the uniqueness of 4. The proof is similar to the proof of “from 2 to 1”. ▪

We will now treat the notion of ideal semantics as described in Dung et al. (2007).8 8
We use the term ideal extension to refer to the biggest ideal set.

Definition 3.5
Let $AF = (Ar, att)$ be an argumentation framework. An admissible set $A rgs$ is called ideal iff it is a subset of each preferred extension. The ideal extension is a maximal (w.r.t. set-inclusion) ideal set.

It turns out that the ideal extension is unique (which implies that it is also the biggest ideal set) and that it is also a complete extension (Dung et al. 2007).

There are several ways of describing the ideal extension.
Proposition 3.6
Let $AF = (Ar, att)$ be an argumentation framework, and let $A rgs \subseteq Ar$ . The following statements are equivalent.
$A rgs$ is the biggest admissible set that is a subset of each preferred extension (that is, $A rgs$ is the ideal extension)

$A rgs$ is the biggest admissible set that is not attacked by any admissible set

$A rgs$ is the biggest admissible set that is not attacked by any complete extension

$A rgs$ is the biggest admissible set that is not attacked by any preferred extension

In Proposition 3.6, the equivalence between points 1 and 2 follows from (Dung et al. 2007, Theorem 3.3). The equivalence between points 2, 3 and 4 follows from the fact that an argument (or set) is attacked by an admissible set iff it is attacked by a complete extension iff it is attacked by a preferred extension.

It turns out that the ideal labelling corresponds to the ideal extension.9 9
Point 2 (but not point 1) of Theorem 3.7 has been proved in Caminada and Pigozzi (2009)

Theorem 3.7
Let $AF = (Ar, att)$ be an argumentation framework. It holds that
if $A rgs$ is the ideal extension of AF, then $Ext 2 Lab (A rgs)$ is the ideal labelling of AF, and

if $L ab$ is the ideal labelling of AF, then $Lab 2 Ext (L ab)$ is the ideal extension of AF.

Proof

Let $A rgs$ be the ideal extension of AF. From Proposition 3.6 it follows that $A rgs$ is the biggest admissible set that is not attacked by any complete extension. Since the ideal extension is also a complete extension, it follows that $A rgs$ is the biggest complete extension that is not attacked by any complete extension. Since attacks among admissible sets are symmetric (and therefore attacks among complete extensions are also symmetric), it follows that $A rgs$ is also the biggest complete extension that does not attack any complete extension. It then follows that $Ext 2 Lab (A rgs)$ is the biggest complete labelling that is compatible with each complete labelling. It then follows that $Ext 2 Lab (A rgs)$ is also the biggest admissible labelling that is compatible with any complete labelling (this follows from point 3 of Theorem 3.4, together with the uniqueness of the ideal labelling and the fact that the ideal labelling is a complete labelling). Therefore, $Ext 2 Lab (A rgs)$ is the ideal labelling.

Let $L ab$ be the ideal labelling of AF. From the fact that the ideal labelling is a complete labelling, together with the one-to-one relationship between complete labellings and complete extensions, it follows that $Ext 2 Lab (Lab 2 Ext (L ab)) = L ab$ . Let $A rgs = Lab 2 Ext (L ab)$ . From the fact that $Ext 2 Lab (A rgs) = L ab$ , together with the fact that the ideal extension is unique, it follows (from point 1) that $A rgs$ is the ideal extension.
▪

Since for complete semantics, the relation between labellings and extensions is one-to-one, it follows that for ideal semantics the relation is one-to-one as well (this is because the ideal extension/labelling is also a complete extension/labelling).
4. Stage semantics

The concept of stage semantics goes back to the work of Verheij (1996). In essence, a stage extension can be described as a conflict-free set of arguments $A rgs$ , where $A rgs \cup A {rgs}^{+}$ is maximal w.r.t. set-inclusion.10

10
Recall that $A {rgs}^{+}$ stands for the set of arguments attacked by $A rgs$ .

In order to describe a stage extension in terms of labellings, we first introduce the concept of a conflict-free labelling
Definition 4.1
Let $L ab$ be a labelling of argumentation framework $AF = (Ar, att)$ . $L ab$ is {\rm conflict-free} iff for each $A \in Ar$ it holds that:

if A is labelled in then it does not have an attacker that is labelled in

if A is labelled out then it has at least one attacker that is labelled in

When comparing a conflict-free labelling with an admissible labelling, it can be noticed that the condition on out labelled arguments (point 2) is essentially the same. However, the condition for in-labelled arguments (point 1) is weaker for conflict-free labellings than for admissible labellings. It then follows that every admissible labelling is also a conflict-free labelling (just like every admissible set is also a conflict-free set by definition).

The idea of a stage labelling can then be described as a conflict-free labelling where $undec$ is minimal.
Definition 4.2
Let $AF = (Ar, att)$ be an argumentation framework. A labelling $L ab$ is called a {\rm stage labelling} iff it is a conflict-free labelling where $undec (L ab)$ is minimal (w.r.t. set-inclusion) among all conflict-free labellings.

It holds that every stable labelling is also a stage labelling.11 11
A similar observation was made in Verheij (1996).

Theorem 4.3
Let $L ab$ be a labelling of argumentation framework $AF = (Ar, att)$ . If $L ab$ is a stable labelling of AF then $L ab$ is also a stage labelling of AF.
Proof
Let $L ab$ be a stable labelling of AF. Then $L ab$ is a complete labelling with $undec (L ab) = \emptyset$ . From the fact that $L ab$ is a complete labelling (points 1 and 2 from Proposition 2.8), it follows (Definition 4.2) that $L ab$ is a conflict-free labelling (points 1 and 2 from Definition 4.1). Since $undec (L ab) = \emptyset$ , it directly follows that $undec (L ab)$ is minimal among all conflict-free labellings. Hence, $L ab$ is a stage labelling. ▪

If there exists at least one stable labelling, then each stage labelling is also a stable labelling.12 12
A similar observation, in the context of DefLog, was made in Verheij (2003, page 337).

Theorem 4.4
Let $AF = (Ar, att)$ be an argumentation framework. If there exists at least one stable labelling of AF, then every stage labelling is also a stable labelling.
Proof
Let $L ab$ be a stable labelling of AF. Then from Theorem 4.3, it follows that $L ab$ is also a stage labelling. In particular, $L ab$ is a stage labelling with $undec (L ab) = \emptyset$ . Now, let $L {ab}^{'}$ be an arbitrary stage labelling of AF. It then follows that $undec (L {ab}^{'})$ is minimal among all conflict-free labellings. Since $L ab$ is a conflict-free labelling with $undec (L ab) = \emptyset$ it follows that $undec (L {ab}^{'})$ must also be ∅. So $L {ab}^{'}$ is a conflict-free labelling with $undec (L {ab}^{'}) = \emptyset$ . In order to show that $L {ab}^{'}$ is a stable labelling, we first show that it is a complete labelling, hence that the three points of Definition 2.7 are satisfied:
“if A is labelled in then all attackers of A are labelled out”

This follows from point 1 of Definition 4.1, together with the fact that $undec (L ab) = \emptyset$ (therefore from the fact that A does not have any defeaters that are labelled in it follows that all defeaters of A are labelled out).

“if A is labelled out then all attackers of A are labelled in”

This follows from point 2 of Definition 4.1.

“if A is labelled $undec$ then not all attackers of A are labelled out and A does not have an attacker that is labelled in”

This is trivially satisfied, since $undec (L {ab}^{'}) = \emptyset$ .
So $L {ab}^{'}$ is a complete labelling with $undec (L {ab}^{'}) = \emptyset$ . Hence (Definition 2.11) $L {ab}^{'}$ is a stable labelling ▪

There also exists an alternative way to describe the concept of a stage labelling. In essence, what a stage labelling does is to take a maximal subgraph of the argumentation framework that has a stable labelling. A stage labelling is then a stable labelling of such a maximal subgraph, augmented with $undec$ labels for the arguments that did not make their way into the subgraph.

In the following lemma, $AF |_{A rgs}$ stands for $(Ar \cap A rgs, att \cap (A rgs \times A rgs))$ (assuming that $AF = (Ar, att)$ ) and $L ab |_{A rgs}$ stands for $L ab \cap (A rgs \times {in, out, undec})$ .
Lemma 4.5
Let $L ab$ be a labelling of argumentation framework $AF = (Ar, att)$ . The following two statements are equivalent.

$L ab$ is a conflict-free labelling.

$L ab |_{A rgs}$ is a stable labelling of $AF |_{A rgs}$ , where $A rgs = in (L ab) \cup out (L ab)$ .

Proof
From 1 to 2: Let $L ab$ be a conflict-free labelling. We now prove that $L ab |_{A rgs}$ is a stable labelling of $AF |_{A rgs}$ . We do this by proving that $L ab |_{A rgs}$ fulfils the three conditions of a complete labelling (Definition 2.7).
“If A is labelled in then all attackers of A are labelled out”

This follows from point 1 of Definition 4.1, together with the fact that $undec (L ab |_{A rgs}) = \emptyset$ .

“if A is labelled out then A has an attacker that is labelled in”

This follows from point 2 of Definition 4.1.

“if A is labelled $undec$ then not all attackers of A are labelled out and A does not have an attacker that is labelled in”

This is trivially satisfied since $undec (L ab |_{A rgs}) = \emptyset$ .
From the validity of point 1, 2 and 3 it follows that $L ab |_{A rgs}$ is a complete labelling of $AF |_{A rgs}$ . From the fact that $undec (L ab |_{A rgs}) = \emptyset$ it follows that $L ab |_{A rgs}$ is also a stable labelling of $AF |_{A rgs}$ . From 2 to 1:

Let $L ab$ be a labelling of AF such that $L ab |_{A rgs}$ is a stable labelling of $AF |_{A rgs}$ . We now prove that $L ab$ is a conflict-free labelling of AF. According to Definition 4.1 we need to prove two things:
“if A is labelled in then it does not have an attacker that is labelled in”

Let B be an arbitrary attacker of A in AF. We distinguish two cases:
$B \in A rgs$ . Then B also attacks A in $AF |_{A rgs}$ . From the fact that $L ab |_{A rgs}$ is a stable labelling (and therefore also a complete labelling) of $AF |_{A rgs}$ it follows that B is labelled out by $L ab |_{A rgs}$ , and therefore that B is labelled out by $L ab$ .

$B \notin A rgs$ . Then $B \notin in (L ab) \cup out (L ab)$ so $B \in undec (L ab)$ .
In both cases, B is not labelled in by $L ab$ . Therefore A does not have an attacker in AF that is labelled in by $L ab$ .

“If A is labelled out then it has at least one attacker that is labelled in”

Let A be an argument that is labelled out by $L ab$ . Then $A \in A rgs$ , so the fact that $L ab |_{A rgs}$ is a stable (and therefore also complete) labelling of $AF |_{A rgs}$ implies that there exists an argument B labelled in by $L ab |_{A rgs}$ that attacks A in $AF |_{A rgs}$ , so B is also labelled in by $L ab$ and also attacks A in AF.
▪
Theorem 4.6
Let $L ab$ be a labelling of argumentation framework $AF = (Ar, att)$ . The following two statements are equivalent.

$L ab$ is a conflict-free labelling where $undec (L ab)$ is minimal (w.r.t. set inclusion) among all conflict-free labellings (that is, $L ab$ is a stage labelling)

$A rgs = in (L ab) \cup out (L ab)$ is a maximal subset of Ar such that $AF |_{A rgs}$ has a stable labelling, and $L ab |_{A rgs}$ is a stable labelling of $AF |_{A rgs}$ .

Proof
From 1 to 2: Let $L ab$ be a conflict-free labelling where $undec (L ab)$ is minimal. From Lemma 4.5 it follows that $L ab |_{A rgs}$ is a stable labelling of $AF |_{A rgs}$ . We now prove that $A rgs$ is a maximal subset of Ar such that $AF |_{A rgs}$ has a stable labelling. Suppose $A {rgs}^{'} ⫌ A rgs$ is a subset of Ar such that $AF |_{A {rgs}^{'}}$ has a stable labelling (say $L {ab}^{'}$ ). Let $L {ab}^{″} = L ab \cup {(A, undec) ∣ A \in Ar ∖ A {rgs}^{'}}$ . It holds that $L {ab}^{'} = L {ab}^{″} |_{A {rgs}^{'}}$ . From Lemma 4.5 it follows that $L {ab}^{″}$ is a conflict-free labelling of AF. Moreover, it holds that $undec (L {ab}^{″}) ⫋ undec (L ab)$ ; so $undec (L ab)$ is not minimal. Contradiction. From 2 to 1: Let $A rgs = in (L ab) \cup out (L ab)$ be a maximal subset of Ar such that $AF |_{A rgs}$ has a stable labelling, and that $L ab |_{A rgs}$ is a stable labelling of $AF |_{A rgs}$ . From Lemma 4.5, it follows that $L ab$ is a conflict-free labelling of AF. We now prove that $undec (L ab)$ is minimal. Let $L {ab}^{'}$ be a conflict-free labelling of AF with $undec (L {ab}^{'}) ⫋ undec (L ab)$ and let $A {rgs}^{'} = in (L {ab}^{'}) \cup out (L {ab}^{'})$ . Then, according to Lemma 4.5, it follows that $L {ab}^{'} |_{A {rgs}^{'}}$ is a stable labelling of $AF |_{A rgs}$ . However, since $A {rgs}^{'} ⫌ A rgs$ , it follows that $A rgs$ is not a maximal subset of Ar such that $AF |_{A rgs}$ has a stable labelling. Contradiction. ▪

As was mentioned at the beginning of the current section, stage semantics can also be expressed using the traditional approach of argument extensions.
Definition 4.7
Let $AF = (Ar, att)$ be an argumentation framework. A stage extension is a conflict-free set $A rgs \subseteq Atr$ where $A rgs \cup A {rgs}^{+}$ is maximal (w.r.t. set inclusion) among all conflict-free sets.
Lemma 4.8
Let $AF = (Ar, att)$ be an argumentation framework and $A rgs \subseteq Ar$ . The following two statements are equivalent:

$A rgs$ is a conflict-free set of AF

$A rgs$ is a stable extension of $AF |_{A rgs \cup A {rgs}^{+}}$

Proof
Similar to Lemma 4.5. ▪
Theorem 4.9
Let $AF = (Ar, att)$ be an argumentation framework and $A rgs \subseteq Ar$ . The following two statements are equivalent.

$A rgs$ is a conflict-free set where $A rgs \cup A {rgs}^{+}$ is maximal (w.r.t. set inclusion) among all conflict-free sets (that is, $A rgs$ is a stage extension).

$A rgs \cup A {rgs}^{+}$ is a maximal subset of Ar such that $AF |_{A rgs \cup A {rgs}^{+}}$ has a stable extension, and $A rgs$ is a stable extension of $AF |_{A rgs \cup A {rgs}^{+}}$ .

Proof
Similar to the proof of Theorem 4.6. ▪

Before discussing the connection between stage labellings and stage extensions, we first state the connection between conflict-free labellings and conflict-free sets.
Proposition 4.10
Let $AF = (Ar, att)$ be an argumentation framework. It holds that

if $A rgs$ is a conflict-free set of AF, then $Ext 2 Lab (A rgs)$ is a conflict-free labelling of AF

if $L ab$ is a conflict-free labelling of AF, then $Lab 2 Ext (L ab)$ is a conflict-free set of AF

The relation between conflict-free sets and conflict-free labellings is not one-to-one, however. There can be several conflict-free labellings which are associated with the same conflict-free set.13 13
An example would be an argumentation framework $({A, B}, {(A, B)})$ with $L {ab}_{1} = ({A}, {B}, \emptyset)$ and $L {ab}_{2} = ({A}, \emptyset, {B})$ .

Theorem 4.11
Let $AF = (Ar, att)$ be an argumentation framework. It holds that

if $A rgs$ is a stage extension of AF, then $Ext 2 Lab (A rgs)$ is a stage labelling of AF

if $L ab$ is a stage labelling of AF, then $Lab 2 Ext (L ab)$ is a stage extension of AF

Proof
This follows from Proposition 4.10. ▪

Stage extensions and stage labellings stand in a one-to-one relation to each other. That is, when restricted to stage extensions and stage labellings, the functions $Ext 2 Lab$ and $Lab 2 Ext$ become bijections and each other's inverse.
Theorem 4.12
Let $AF = (Ar, att)$ be an argumentation framework, se its set of stage extensions and sl its set of stage labellings. Let ${Ext 2 Lab}^{s} : se \to sl$ be a function such that ${Ext 2 Lab}^{s} (A rgs) = Ext 2 Lab (A rgs)$ (that is, ${Ext 2 Lab}^{s}$ is the function $Ext 2 Lab$ where the domain/range is restricted to stage extensions/labellings) and ${Lab 2 Ext}^{s} : sl \to se$ be a function such that ${Lab 2 Ext}^{s} (L ab) = Lab 2 Ext (L ab)$ (that is, ${Lab 2 Ext}^{s}$ is the function $Lab 2 Ext$ where the domain/range is restricted to stage labellings/extensions). The functions ${Ext 2 Lab}^{s}$ and ${Lab 2 Ext}^{s}$ are bijective and each other's inverse.
Proof
As every function that has an inverse is bijective, we only need to prove that ${Lab 2 Ext}^{s}$ and ${Ext 2 Lab}^{s}$ are each other's inverses. That is ${({Lab 2 Ext}^{s})}^{- 1} = {Ext 2 Lab}^{s}$ and ${({Ext 2 Lab}^{s})}^{- 1} = {Lab 2 Ext}^{s}$ . For this, we prove the following two things:
“For every stage labelling $L ab$ it holds that ${Ext 2 Lab}^{s} ({Lab 2 Ext}^{s} (L ab)) = L ab$ .”

Let $L ab$ be a stage labelling of AF. Let $A rgs = in (L ab) \cup out (L ab)$ . Then according to Theorem 4.6 $L ab |_{A rgs}$ is a stable labelling of $AF |_{A rgs}$ and since stable labellings and stable extensions are one-to-one related (this follows from the fact that complete labellings and complete extensions are one-to-one related, as proved in Caminada and Gabbay 2009) it follows that $Ext 2 Lab (Lab 2 Ext (L ab |_{A rgs})) = L ab |_{A rgs}$ . It then follows that for every $A \in Ar$ :

${Ext 2 Lab}^{s} ({Lab 2 Ext}^{s} (L ab)) (A) = in$ iff $L ab (A) = in$

${Ext 2 Lab}^{s} ({Lab 2 Ext}^{s} (L ab)) (A) = out$ iff $L ab (A) = out$

It then directly follows that: ${Ext 2 Lab}^{s} ({Lab 2 Ext}^{s} (L ab)) (A) = undec$ iff $L ab (A) = undec$

So ${Ext 2 Lab}^{s} ({Lab 2 Ext}^{s} (L ab)) = L ab$ .

“For every stage extension E it holds that ${Lab 2 Ext}^{s} ({Ext 2 Lab}^{s} (E)) = E$ ”.

Let E be a stage extension of AF. We now prove two things:
${Lab 2 Ext}^{s} ({Ext 2 Lab}^{s} (E)) \subseteq E$

Let $A \in {Lab 2 Ext}^{s} ({Ext 2 Lab}^{s} (E)) \subseteq E$ . Then A is labelled in by ${Ext 2 Lab}^{s} (E)$ . Therefore A∈E.

$E \subseteq {Lab 2 Ext}^{s} ({Ext 2 Lab}^{s} (E))$

Let A∈E. Then A is labelled in by ${Ext 2 Lab}^{s} (E)$ . Therefore $A \in {Lab 2 Ext}^{s} ({Ext 2 Lab}^{s} (E))$ .

▪

In order to understand the difference between stage semantics and the admissibility based semantics, it is useful to make an analogy with classical logic. In the presence of a potentially inconsistent knowledge base one could do two things:
Take the maximal consistent subsets of the knowledge base, and examine what is entailed by all of these. That is, take the (classical) models of the maximal subsets of the knowledge base that have classical models.

Define a new semantics such that the entire knowledge base will have models. This is the approach that is, for instance, taken in the field of paraconsistent logic (Arieli and Avron 1998; Carnielli Coniglio, and Marcos 2002).

Solution 1 (applying the original semantics to maximal subsets of the original problem description) is comparable to stage semantics, whereas solution 2 (redefining the semantics so that it can meaningfully be applied to a bigger class of knowledge bases) is comparable to the admissibility based semantics.
4.1 Stage semantics versus semi-stable semantics

The concept of stage semantics is similar to that of semi-stable semantics, as both of these semantics aim to maximise the range ( $A rgs \cup A {rgs}^{+}$ ) of their extensions.14

14
Or, alternatively, they try to minimise the set of $undec$ -labelled arguments of their labellings.
However, where semi-stable semantics aims to maximise the range under the condition of admissibility, stage semantics tries to maximise the range under the weaker condition of conflict-freeness. It turns out that the approach of stage semantics is equivalent to taking the stable extensions (labellings) of the biggest subframework that has at least one stable extension (labelling). Hence, the approach of stage semantics is comparable to the approach of handling inconsistent knowledge bases, where one can select maximal consistent subsets of the knowledge base, and then examine what holds in all of them (in the union of all their models). That is, it is as if stage semantics interprets the absence of stable extensions as some form of “inconsistency”, which needs to be handled taking the “maximal consistent subframeworks”.

In semi-stable semantics, on the other hand, one still takes all the arguments of the argumentation framework into account. That is, one does not ignore any information provided by the argumentation framework. An example is shown in Figure 1. Here, semi-stable semantics yields a single extension ∅, corresponding with a labelling $(\emptyset, \emptyset, {A, B})$ , whereas stage semantics yields a single extension {B}, corresponding with a labelling $({B}, \emptyset, {A})$ . In essence, what stage semantics does is to ignore argument A, since this argument causes the framework not to have any stable extensions.

Figure 1.
Stage semantics differs from semi-stable semantics.

Another example to illustrate the difference between stage semantics and semi-stable semantics is given in Figure 2. Here, semi-stable semantics yields a single extension {A}, corresponding to a labelling $({A}, {B}, {C})$ . Stage semantics yields two extensions, the first one being equivalent to the one yielded by semi-stable semantics, the second one being {B}, corresponding to a labelling $({B}, {C}, {A})$ . The first stage extension (labelling) is the result of ignoring argument C, the second stage extension (labelling) is the result of ignoring argument A. For both possibilities, the remaining argumentation framework is a maximal one that has at least one stable extension (labelling). It can therefore be observed that under stage semantics, even an argument without any attackers (like argument A in Figure 2) is not always labelled in.15 15
We would like to thank Pietro Baroni and Massimiliano Giacomin for this observation.
With semi-stable semantics, however, an argument without any attackers is always labelled in.

Figure 2.
Stage semantics does not always endorse non-attacked arguments.

Although examples like illustrated by Figure 2 pose a serious problem for stage semantics, the situation is not hopeless. A positive aspect is that each argumentation framework has at least one stage labelling that is at least as committed (“bigger or equal”) as the grounded labelling. It then directly follows that each argumentation framework has at least one stage labelling that labels each argument without any attackers in. In order to prove this, we need the following lemma. In this lemma, as well as in the subsequent theorem, the range of a labelling stands for its set of in-labelled or out-labelled arguments (that is, $range (L ab) = in (L ab) \cup out (L ab)$ ).
Lemma 4.13
Let AF be an argumentation framework with grounded labelling 𝒢 such that $undec (G) = \emptyset$ . Let 𝒞 be an arbitrary conflict-free labelling of AF. It holds that if $range (G) \subseteq range (C)$ then $C = G$ .
Proof
From the fact that $range (G) \subseteq range (C)$ , together with the fact that $undec (G) = \emptyset$ , it follows that $range (G) = range (C)$ . So $undec (C) = \emptyset$ , so 𝒞 is a stable labelling. The grounded labelling is less or equally committed than every complete labelling (and is therefore also less or equally committed than every stable labelling). That is, $G ⊑ C$ . Since $undec (G) = \emptyset$ it then follows that $G = C$ . ▪
Theorem 4.14
Let $AF = (Ar, att)$ be an argumentation framework and 𝒢 be its grounded labelling. There exists at least one stage labelling 𝒮 such that $G ⊑ S$ .
Proof
Let $C_{\max}$ be an element of ${C ∣ C$ is a conflict-free labelling of AF and $G ⊑ C}$ with a maximal range within this set. Since the set is finite (because AF is finite) and non-empty (because it contains at least 𝒢) such an element with maximal range ( $C_{\max}$ ) does exist. Now suppose that $C_{\max}$ is not a stage labelling. Then there exists a conflict-free labelling $D_{\max}$ of AF such that $range (C_{\max}) ⊊ range (D_{\max})$ . Let ${AF}^{'} = AF |_{range (G)}$ , $G^{'} = G |_{range (G)}$ , $C_{\max}^{'} = C_{\max} |_{range (G)}$ , and $D_{\max}^{'} = D_{\max} |_{range (G)}$ . From the fact that $G ⊑ C_{\max}$ it follows that $G^{'} = C_{\max}^{'}$ . Also, from $range (C_{\max}) ⊊ range (D_{\max})$ it follows that $range (C_{\max}^{'}) \subseteq range (D_{\max}^{'})$ . Furthermore, it holds that $range (G^{'}) \subseteq range (C_{\max}^{'})$ (since $G^{'} = C_{\max}^{'}$ ), so by transitivity we obtain $range (G^{'}) = range (D_{\max}^{'})$ . From Lemma 4.13 it then follows that $G^{'} = D_{\max}^{'}$ , from which it follows that $G ⊑ D_{\max}$ . So $D_{\max}$ is an element of ${C ∣ C$ is a conflict-free labelling of AF and $G ⊑ C}$ . But since $range (C_{\max}) ⊊ range (D_{\max})$ it then follows that $C_{\max}$ does not have a maximal range among the elements of this set. Contradiction. ▪

Hence, a possible way of dealing with problems such as the one illustrated in Figure 2 is simply to delete all stage labellings that do not label all arguments without attackers in. Theorem 4.14 guarantees that after doing so, there will be at least one stage labelling left.
4.2 Verheij's original formalisation of stage semantics

In Verheij (1996), stage semantics was originally introduced not in terms of traditional argument extensions, nor in terms of labellings in the sense of Definition 2.4. Instead, it was introduced using what we will refer to as argumentation tuples, which in essence is a type of labelling in which $undec$ is not explicitly represented. In the current section we treat the overlap between our formalisation and Verheij's original work.

We first state (Verheij 1996, Definition 3), although we have slightly changed the terminology in order to be compatible with what is nowadays commonly used in the field of formal argumentation.

Definition 4.15 Verheij 1996, Definition 3

An argumentation tuple $(IN, OUT)$ is a pair of disjoint sets of arguments. The union of in and out is called the range of the argumentation tuple.

A stage tuple is an argumentation tuple $(IN, OUT)$ such that for each argument $A \in IN \cup OUT$ it holds that:

$A \in OUT$ iff there exists an argument $A^{'} \in IN$ that attacks A

A stage tuple extension is a stage tuple $(IN, OUT)$ such that there is no stage tuple with a larger range.

There exists a one-to-one relationship between the notion of stage tuples (Definition 4.15) and the notion of a conflict-free labellings (Definition 4.1).

Theorem 4.16
Let $(Ar, att)$ be an argumentation framework. It holds that $(IN, OUT)$ is a stage tuple iff $(IN, OUT, Ar ∖ (IN \cup OUT))$ is a conflict-free labelling.
Proof
“⇒”: Let $(IN, OUT)$ be a stage tuple. We now prove the following.
“If $A \in IN$ then it does not have an attacker B such that $B \in IN$ .”

Let B be an attacker of A. Then according to point 2 of Definition 4.15, $B \in OUT$ . Since in and out are disjoint, it follows that $B \notin IN$ .

“If $A \in OUT$ then it has at least one attacker B such that $B \in IN$ .”

This follows directly from point 2 of Definition 4.15.
“⇐”: Let $(IN, OUT, Ar ∖ (IN \cup OUT))$ be a conflict-free labelling. That is, for each argument $A \in Ar$ it holds that:
If $A \in IN$ then it does not have an attacker B such that $B \in IN$ .

If $A \in OUT$ then it has at least one attacker B such that $B \in IN$ .
We first observe that in and out are disjoint (if $A \in IN$ and $A \in OUT$ then from 1 and 2 a contradiction follows) thus satisfying point 2 of Definition 4.15. Moreover, for each $A \in IN \cup OUT$ it holds that
if $A \in OUT$ then there exists an $A^{'} \in IN$ that attacks A (follows directly from 2)

if $A \notin OUT$ then there does not exist an $A^{'} \in IN$ that attacks A (follows from 1, together with the fact that $A \in IN$ when $A \in IN \cup OUT$ and $A \notin OUT$ )
From these two implications, point 2 of Definition 4.15 follows. ▪

Similarly, there exists a one-to-one correspondence between the notion of stage tuple extensions (Definition 4.15) and the notion of stage labellings (Definition 4.2).
Theorem 4.17
Let $(Ar, att)$ be an argumentation framework. It holds that $(IN, OUT)$ is a stage tuple iff $(IN, OUT, Ar ∖ (IN \cup OUT))$ is a stage labelling.
Proof
“⇒”: Let $(IN, OUT)$ be a stage extension. It then follows that $(IN, OUT, Ar ∖ (IN \cup OUT))$ is a conflict-free labelling (Theorem 4.16). The fact that $(IN, OUT, Ar ∖ (IN \cup OUT))$ is also a stage labelling (that is, a conflict-free labelling with minimal $Ar ∖ (IN \cup OUT)$ ) follows from the fact that $IN \cup OUT$ is maximal (from the fact that $(IN, OUT$ is a stage tuple extension, it follows that it has a maximal range). “⇐”: Let $(IN, OUT, Ar ∖ (IN \cup OUT))$ be a stage labelling. It then follows that $(IN, OUT)$ is a stage tuple (Theorem 4.16). The fact that $(IN, OUT)$ is a stage tuple extension (that is, a stage tuple with maximal range $IN \cup OUT$ ) then follows from the fact that $Ar ∖ (IN \cup OUT)$ is minimal (since $(IN, OUT, Ar ∖ (IN \cup OUT))$ is a stage labelling). ▪

Since stage extensions, stage labellings and stage tuple extensions express essentially the same concept (though in different manifestations), we can use either form without loosing essential information.

Although Verheij shows that, given a stage tuple $(IN, OUT)$ the set in is an admissible set (and even a stable extension) of the argumentation framework restricted to $IN \cup OUT$ (Verheij 1996, Theorem 3) he does not go all the way and state that a stage tuple extension is essentially about taking a maximal subframework that has at least one stable extension (labelling), as we have stated in Theorem 4.9 and Theorem 4.6.

The concept of semi-stable semantics corresponds with what Verheij calls “admissible stage extensions”.16 16
Verheij also expresses the notions of preferred and stable semantics, as well as the notion of admissibility, in terms of argumentation tuples.
It was 10 years later that Caminada (initially unaware of this correspondence) reinvented the concept under the name of “semi-stable semantics”, and proved various of its properties, such as the fact that every semi-stable extension is also a complete extension, the fact that semi-stable semantics satisfies the postulate of relevance, and a number of conditions under which an argument is credulously or sceptically endorsed under semi-stable semantics.
5. Roundup

In the current work, we have extended the results of Caminada (2006a), and Caminada and Gabbay (2009) by showing that the labelling approach is applicable to two additional semantics from the existing argumentation literature: ideal semantics and stage semantics. Moreover, there turns out to be a one-to-one correspondence between the extensions and labellings of these two semantics.

Ideal semantics can be described in terms of judgment aggregation. In Caminada and Pigozzi (2009), it was shown that the ideal labelling is the result of the sceptical judgment aggregation procedure based on all preferred labellings, or alternatively, the result of the credulous or super-credulous judgment aggregation procedure on all admissible, complete or preferred labellings. In the current paper, we go one step further and show that this result is also the biggest (w.r.t. “⊑”) admissible and complete labelling that is compatible with all admissible, complete or preferred labellings.

As for stage semantics, it was found that this semantics takes the stable labellings/extensions of the maximal subframework(s) that have at least one stable labelling/extension. Here, we again see that the properties of a semantics (in this case stage semantics) can be expressed both in terms of extensions and in terms of labellings.

Although the labellings approach and the extensions approach are equivalent (after all, an extension is basically the in-labelled part of a labelling) the labellings approach offers several advantages. First of all, the labellings approach can offer some technical advantages. For instance, the algorithm for stage semantics (Caminada 2010) has been stated in terms of labellings, and would be very difficult to rewrite using only the traditional extensions approach. A similar observation holds for the algorithm for semi-stable semantics (Caminada 2006a; Modgil and Caminada 2009). What makes labellings suitable for constructing these algorithms is the fact that labellings can be defined in terms of relatively small and modular properties that hold independently from each other. The algorithms then uses the fine-grainedness of these properties to work to satisfy all of them in an incremental way.

The second and in our view even most important advantage of the labellings approach is that it tends to make formal argumentation more easy to understand, even for non-experts. For instance, for complete semantics (Proposition 2.8) the essential rule is that an argument has to be accepted iff all its attackers are rejected, and an argument has to be rejected iff it has at least one attacker that is accepted. Thus, argumentation can be explained without referring to things like admissibility or fixpoints of Dung's characteristic function. In a gunfight, one stays alive iff all attackers are dead, and one dies iff at least one attacker is still alive. Those who can understand this have basically understood what complete semantics is all about. This understanding can then also be used to explain the basic intuitions behind other semantics, like preferred, grounded, stable and semi-stable (see Table 1). As for ideal semantics, the labellings approach allows it to be described (Proposition Theorem 3.4) as the most committed reasonable (admissible/complete) position one can take that is still compatible with each reasonable (admissible/complete) position. As for stage semantics, the labellings approach also provides an intuitive description (Theorem 4.6): one wants to have a black-and-white (in or out) view of the world, in which there is no room for shades of grey ( $undec$ ), even if one has to ignore part of the available information to achieve this (that is, one wants to have a stable labelling of a maximal part of the argumentation framework).

Overall, by treating two additional semantics (stage and ideal) in terms of labellings, we hope to have contributed to promoting labellings as a general way to characterise argumentation semantics, that has advantages of both technical and conceptual nature.

Footnotes

Acknowledgements

We would like to thank Yining Wu for helping to develop the concept of an ideal labelling.

References

Amgoud, L., Maudet, N. and Parsons, S. 2000. Modelling Dialogues Using Argumentation’. 2000, Boston. Proceedings of the Fourth International Conference on MultiAgent Systems (ICMAS-00, pp. 31–38. MA

Amgoud, L., Bodenstaff, L., Caminada, M.W.A., McBurney, P., Parsons, S., Prakken, H., van Veenen, J. and Vreeswijk, G. A.W. 2006. Final review and report on formal argumentation system , Deliverable D2.6, ASPIC IST-FP6-002307

Arieli, O. and Avron, A. 1998. The Value of the Four Values. Artificial Intelligence , 102: 97–141.

Caminada, M.W.A.

2006a. On the Issue of Reinstatement in Argumentation’. (2006a). Logics in Artificial Intelligence; 10th European Conference, JELIA 2006, Edited by: Fischer, M., van der Hoek, W., Konev, B. and Lisitsa, A. pp. 111–123. Springer. LNAI 4160

Caminada, M. W.A.

2006b. “On the Issue of Reinstatement in Argumentation”. Institute of Information and Computing Sciences, Utrecht University. Technical Report UU-CS-2006-023

Caminada, M. W.A.

Semi-Stable Semantics’. Computational Models of Argument; Proceedings of COMMA 2006, Edited by: Dunne, P. E. and Bench-Capon, T. J.M. pp. 121–130. IOS Press.

Caminada, M. W.A. (2007). An Algorithm for Computing Semi-Stable Semantics’. (2007). Proceedings of the 9th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU 2007, pp. 222–234. Berlin: Springer Verlag. no. 4724 in Springer Lecture Notes in AI

Caminada, M. W.A. (2010). An Algorithm for Stage Semantics’. (2010), Amsterdam, The Netherlands, in print. Computational Models of Argument; Proceedings of COMMA 2010, Edited by: Baroni, P., Cerutti, F., Giacomin, M. and Simari, G. R. IOS Press.

Caminada, M. W.A. and Amgoud, L. 2007. On the Evaluation of Argumentation Formalisms. Artificial Intelligence , 171(5–6): 286–310.

10.

Caminada, M. W.A. and Gabbay, D. M. 2009. A Logical Account of Formal Argumentation. Studia Logica , 93(2–3): 109–145. (Special issue: new ideas in argumentation theory)

11.

Caminada, M. W.A. and Pigozzi, G. 2009. On Judgment Aggregation in Abstract Argumentation. Journal of Autonomous Agents and Multi-Agent Systems , in press, DOI 10.1007/s10458-009-9116-7

12.

Carnielli, W., Coniglio, M. E. and Marcos, J. 2002. “‘Logics of Formal Inconsistency’”. In Handbook of Philosophical Logic , 2, Edited by: Gabbay, D. M. and Guenthner, F. Vol. 14, 15–114. Springer Verlag.

13.

Dung, P. M.

1995. On the Acceptability of Arguments and Its Fundamental Role in Nonmonotonic Reasoning, Logic Programming and n-Person Games. Artificial Intelligence , 77: 321–357.

14.

Dung, P. M., Mancarella, P. and Toni, F. 2007. Computing Ideal Sceptical Argumentation. Artificial Intelligence , 171: 642–674.

15.

Jakobovits, H. and Vermeir, D. 1999. Robust Semantics for Argumentation Frameworks. Journal of logic and computation , 9(2): 215–261.

16.

Modgil, S. and Caminada, M. W.A. 2009. “‘Proof Theories and Algorithms for Abstract Argumentation Frameworks’”. In Argumentation in Artificial Intelligence , Edited by: Rahwan, I. and Simari, G. R. 105–129. Springer.

17.

Pollock, J. L.

1995. Cognitive Carpentry. A Blueprint for How to Build a Person , Cambridge, MA: MIT Press.

18.

Prakken, H. and Sartor, G. 1997. Argument-based Extended Logic Programming with Defeasible Priorities. Journal of Applied Non-Classical Logics , 7: 25–75.

19.

Rahwan, I. and Tohmé, F. Collective Argument Evaluation as Judgement Aggregation’. Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2010),

20.

Rahwan, I., Zablith, F. and Reed, C. 2007. Laying the Foundations for a World Wide Argument Web. Artificial Intelligence , 171(10–15): 897–921.

21.

Simari, G. R. and Loui, R. P. 1992. A Mathematical Treatment of Defeasible Reasoning and Its Implementation. Artificial Intelligence , 53: 125–157.

22.

Verheij, B. (1996). Two Approaches to Dialectical Argumentation: Admissible Sets and Argumentation Stages’. (1996). Proceedings of the Eighth Dutch Conference on Artificial Intelligence (NAIC’96), Edited by: Meyer, J.-J. Ch. and van der Gaag, L. C. pp. 357–368. Utrecht: Utrecht University.

23.

Verheij, B.

2003. DefLog: On the Logical Interpretation of Prima Facie Justified Assumptions. Journal of Logic and Computation , 13: 319–346.

24.

Vreeswijk, G. A.W.

1993. “Studies in Defeasible Argumentation”. Free University of Amsterdam. PhD thesis

25.

Vreeswijk, G. A.W. (2006). An Algorithm to Compute Minimally Grounded and Admissible Defence Sets in Argument Systems’. (2006). Computational Models of Argument; Proceedings of COMMA 2006, Edited by: Dunne, P. E. and Bench-Capon, T. J.M. pp. 109–120. IOS.