A labelling approach for ideal and stage 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 semantics11 (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.

We say that (1) an argument A attacks an argument B iff (A,B)∈att, (2) an argument A attacks a set of arguments Args iff A attacks an argument in Args, (3) a set of arguments attacks an argument A iff an argument in Args attacks A and (4) a set of argument Args1 attacks a set of arguments Args2 iff an argument in Args1 attacks an argument in Args2.

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 Args is a set of arguments, then we write Args+ for the set of arguments that are attacked by at least one argument in Args, and Args− for the set of arguments that attack at least one argument in Args. In the definition below, F(Args) stands for the set of arguments that are acceptable in the sense of Dung (1995).

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.

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.

We write in(Lab) for {A∣Lab(A)=in}, out(Lab) for {A∣Lab(A)=out} and undec(Lab) for {A∣Lab(A)=undec}. Sometimes, we write a labelling Lab as a triple (Args1,Args2,Args3) where Args1=in(Lab), Args2=out(Lab) and Args3=undec(Lab).

We introduce two functions (Lab2Ext and Ext2Lab) 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, Lab2Ext(Lab)=in(Lab). 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, Ext2Lab(Args)=(Args,Args+,Ar∖(Args∪Args+)), where Ar is the set of all arguments in the argumentation framework. Notice that although Lab2Ext is defined for any labelling, Ext2Lab is defined only for sets of arguments that are conflict-free (otherwise the result would not be a correct labelling).

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.

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.

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

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.

Preferred, grounded, semi-stable and stable labellings correspond to preferred, grounded, semi-stable and stable extensions, respectively, as stated in the following theorem.

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.

3.Ideal semantics

The intuition behind ideal semantics 33 (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).

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.44 It holds that “⊑” is at least as strong as “≈”; that is, if Lab1⊑Lab2 then Lab1≈Lab2.55

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(Lab1)∩out(Lab2)=∅ and out(Lab1)∩in(Lab2)=∅, 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.

The uniqueness of the ideal labelling has been proved in Caminada and Pigozzi (2009).66 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.

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.

We will now treat the notion of ideal semantics as described in Dung et al. (2007).88

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.

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.99

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 Args, where Args∪Args+ is maximal w.r.t. set-inclusion.1010

In order to describe a stage extension in terms of labellings, we first introduce the concept of a conflict-free labelling

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.

It holds that every stable labelling is also a stage labelling.1111

If there exists at least one stable labelling, then each stage labelling is also a stable labelling.1212

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|Args stands for (Ar∩Args,att∩(Args×Args)) (assuming that AF=(Ar,att)) and Lab|Args stands for Lab∩(Args×{in,out,undec}).

As was mentioned at the beginning of the current section, stage semantics can also be expressed using the traditional approach of argument extensions.

Before discussing the connection between stage labellings and stage extensions, we first state the connection between conflict-free labellings and conflict-free sets.

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.1313

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 Ext2Lab and Lab2Ext become bijections and each other's inverse.

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:

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.1Stage 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 (Args∪Args+) of their extensions.1414 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 (∅,∅,{A,B}), whereas stage semantics yields a single extension {B}, corresponding with a labelling ({B},∅,{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.1515 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(Lab)=in(Lab)∪out(Lab)).

Lemma 4.13

Let AF be an argumentation framework with grounded labelling 𝒢 such that undec(G)=∅. Let 𝒞 be an arbitrary conflict-free labelling of AF. It holds that if range(G)⊆range(C) then C=G.

Proof

From the fact that range(G)⊆range(C), together with the fact that undec(G)=∅, it follows that range(G)=range(C). So undec(C)=∅, 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)=∅ 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 Cmax 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 (Cmax) does exist. Now suppose that Cmax is not a stage labelling. Then there exists a conflict-free labelling Dmax of AF such that range(Cmax)⊊range(Dmax). Let AF′=AF|range(G), G′=G|range(G), Cmax′=Cmax|range(G), and Dmax′=Dmax|range(G). From the fact that G⊑Cmax it follows that G′=Cmax′. Also, from range(Cmax)⊊range(Dmax) it follows that range(Cmax′)⊆range(Dmax′). Furthermore, it holds that range(G′)⊆range(Cmax′) (since G′=Cmax′), so by transitivity we obtain range(G′)=range(Dmax′). From Lemma 4.13 it then follows that G′=Dmax′, from which it follows that G⊑Dmax. So Dmax is an element of {C∣C is a conflict-free labelling of AF and G⊑C}. But since range(Cmax)⊊range(Dmax) it then follows that Cmax 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.

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.