2.1 Basic concepts

Central to the theory of abstract argumentation is the notion of an argumentation framework, which, as mentioned in the introduction, is essentially a directed graph in which the arguments are represented by the nodes and the attack relation is represented by the arrowsFootnote 2. Given the tutorial nature of this paper, we keep the presentation simple by restricting ourselves to finite argumentation frameworks. Some notes on infinite argumentation frameworks are given in Section 4.4.

We say that argument A ∈ Ar attacks argument B ∈ Ar (or that A is an attacker of B) iff (A, B) ∈ att. If and A ∈ Ar then we say that A attacks iff there exists such that A attacks B. Likewise, we say that attacks A iff there exists such that B attacks A. For A ∈ Ar we then write A ⁻ for {B | (B, A) ∈ att} and A ⁺ for {B | (A, B) ∈ att}. Likewise, for we write for and for .

We will also need to consider the restriction of an argumentation framework to a subset of its arguments.

An argumentation framework encodes, through the attack relation, the existing conflicts within a set of arguments. It is then interesting to identify the conflict outcomes, which, roughly speaking, means determining which arguments should be accepted (let us say, ‘survive the conflict’) and which arguments should be rejected (let us say, ‘are defeated in the conflict’), according to some reasonable criterion.

Consider for instance the argumentation framework depicted in Figure 2. Which arguments are able to survive the conflict? Is there only one possibility or are there several solutions available? While the reader may resort to her/his personal intuition to devise a specific answer in this simple case, it appears that a well-defined systematic method is needed to deal with the case of arbitrarily complex argumentation frameworks: such a formal method to identify conflict outcomes for any argumentation framework is called argumentation semantics.

Figure 2

A simple argumentation framework

Two main approaches to the definition of argumentation semantics are available in the literature: the labelling-based approach and the extension-based approach.

The idea underlying the labelling-based approach is to give each argument a label. A sensible (although not the only possible) choice for the set of labels is: in, out or undec, where the label in means that the argument is accepted, the label out means that the argument is rejected, and the label undec means one abstains from an opinion on whether the argument is accepted or rejected. Each argument then receives exactly one label. In Figure 2, one might start assigning the label in to argument A, as it does not receive attacks, then derive that the argument B should be out, and then assume that C should be in in turn. While this labelling may sound reasonable, other choices are, at least in principle, available: for example, one might assign all arguments the label in, but this seems incompatible with the existence of conflicts among them, or one might assign all arguments the label undec, but this seems excessively cautious at least as far as the unattacked argument A is concerned. Thus, a specific labelling-based argumentation semantics provides a way to select ‘reasonable’ labellings among all the possible ones, according to some criterion embedded in its definition.

The idea underlying the extension-based approach is to identify sets of arguments, called extensions, which can survive the conflict together and thus represent collectively a reasonable position an autonomous reasoner might take. Exemplifying with an incremental procedure for extension construction, in Figure 2, one might start including the argument A, as it does not receive attacks, then exclude the argument B, and then assume that C should be included in turn, ending up with the extension {A, C}. Also, in this case, other choices are available, at least in principle: for example, one might consider the extension {A, B, C}, but (again) this seems incompatible with the existing conflicts among arguments, or one might consider the empty set as extension, but this seems excessively cautious since at least A seems to deserve inclusion in any extension. Thus, a specific extension-based argumentation semantics provides a way to select ‘reasonable’ sets of arguments among all the possible ones, according to some criterion embedded in its definition.

Let us now turn to the formal counterpart of the notions exemplified above.

A generic labelling assigns to each argument of an argumentation framework a label taken from a predefined set.

A labelling-based semantics prescribes a set of labellings for any argumentation framework.

We will also need the notion of restriction of a labelling to a set of arguments.

In this paper, we focus on the case Λ = {in, out, undec}, a sensible choice for Λ that has received considerable attention in the literature (Caminada, Reference Caminada2006a, Reference Caminada2007a; Rahwan & Larson, Reference Rahwan and Larson2008; Caminada & Gabbay, Reference Caminada and Gabbay2009; Rahwan & Tohmé, Reference Rahwan and Tohmé2010; Caminada & Pigozzi, Reference Caminada and Pigozzi2011). An alternative approach can be found in Jakobovits and Vermeir (Reference Jakobovits and Vermeir1999), where a four-valued labelling is considered. The idea of labelling can also be placed in correspondence with the notion of status assignment in inference graphs (Pollock, Reference Pollock1995). Connections between defeat status assignments and extensions in Dung's argumentation frameworks have been firstly investigated by Verheij (Reference Verheij1996).

We will implicitly assume the use of Λ = {in, out, undec}, when the reference to the label set is excluded. In particular, given a labelling , we write in for in}, out for out} and undec for undec}. A labelling can be represented as a set of pairs. For instance, the labelling exemplified above for Figure 2 can be described as {(A, in), (B, out), (C, in)}. Sometimes, we will also represent a labelling as the triple (in out undec). The same labelling for Figure 2 can thus be represented as ({A, C}, {B}, ∅).

As an extension is simply a set of arguments, we can directly introduce the notion of extension-based semantics.

Some observations concerning the relations between the labelling and extension-based approaches are worth mentioning. First, as set membership can be formulated in terms of a simple binary labelling, for example, with Λ = {∈, ∉}, the extension-based approach can be regarded as a special case of the general labelling-based approach. The latter is therefore more general, while the former, probably due to its simplicity, has received by far more attention in previous literature.

Considering the three-valued labelling we focus on in this paper, a correspondence with the extension-based approach can be drawn, so that a semantics based on this labelling can be turned into an extension-based one through a simple mapping. In fact, given a labelling of an AF, the labels in can be understood as identifying the members of an extension. This kind of correspondence can be easily identified in the exemplification concerning Figure 2 given above and is formally expressed by the following definitions.

On the other hand, given a set of arguments E, it is possible to define a corresponding three-valued labelling by distinguishing the arguments belonging to E, those attacked by some member of E, and those which neither belong to E nor are attacked by E. As this correspondence is well defined only if E satisfies some basic conditions, we defer its formal definition to Section 2.2 (Definition 14).

We now introduce some notions that are common to both approaches.

First, it can be noted that both approaches encompass (in general) the existence of a set of alternatives (either labellings or extensions) for a single argumentation framework. It may be the case, however, that a semantics is defined so that a univocal outcome is prescribed for each argumentation framework (formally for any argumentation framework AF, or ). In this case, the semantics is said to belong to the unique-status (or single-status) approach, while in the general case, it is said to belong to the multiple-status approach.

Consider the argumentation framework of Figure 3 representing a mutual attack. A unique-status approach may prescribe the {(A, undec), (B, undec)} labelling or analogously a single empty extension, corresponding to an explicit abstention from decision. On the other hand, a multiple-status approach may encompass the two alternative labellings {(A, in), (B, out)} and{(A, out), (B, in)} or analogously the extensions {A} and {B} corresponding to two opposite ways of solving the conflict.

Figure 3

An argumentation framework with mutual attack

As evident from the previous example, a semantics does not provide, in general, the ‘last word’ about the status of an argument A. In fact, may prescribe both a labelling where A is labelled in and another where A is labelled out (or, analogously, an extension including A and another one not). In the view of producing a synthetic evaluation for each argument, one has then to consider questions like ‘Is being in in all labellings significantly different from being in only in some of them?’ or ‘If an argument is not in in all labellings should it being labelled out or undec in the remaining labellings make some difference?’. Analogous questions may arise for the extension-based approach. It emerges that the assessment of a synthetic justification status for each argument of an argumentation framework is a further distinct (and not trivial) step after the identification of labellings or extensions. This will be dealt with in Section 4, where the related issue of skepticism comparison between semantics will also be examined.

In Sections 2.3–2.10, we will examine several argumentation semantics proposed and widely studied in the literature. The presentations of the various semantics roughly follow a common line: first, the underlying intuitive idea is introduced, then the semantics formal definition is given according to both the labelling and the extension-based approach, and finally, the presentation is completed by discussing illustrative examples and examining additional important formal properties and inter-semantics relationships. As to examples, the relatively simple ones provided in Figures 4–6 will be used as a common reference throughout this section, adding other more specific and/or complex ones where necessary. We invite the reader to go through Figures 4–6 in order to set up a ‘personal view’ on how the conflict they encode might be resolved, and then comparing this view with those emerging from the various semantics proposals analyzed in the following. Before dealing directly with semantics, however, we need to examine in the next subsection two general properties, which underlie most of them, namely admissibility and conflict-freeness.

Figure 4

A simple argumentation framework

Figure 5

The case of ‘floating’ acceptance

Figure 6

Cycle of three attacking arguments

2.2 Admissibility and conflict-freeness

To introduce the notion of admissibility let us start from a very simple principle: for every argument A one accepts (or rejects) an explanation of why it is accepted (or rejected) should be available, in relation to acceptance or rejection of other arguments connected to A through the attack relation. This concept lends itself to slightly different, although converging, declinations in the labelling and in the extension-based approach.

In the labelling-based approach, assigning the in label to an argument A can be explained by having assigned the out label to all its attackers (or by A being attacked by no argument) so that A is not affected by any attack, while assigning the out label to A can be explained by having assigned the in label to one of its attackers, which enables A to be rejected.

This is expressed by the following definitions.

• • An in-labelled argument is said to be legally in iff all its attackers are labelled out.

• • An out-labelled argument is said to be legally out iff it has at least one attacker that is labelled in.

Note that, according to this definition, for any argumentation framework, a labelling where all arguments are undec is admissible. Let us now examine admissible labellings in the reference examples. Considering Figure 4, it is evident that A, having no attackers, can only be labelled legally in or undec. Considering the latter case, B can only be labelled undec, which implies that C cannot be legally in. If C is labelled undec then D is undec too; otherwise, C is labelled out, entailing that D is labelled in. This yields two admissible labellings: the trivial one (∅, ∅, {A, B, C, D}) and ({D}, {C}, {A, B}). The case where A is labelled in leaves two alternatives for B. If B is labelled undec we have the same options as above for C and D yielding the two additional admissible labellings ({A}, ∅, {B, C, D}) and ({A, D}, {C}, {B}). Finally, if B is labelled out, three alternatives are left open for C and D: they can be both labelled undec or C can be legally labelled in if D is labelled out and vice versa, yielding three other labellings: ({A}, {B}, {C, D}), ({A, C}, {B, D}, ∅), and ({A, D}, {B, C}, ∅).

In Figure 5, with a reasoning similar to that in the previous example it can be noted that both A and B can be labelled undec or one in and the other out. The first case yields only the trivial labelling (∅, ∅, {A, B, C, D}), and in the other cases C may be labelled undec, yielding D undec, or out leaving for D both the options undec and in. In summary, there are seven admissible labellings whose enumeration is left to the reader.

In Figure 6, no admissible labellings besides the trivial one (∅, ∅, {A, B, C}) are possible.

Turning now to the extension-based approach, the inclusion of an argument A in an extension E can be supported by the fact that E rules out all the attackers of A by in turn attacking them (if any). In other words, E ‘defends’ A. This is formalized in the following definitions.

An example of defense is given in Figure 7. Here, we have an argument A that has three attackers: B ₁, B ₂, and B ₃. defends A because it attacks all these attackers.

Figure 7

defends argument A

Having introduced the notion of defense, a basic requirement for a set of arguments is the capability to defend all its elements. It is, however, natural to also require that the set of arguments features a sort of ‘internal coherence’: no conflict should be allowed within a set of arguments that are considered able to survive the conflict together. This leads to the definition of a conflict-free set.

Note that this definition also rules out sets containing self-attacking arguments (in the case A = B).

An admissible set (Dung, Reference Dung1995) is required to be both internally coherent and able to defend its elements.

As evident from this definition, the empty set is admissible for any argumentation framework. Apart from this trivial case, let us examine conflict-free and admissible sets in the reference examples. Considering Figure 4, one can observe that the non-empty conflict-free sets are {A}, {B}, {C}, {D}, {A, C}, {A, D}, and {B, D}. Among them, {A}, having no attackers, is admissible (actually F({A}) = {A}). The sets {B} and {C} are not admissible (B does not defend itself from A and C does not defend itself from B), while {D} is, as it defends itself from C (in particular F({D}) = {A, D}). Moreover, the sets {A, C} and {A, D} are admissible (in the former case, C defends itself from the attack by D and is defended by A against B, and in the latter, both A and D are able to defend themselves), while {B, D} is not (a defense for B against A is lacking). Applying analogous considerations in Figure 5, it can be seen that the non-empty admissible sets are {A}, {B}, {A, D}, and {B, D}. On the other hand, in Figure 6, only the empty set is admissible since the non-empty conflict-free sets are just the singletons {A}, {B}, {C} but no argument defends itself from the attack it receives.

As probably noticed by the reader, the above examples point out a correspondence between admissible labellings and admissible sets. Before stating this correspondence in the general case, we need to provide the mapping from sets of arguments to labellings that was not introduced in the previous section since it is well defined only for conflict-free sets of argumentsFootnote 4.

Let us call an extension-based semantics conflict-free if all its extensions are conflict-free sets. We can then extend the above definition to sets of extensions.

The correspondence between admissible labellings and admissible sets stated by Proposition 1 has been proved in Caminada and Gabbay (Reference Caminada and Gabbay2009).

• • if is an admissible set then Ext2Labis an admissible labelling;

• • if is an admissible labelling then Lab2Extis an admissible set.

It can be noted that the correspondence is not bijective, since different admissible labellings may give rise to the same admissible set. For instance, in the argumentation framework of Figure 4, both ({A}, {B}, {C, D}) and ({A}, ∅, {B, C, D}) are admissible labellings, whose set of in-labelled arguments yields the same admissible set {A}.

To complete the correspondence, it is also possible to define a notion of a conflict-free labelling that parallels the one of the conflict-free setFootnote 5.

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

2. 2. 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 (second bullet) is essentially the same. However, the condition for in-labelled arguments (first bullet) 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).

2.3 Complete semantics

Complete semantics can be regarded as a strengthening of the basic requirements enforced by the idea of admissibility. Intuitively, while admissibility requires one to be able to give reasons for accepted and rejected arguments but leaves one free to abstain about any argument, complete semantics also requires one to abstain only if there are no good reasons to do otherwise. That is, if one abstains from having an opinion on whether the argument is accepted or rejected, then one should have insufficient grounds to accept the argument (meaning that not all its attackers are rejected) and insufficient grounds to reject the argument (meaning that it does not have an attacker that is accepted). Note in particular that, while the trivial solution of leaving anything undecided is always admissible, it is not always complete since there can be arguments one has good reason not to abstain about.

In the labelling-based approach, the intuition described above corresponds to extending Definition 9 in order to encompass a notion of an argument being legally undecided.

• • An undec-labelled argument is said to be legally undec iff not all its attackers are labelled out and it does not have an attacker that is labelled in.

It is clear from Definitions 18 and 10 that every complete labelling is an admissible labelling (but the reverse does not hold in general).

An alternative characterization of a complete labelling can be provided (Caminada & Gabbay, Reference Caminada and Pigozzi2009).

1. 1. A is labelled in iff all its attackers are labelled out;

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

Although Proposition 2 does not explicitly mention undec, it follows that each argument that is labelled undec does not have all its attackers out (otherwise, it would have to be labelled in by point 1) and it does not have an attacker that is labelled in (otherwise, it would have to be labelled out by point 2). Therefore, each undec-labelled argument is legally undec. A formal proof of Proposition 2 can be found in Caminada and Gabbay (Reference Caminada and Gabbay2009).

Turning to the extension-based approach, a complete extension is a conflict-free set that includes precisely those arguments it defends. That is, if an argument is defended by the set it should be in the set, and if an argument is not defended by the set, it should not be in the set. Technically, this means that a complete extension is a conflict-free fixed point of the characteristic function, as stated in the following definition (Dung, Reference Dung1995).

It is clear from Definitions 19 and 13 that every complete extension is an admissible set (but the reverse does not hold in general).

Let us now provide some examples to illustrate the notion of complete semantics. In Figure 4, one can observe that, among the seven admissible labellings, ({A}, {B}, {C, D}), ({A, C}, {B, D}, ∅), and ({A, D}, {B, C}, ∅) are complete. In particular, note that A is legally in in all labellings because all its attackers are out (trivially, because it has no attackers). B is legally out in all labellings because it has an attacker (A) that is in. On the other hand, C and D can be both legally undec or one legally in and the other legally out. Analogously, in the same figure, it can be noted that {A} is a complete extension (A has no attackers and is therefore trivially defended by any set, A defends C from B but not from D), and {A, C} and {A, D} are complete extensions too.

In Figure 5, the trivial labelling (∅, ∅, {A, B, C, D}) is complete, as well as ({A, D}, {B, C}, ∅) and ({B, D}, {A, C}, ∅). Analogously, ∅ is a complete extension (no unattacked arguments exist, which would be the only arguments defended by the empty set) as well as {A, D} and {B, D}, while {A} and {B} are not complete extensions since they both also defend argument D.

In Figure 6, the only complete labelling is the trivial one (∅, ∅, {A, B, C}) and analogously the only complete extension is ∅ (as it was the case for admissible labellings/sets).

As the above examples also show, there is a direct mapping between complete labellings and complete extensions: it has been proved in Caminada and Gabbay (Reference Caminada and Gabbay2009) that this correspondence is bijective as stated in the following proposition.

2.4 Grounded semantics

If one regards each complete labelling (or complete extension) as a reasonable position one can take in the presence of the conflicting information expressed in the argumentation framework, then a possible question is to examine what is the most ‘grounded’ position one can take, namely the position that is least questionable. The idea is then to accept only the arguments that one cannot avoid to accept, to reject only the arguments that one cannot avoid to reject, and abstaining as much as possible. This gives rise to the most skeptical (or least committed) semantics among those based on complete extensions.

This idea has a straightforward formal counterpart in terms of a minimality requirementFootnote 6.

As we have already seen complete labellings and extensions in the examples of Figures 4–6, one can identify those featuring the minimality property required by the above definitions. In the example of Figure 4, the grounded labelling is ({A}, {B}, {C, D}) while the grounded extension is {A}. In both Figures 5 and 6, the grounded labelling is the trivial one ((∅, ∅, {A, B, C, D}) and (∅, ∅, {A, B, C}), respectively), and analogously, the grounded extension is the empty set in both cases.

The uniqueness of the grounded labelling and extension in these examples is not accidental. Considering the grounded extension, since F is monotonic, it follows from the Knaster–Tarski theorem that F has a unique smallest fixed point. It can then be proved that this fixed point is also conflict-free (Dung, Reference Dung1995).

1. 1. is a minimal conflict-free fixed point of F;

2. 2. is the smallest fixed point of F.

It follows that:

• • the grounded extension is unique (i.e. grounded semantics belongs to the unique-status approach);

• • the grounded extension is the least complete extension; in particular, it is included in any complete extension.

By virtue of the one-to-one correspondence between complete extensions and complete labellings established in Section 2.3, it can be proved that the grounded labelling is unique and coincides with Ext2Lab, where is the grounded extension. Similarly, if is the grounded labelling, then Lab2Ext is the grounded extension.

As a confirmation of the intuitive meaning stated at the beginning of the section, it turns out that the grounded semantics can be described not only in terms of minimizing acceptance. In fact, the complete labelling where is minimal is also the complete labelling where is minimal and the complete labelling where is maximal. This is stated in Proposition 5, whose proof is based on Lemma 1 (see Caminada and Gabbay (Reference Caminada and Gabbay2009) for details).

1. 1. is the complete labelling where is minimal (w.r.t. set inclusion);

2. 2. is the complete labelling where is minimal (w.r.t. set inclusion);

3. 3. is the complete labelling where is maximal (w.r.t. set inclusion).

Given the bijective correspondence between complete labellings and complete extensions, the above proposition can be equivalently formulated for the extension-based approach.

1. 1. E is the least (w.r.t. set inclusion) complete extension;

2. 2. E is the complete extension such that E ⁺is minimal (w.r.t. set inclusion);

3. 3. E is the complete extension such that Ar\(E ∪ E ⁺) is maximal (w.r.t. set inclusion).

Finally, an interesting property proved in Dung (Reference Dung1995) provides a useful ‘constructive’ characterization of grounded semantics for finite (and more generally finitaryFootnote 7) argumentation frameworks.

On the basis of Proposition 7, the grounded labelling (or equivalently extension) can be obtained incrementally by first labelling in those arguments that do not receive attacks. Then the arguments attacked by those labelled in are labelled out. The same steps are iterated considering only those arguments that have not been labelled yet, namely repeating the procedure on an argumentation framework obtained by suppressing the already labelled arguments. In particular, this corresponds to labelling in those unlabelled arguments that only receive attacks from arguments labelled out, and then labelling out those attacked by the newly labelled in arguments. The procedure is then iterated until an iteration does not produce any newly in or out labelled argument. Then, any still unlabelled arguments are labelled undec.

It can be noted that the first iteration corresponds to labelling in the arguments in F ¹(∅) and out the arguments attacked by F ¹(∅), the second iteration labelling in the arguments in F ²(∅) and out the arguments attacked by F ²(∅), and so on. This procedure can be applied to the examples and shows that the grounded extension includes those and only those arguments whose defense is ‘rooted’ in unattacked arguments (see Baroni and Giacomin (Reference Baroni and Giacomin2007) for a formal treatment of this notion, called strong defense).

If the aim is not so much to compute the entire grounded extension (labelling) but merely to examine whether or not an argument is in the grounded extension (labelled in by the grounded labelling), then one could also use the proof procedures described in Modgil and Caminada (Reference Modgil and Caminada2009).

2.5 Preferred semantics

While grounded semantics adopts a skeptical, or least-commitment, standpoint, one can also consider the alternative view oriented at accepting as many arguments as reasonably possible. This may give rise to mutually exclusive alternatives for acceptance: for instance, a mutual attack can be reasonably resolved by accepting either of the conflicting arguments, but clearly not both.

The idea of maximizing accepted arguments is expressed by preferred semantics, whose description in the labelling-based and extension-based approaches is given in the following definitions.

Considering the examples of Figures 4–6, the existence of multiple preferred labellings (or extensions) immediately emerges. For instance, in Figure 4, two non-skeptical solutions exist for the mutual attack between C and D, giving rise to the preferred labellings ({A, C}, B, D}, ∅) and ({A, D}, {B, C}, ∅). Similarly, two preferred extensions exist, namely, {A, C} and {A, D}.

In Figure 5, again, two alternative non-skeptical solutions exist for the mutual attack between A and B. In both cases, C is then rejected and D accepted. This intuitive description corresponds to the two preferred labellings ({A, D}, {B, C}, ∅) and ({B, D}, {A, C}, ∅) and, analogously, to the preferred extensions {A, D} and {B, D}.

In Figure 6, instead, no non-trivial solutions to the conflict are available under the constraint of admissibility, as the reader may remember from previous subsections. It then follows that the unique preferred labelling in this case is (∅, ∅, {A, B, C}) and, similarly, the only preferred extension is ∅.

As usual, the evident correspondences in the above examples are not accidental: it can be proved that an analogous version of Proposition 3 holds for preferred semantics, that is, there is a bijective correspondence between preferred labellings and preferred extensions through the Ext2Lab (and Lab2Ext) functions.

It turns out that the complete labellings with maximal in are the same as the complete labellings with maximal out, as stated in Proposition 8, whose proof is based on Lemma 1.

1. 1. is a complete labelling where is maximal (w.r.t. set inclusion) among all complete labellings;

2. 2. is a complete labelling where is maximal (w.r.t. set inclusion) among all complete labellings.

An analogous formulation of Proposition 8 for the extension-based approach could be provided in a straightforward way.

Relationships of preferred extensions with other semantics notions have been analyzed in Dung (Reference Dung1995). Preferred extensions can for instance equivalently be characterized as maximal complete extensions.

1. 1. is a maximal (w.r.t. set inclusion) admissible set of AF;

2. 2. is a maximal (w.r.t. set inclusion) complete extension of AF.

This in particular implies that the grounded extension is included in any preferred extension, as it is in any complete extension. By definition, the grounded extension coincides with the intersection of all complete extensions: one may then wonder whether this also holds for preferred extensions. The answer is negative, as shown for instance by the example of Figure 5, where the grounded extension is ∅ while the intersection of the preferred extensions is {D}. Again, this fact can be easily translated in the labelling-based approach referring to the in-labelled arguments.

An algorithm that produces all preferred labellings (and therefore also produces all preferred extensions) is described in Caminada (Reference Caminada2007a) and Modgil and Caminada (Reference Modgil and Caminada2009). If the aim is merely to determine whether an argument is in at least one preferred extension (labelled in by at least one preferred labelling), then one could also use the proof procedures described in Vreeswijk and Prakken (Reference Vreeswijk and Prakken2000), Vreeswijk (Reference Vreeswijk2006), Verheij (Reference Verheij2007), Modgil and Caminada (Reference Modgil and Caminada2009), and Caminada (Reference Caminada and Wu2010b). Proof procedures for determining whether an argument is in every preferred extension (labelled in by every preferred labelling) are provided in Cayrol et al. (Reference Cayrol, Doutre and Mengin2003) and Modgil and Caminada (Reference Modgil and Caminada2009).

2.6 Stable semantics

So far, we have discussed semantics according to the intuitive idea that an argument can be accepted, rejected, or left undecided. One can, however, prefer more committed evaluations, in which there is no room for neutrality or shades of gray and everything is just black or white. This means that undecided arguments are simply ‘forbidden’ as in statements like ‘you're either with us or against us’.

This clear-and-strong view has a direct formulation in both the labelling-based and the extension-based approach.

In the example of Figure 4, there are two stable labellings, namely ({A, C}, {B, D}, ∅) and ({A, D}, {B, C}, ∅). Similarly, two stable extensions exist, namely {A, C} and {A, D}. In Figure 5, the labellings ({A, D}, {B, C}, ∅) and ({B, D}, {A, C}, ∅) are stable and, analogously, there are two stable extensions, namely {A, D} and {B, D}.

Figure 6 shows that the strong view underlying stable semantics cannot be universally applied. In fact, no labelling or extension complying with the definition can be identified (the requirements of conflict-freeness and the ability to attack all other arguments are incompatible in this case). This can be regarded as a limitation of stable semantics as ‘stable extensions do not capture the intuitive semantics of every meaningful argumentation system’ (Dung, Reference Dung1995). Looking at this fact from another perspective, different from other semantics reviewed so far, in the case of stable semantics, the trivial labelling (or extension) does not represent the ‘default’ conflict resolution one can resort to when nothing else is reasonable. It follows that, using a terminology from Baroni and Giacomin (Reference Baroni and Giacomin2009a), stable semantics is not universally defined, since there are argumentation frameworks where it is intrinsically impossible to apply its ‘in-or-out’ view. No other argumentation semantics considered in the literature shows this limitation.

Apart from this critical case, the reader may have noticed that the stable labellings (extensions) coincide with the preferred ones in the other two cases. One may then wonder whether stable semantics (leaving apart critical cases) coincides with preferred semantics. The answer is negative, as shown by the argumentation framework of Figure 8. Here, one can verify that there are three complete labellings, namely (∅, ∅, {A, B, C, D, E}), ({A}, {B}, {C, D, E}), and ({B, D}, {A, C, E}, ∅), and, correspondingly, three complete extensions. Two of the three labellings (extensions) are preferred, namely ({A}, {B}, {C, D, E}), and ({B, D}, {A, C, E}, ∅), but clearly only the last one is stable.

Figure 8

An argumentation framework where preferred and stable semantics differ

Let us now generalize this and possibly related observations, examining the properties of stable semantics in general.

First, it is possible to characterize the concept of a stable labelling in other terms. In particular, note that the difference between a complete labelling and an admissible labelling is that a complete labelling has the additional requirement that every undec-labelled argument is legally undec. However, if, as in Definition 24, there are no undec-labelled arguments in the first place, then this extra requirement becomes superfluous. Moreover, the fact that anything that is not labelled in is labelled out ensures that every stable labelling is also preferred (but not vice versa, as we have already seen). These considerations are summarized in Proposition 10 (note that point 3 of Proposition 10 coincides with Definition 24).

1. 1. is a conflict-free labelling with undec;

2. 2. is an admissible labelling with undec;

3. 3. is a complete labelling with undec;

4. 4. is a preferred labelling with undec.

On the other hand, it is immediate to see that a stable extension is an admissible set, hence the equivalent characterizations given in Proposition 11 (again, note that point 1 of Proposition 11 coincides with Definition 25).

1. 1. is a conflict-free set with ;

2. 2. is an admissible set such that ;

3. 3. is a complete extension such that ;

4. 4. is a preferred extension such that ;

5. 5. .

As probably evident from above, the bijective labellings–extensions correspondence through Ext2Lab (and Lab2Ext) also holds for stable semantics as proved in Caminada and Gabbay (Reference Caminada and Gabbay2009).

An algorithm that produces all stable labellings (and therefore also all stable extensions) is described in Caminada (Reference Caminada2007a) and Modgil and Caminada (Reference Modgil and Caminada2009). If the aim is merely to determine whether an argument is in at least one stable extension (labelled in by at least one stable labelling) then one could also use the proof procedures described in Caminada and Wu (Reference Caminada and Wu2009). Proof procedures for determining whether an argument is in every stable extension (labelled in by every stable labelling) are also provided in Caminada and Wu (Reference Caminada and Wu2009).

2.7 Semi-stable semantics

As illustrated in the previous section, the requirement of ‘forbidding’ undecided arguments turns out to yield no results in some cases. A more sophisticated idea consists in expressing a definite opinion on the largest possible set of arguments, while restricting as much as possible (but not necessarily avoiding) those that are left undecided. This intuition lies at the basis of semi-stable semantics, which can be defined as follows:

It follows directly that each stable labelling is also a semi-stable labelling and that semi-stable labellings coincide with stable labellings when the latter exist. This is because a stable labelling is a complete labelling with an empty set of undec-labelled arguments. Hence, it is a complete labelling where the set of undec-labelled arguments is minimal (so a semi-stable labelling). Furthermore, if there exists at least one stable labelling then the set of undec-labelled arguments has to be empty in any complete labelling with a minimal set of undec-labelled arguments (semi-stable labelling) and hence any such a labelling has to be stable. The same relationship holds between stable and semi-stable extensions: each stable extension is a semi-stable extension and semi-stable extensions coincide with stable extensions when the latter exist. Accordingly, we already know, from the previous section, the behavior of semi-stable semantics in the examples of Figures 4 and 5.

Even in situations where stable extensions/labellings do not exist, the existence of semi-stable labellings (or extensions) is anyway guaranteed, since they are selected among the (always existing) complete ones. In particular, in the example of Figure 6, the only semi-stable labelling (extension) is (again) the trivial one.

The maximization requirement imposed by semi-stable semantics is intuitively similar, but clearly different, from the maximization requirement in the definition of preferred semantics. One may wonder whether these different maximizations actually lead to the same results. The answer is negative (see also Verheij, Reference Verheij2003) as shown by the example of Figure 8, where there are two preferred labellings (and then two corresponding extensions) namely ({A}, {B}, {C, D, E}) and ({B, D}, {A, C, E}, ∅), but only the latter is semi-stable (as well as stable).

Equivalent characterizations of semi-stable semantics in terms of admissible labellings/sets and of preferred labellings/extensions are available (see for instance Caminada and Gabbay, Reference Caminada and Gabbay2009) as summarized in the following propositions.

1. 1. is a complete labelling where undecis minimal (w.r.t. set inclusion) among all complete labellings.

2. 2. is an admissible labelling where undecis minimal (w.r.t. set inclusion) among all admissible labellings.

3. 3. is a preferred labelling where undecis minimal (w.r.t. set inclusion) among all preferred labellings.

1. 1. is a complete extension where is maximal (w.r.t. set inclusion) among all complete extensions;

2. 2. is an admissible set where is maximal (w.r.t. set inclusion) among all admissible sets;

3. 3. is a preferred extension where is maximal (w.r.t. set inclusion) among all preferred extensions.

Finally, the usual bijective labellings–extension correspondence also holds for semi-stable semantics (see Caminada, Reference Caminada2007a; Caminada & Gabbay, Reference Caminada and Gabbay2009). An algorithm that produces all semi-stable labellings (and therefore also all semi-stable extensions) is described in Caminada (Reference Caminada2007a) and Modgil and Caminada (Reference Modgil and Caminada2009).

The concept of semi-stable semantics can be traced back to the notion of admissible stage extensions (see Section 2.9) introduced by Verheij (Reference Verheij1996). Although there are differences in the basic formalization (Verheij for instance does not use the standard extension-based approach), it can be proved that Verheij's approach is equivalent to that of Caminada, who, independently from Verheij, rediscovered the same concept under the name of semi-stable semantics (Caminada, Reference Caminada2006b).

2.8 Ideal semantics

The notion of ideal semantics can perhaps be best explained using a description concerning a judgment aggregation context (Caminada & Pigozzi, Reference Caminada and Pigozzi2011). Assume a group of people who all try to accept as much as possible, examine what they all agree on, and check whether this position is still defensible: if not, water it down (by abstaining from some arguments instead of accepting or rejecting them) until it becomes defensible. The result is the ideal labelling/extension.

In order to formally define the concept of the ideal labelling, we first need to treat some preliminaries (see Caminada & Pigozzi, Reference Caminada and Pigozzi2011).

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 transitivityFootnote 8. It holds that ‘⊑’ is at least as strong as ‘≈’; that is, if then Footnote 9.

The idea of ‘⊑’ is to define what it means for a labelling to be more committed than another labelling (this is a special case of skepticism comparison, an issue that will be dealt with systematically in Section 4). 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 out and out in ∅, 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, it is less problematic to have conflicts between in and undec or between out and undec. Thus, compatibility provides an indication of how easy or difficult it is to share 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 of defining an initial labelling. If everybody agrees that the argument is labelled in (i.e. 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 (i.e. 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 Reference Caminada and Pigozzi(2011) that this process results in constructing the most committed (‘biggest’) labelling that is less or equally committed than each preferred labelling. This leads to the following definition of ideal semantics.

The uniqueness of the ideal labellingFootnote 10 and the fact that the ideal labelling is a complete labelling have been proved in Caminada and Pigozzi Reference Caminada and Pigozzi(2011). Since the grounded labelling is the smallest complete labelling (w.r.t. ‘⊑’), it directly follows that the ideal labelling is bigger than or equal to the grounded labelling.

There are several ways of describing the ideal labelling (Reference CaminadaCaminada, 2011).

1. 1. is the biggest admissible labelling that is smaller than or equal to each preferred labelling;

2. 2. is the biggest admissible labelling that is compatible with each admissible labelling;

3. 3. is the biggest admissible labelling that is compatible with each complete labelling;

4. 4. is the biggest admissible labelling that is compatible with each preferred labelling.

The concept of ideal semantics was originally introduced in terms of extensions in Dung et al. (Reference Dung, Mancarella and Toni2007), drawing inspiration from the analogous concept of ideal skeptical semantics in extended logic programs (Alferes et al., Reference Alferes, Dung and Pereira1993).

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., Reference Dung, Mancarella and Toni2007). It then follows directly that the ideal extension is a superset of the grounded extension.

There are several ways of describing the ideal extension.

1. 1. is the biggest admissible set that is a subset of each preferred extension;

2. 2. is the biggest admissible set that is not attacked by any admissible set;

3. 3. is the biggest admissible set that is not attacked by any complete extension;

4. 4. is the biggest admissible set that is not attacked by any preferred extension.

In Proposition 17, the equivalence between points 1 and 2 follows from Dung et al. (Reference Dung, Mancarella and Toni2007, 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.

The bijective labellings–extensions correspondence through Ext2lab (and Lab2Ext) also holds for ideal semantics (Reference CaminadaCaminada, 2011).

Ideal semantics is similar to grounded semantics in the sense that it always yields a unique labelling (extension). Actually, it can be seen that the ideal labelling (extension) coincides with the grounded labelling (extension) in the examples of Figures 4–6. In particular, referring to extensions, in Figure 4, the intersection of preferred extensions {A} coincides with the grounded extension; in Figure 5, the intersection of preferred extensions {D} is not admissible and its only admissible subset is the empty set (coinciding with the grounded extension); in Figure 6, there is only one (empty) preferred extension, which coincided with the grounded and the ideal extension.

However, as shown in Propositions 14 and 16, in general, ideal semantics tends to be less skeptical than grounded semantics. As an example, in the argumentation framework of Figure 9, the grounded labelling is (∅, ∅, {A, B}) (the grounded extension is ∅), whereas the ideal labelling is ({A}, {B}, ∅) (the ideal extension is {A}).

Figure 9

The ideal labelling can be less skeptical than the grounded labelling

To determine whether an argument is an element of the ideal extension, point 2 of Proposition 17 implies that it is sufficient to determine whether it is an element of an admissible set that is not attacked by any admissible set. Proof procedures for this are straightforward and have been described in Dung et al. (Reference Dung, Mancarella and Toni2007).

An alternative approach that is very close to ideal semantics is that of eager semantics (Caminada, Reference Caminada2007b). Where the ideal extension is the (unique) biggest admissible (and complete) subset of each preferred extension, the eager extension is the (unique) biggest admissible (and complete) subset of each semi-stable extension. The eager extension is a superset of the ideal extension, making eager semantics (to the best of our knowledge) the most credulous unique status semantics that has been proposed in the literature. The eager extension and the associated eager labelling can be computed by first calculating all semi-stable labellings (using for instance the algorithm of Caminada (Reference Caminada2007a)) and subsequently applying the judgment aggregation operators specified in Caminada and Pigozzi Reference Caminada and Pigozzi(2011).

2.9 Stage semantics

The concept of stage semantics has been introduced in Verheij (Reference Verheij1996) and further developed in Verheij (Reference Verheij2003) in different formal settings with respect to the ones considered in this paper. Precise (and rather straightforward) correspondences can be drawn anyway so that we can describe stage semantics in terms of labellings and extensions, as for all other semantics in this paper. In essence, a stage labelling is a conflict-free labelling where undec is minimal, whereas a stage extension is a conflict-free set of arguments , where is maximal.

It holds that every stable labelling (extension) is also a stage labelling (extension).

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

There also exists an alternative way to describe the concept of stage semantics. 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 with undec labels for the arguments that did not make their way into the subgraph. Similarly, a stage extension takes a maximal subgraph of the argumentation framework that has at least one stable extension. A stage extension is then a stable extension of such a maximal subgraph.

1. 1. is a conflict-free labelling where undec() is minimal (w.r.t. set inclusion) among all conflict-free labellings;

2. 2. is a maximal subset of Ar such that has a stable labelling, and is a stable labelling of .

1. 1. is a conflict-free set where is maximal (w.r.t. set inclusion) among all conflict-free sets;

2. 2. is a maximal subset of Ar such that has a stable extension, and is a stable extension of .

The bijective labellings–extensions correspondence through Ext2Lab (and Lab2Ext) also holds for stage semantics, as proved in Caminada Reference Caminada(2011). An algorithm that produces all stage labellings (and therefore also all stage extensions) is described in Caminada (Reference Caminada2010a).

To exemplify stage labellings (extensions), let us refer as usual to the examples of Figures 4–6. Stage labellings (extensions) coincide with stable labellings (extensions), when the latter exist, as in the case of Figures 4 and 5. On the other hand, in the case of Figure 6, different from all the other semantics examined so far, stage semantics prescribes three non-trivial labellings, namely ({A}, {B}, {C}), ({B}, {C}, {A}, ({C}, {A}, {B}) (and, of course, the corresponding three non-empty extensions, {A}, {B}, and {C}).

Using the technical properties and the examples described above, we are now ready to describe the intuition behind stage semantics. In essence, stage semantics shares with stable semantics a sort of preference for strongly committed evaluations with respect to the undecided ones. As already seen, such an attitude is not universally applicable: the solution of stage semantics is to consider the maximal restrictions where this attitude is still applicable. In other terms, stage semantics can be read as the attempt to identify and then ignore the minimal amounts of information that prevent the application of a black-and-white view of the world. Note that different information can be ignored in different labellings (extensions), for instance in the example of Figure 6 arguments A, B, and C are alternatively ignored.

The idea of minimizing the set of undec-labelled arguments or, alternatively, of maximizing the range () of extensions is common to stage and semi-stable semantics. However, where semi-stable semantics aims to maximize the range under the condition of admissibility, stage semantics tries to maximize the range under the weaker condition of conflict-freeness. As shown above, this amounts to taking the stable labellings (extensions) of the biggest subframework that has at least one stable labelling (extension). Hence, the approach of stage semantics is comparable with 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 intersection of all their models). That is, it is as if stage semantics interprets the absence of stable labellings/extensions as some form of ‘inconsistency’, which needs to be handled taking the ‘maximal consistent subframeworks’. On the other hand, in semi-stable semantics as well as in most other semantics, all arguments play a role in all extensions/labellings. In particular, an undecided argument retains the capability to cause other arguments to be undecided, while this is not the case in stage semantics. An example is shown in Figure 10. Here, any other semantics considered in this paper yields a single labelling (∅, ∅, {A, B}) corresponding to the extension ∅, whereas stage semantics yields a single labelling ({B}, ∅, {A}) corresponding to the extension {B}. In essence, what stage semantics does is to ignore argument A, since this argument causes the framework not to have any stable labelling/extension.

Figure 10

Stage semantics differs from semi-stable semantics

Another example to illustrate the difference between stage semantics and semi-stable semantics is given in Figure 11. 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, and the second one being {B}, corresponding to a labelling ({B}, {C}, {A}). The first stage extension (labelling) is the result of ignoring argument C and 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 11) is not always labelled in. With any other semantics considered in this paper, however, an argument without any attackers is always labelled in.

Figure 11

A peculiar case for stage semantics

2.10 CF2 semantics

With the exception of stage semantics, all semantics reviewed so far are admissibility based, that is, the labellings (extensions) they prescribe are admissible. Moreover, they are compatible with the basic skeptical view represented by grounded semantics, in the sense that in any of their labellings (extensions), the accepted arguments are a superset of those accepted by the grounded semantics. Focusing now on those of these semantics that are multiple-status (namely complete, preferred, stable, and semi-stable), one can notice that odd-length unidirectional attack cycles cause a sort of singularity in their behavior. For instance, considering the example of Figure 6, only the trivial labelling (extension) is prescribed and, in the case of stable semantics, no labelling (extension) exists at all. This gives rise to a sort of unbalanced treatment of even-length and odd-length unidirectional attack cycles: non-trivial labellings (extensions) exist for the former ones, while they do not exist for the latter. This has been regarded as problematic by Pollock (Reference Pollock2001), since in some contexts an ‘equal’ treatment of cycles, independent of their length, can be more appropriateFootnote 11. It is evident that this requires giving up the property of admissibility, as no non-trivial admissible labellings (extensions) exist for the example of Figure 6. In fact, the behavior of stage semantics goes in that direction, since in the example of Figure 6, it prescribes three non-trivial labellings, namely ({A}, {B}, {C}), ({B}, {C}, {A}), ({C}, {A}, {B}), or, analogously, three non-empty extensions, namely {A}, {B}, and {C}. Stage semantics, however, shows a peculiar behavior and strongly departs from grounded semantics in some cases. As already commented in Section 2.9, a stage labelling (or extension) may even exclude from acceptance an unattacked argument (A in the example of Figure 11) while including an argument attacked by it (B in the same example). This kind of behavior has no parallel in all other semantics considered in this paper and, as such, appears rather hard to justify. Then the question arises as to whether it is possible to define a multiple-status semantics that is not admissibility based, treats in an ‘equal’ way odd- and even-length unidirectional attack cycles, while preserving compatibility with the grounded semantics in any case.

CF2 semantics (Baroni & Giacomin, Reference Baroni and Giacomin2003; Baroni et al., Reference Baroni, Giacomin and Guida2005) satisfies the above requirements. In fact, to achieve this objective a relatively sophisticated semantics definition scheme has been devised called SCC (strongly connected component)-recursiveness. The SCC-recursive scheme is based on the graph theoretical notion of SCC. In brief, SCCs provide a unique partition of a directed graph into disjoint parts where all nodes are mutually reachable (it is assumed that reachability is a reflexive relation). Formally, SCCs are the equivalence classes induced by the path equivalence (i.e. mutual reachability) relation between nodes. To illustrate this notion, in the example of Figure 4, there are three SCCs, namely {A}, {B}, and {C, D}, in Figure 5 there are three SCCs too, namely {A, B}, {C}, and {D}, while the argumentation framework of Figure 6 consists of a unique SCC, namely {A, B, C}. As another example, in the argumentation framework of Figure 8, there are two SCCs, namely {A, B} and {C, D, E}.

An important property of the SCC decomposition is that the graph obtained considering SCCs as single nodes is acyclic, that is, the attack relation induces a partial order between the SCCs. The SCC-recursive scheme exploits this property and can be intuitively regarded as a constructive procedure to incrementally build extensions (or labellings) following the partial order of SCCs. In brief, one ‘locally’ applies some extension selection criterion to the initial SCCs, that is, those not receiving attacks from others. Then, for each possible choice identified in the initial SCCs, one accordingly suppresses some arguments from the initial argumentation framework and the procedure is recursively applied to the new argumentation framework resulting from this modification, until no remaining arguments are left to process. In the case of CF2 semantics, the ‘local’ selection criterionFootnote 12 applied to SCCs is quite simple and is similar to the intuition underlying stage semantics: all maximal conflict-free sets are selected. However, embedding this criterion within the SCC-recursive scheme gives rise to different results.

We now provide a formal definition of CF2 semantics in terms of extensions (as this is its original and easier to follow formulation), exemplify its behavior, and review its properties. For further details and more extensive explanations of the SCC-recursive scheme, the reader may refer to Baroni et al. (Reference Baroni, Giacomin and Guida2005). A labelling-based formulation of CF2 semantics has not been previously considered in the literature and will be examined at the end of the section.

• • if |SCCS_AF| = 1;

• • otherwise,

  where

• • denotes the set of maximal conflict-free sets of AF;

• • SCCS_AF denotes the set of strongly connected components of AF;

• • for any , .

Definition 33 is quite complicated and its detailed illustration is beyond the scope of the paper. We remark only that the recursion is well founded since, in the second branch of Definition 33, CF2 semantics itself is applied to a set of restricted (and disjoint) argumentation frameworks, each including a strictly lesser number of arguments with respect to the original one. This ensures that the base case, namely the application of CF2 semantics to an argumentation framework consisting of a single SCC (the first branch of Definition 33), is reached in a finite number of steps. Note, in particular, that an argumentation framework including 0 or 1 arguments necessarily consists of a single SCC.

Despite technical complications, the idea underlying CF2 semantics is relatively simple and can be illustrated with reference to our examples. In Figure 4, there is one initial SCC, namely {A}, and of course it contains only one maximal conflict-free set, namely {A} itself, which is selected for extension building. The subsequent (according to the partial order induced by the attack relation) SCC, namely {B}, is suppressed as its only element is attacked by the already selected argument A. The last SCC, namely {C, D}, then remains unaffected by previously selected elements and we can select its maximal conflict-free subsets {C} and {D} to be combined with the previous selection, leading to the CF2 extensions {A, C} and {A, D}.

In Figure 5, there is one initial SCC, namely {A, B}, whose maximal conflict-free sets are {A} and {B}, each representing a starting point for further extension construction. In fact, in both cases, the subsequent SCC, namely {C} is suppressed, leaving the remaining SCC, {D}, unaffected and providing {D} itself as a maximal conflict-free subset. It turns out that there are two CF2 extensions, namely {A, D} and {B, D}.

The argumentation framework of Figure 6 consists of only one SCC and therefore its CF2 extensions coincide with its maximal conflict-free subsets {A}, {B}, and {C}.

In the example of Figure 8, the application of CF2 semantics definition is more articulated. The (again unique) initial SCC is {A, B}, which, as in the previous case, yields {A} and {B} as the starting points for further extension construction. Considering {A}, we have that B is attacked by the extension and the subsequent SCC {C, D, E} is left unaffected. As a consequence, all its maximal conflict-free subsets {C}, {D}, and {E} are available, yielding the three CF2 extensions {A, C}, {A, D}, and {A, E}. Considering {B}, both A and C are attacked by the extension and therefore suppressed. The restriction of the argumentation framework to the set {D, E} then remains to be evaluated. As {D} is the initial SCC of this restricted argumentation framework, it is selected and then the subsequent SCC {E} is entirely suppressed, yielding a further CF2 extension {B, D}.

Finally, in the example of Figure 11, a unique CF2 extension is identified, namely {A}, yielding agreement with grounded semantics.

Having exemplified the behavior of CF2 semantics, we summarize in Proposition 18 some of its known properties in relation to the other semantics notions considered in the paper.

• • —any CF2 extension is a maximal conflict-free set of AF;

• • the grounded extension is included in any CF2 extension;

• • for any preferred extension E there is a CF2 extension E′ such that E ⊆ E′;

• • any stable extension is also a CF2 extension.

As mentioned above, CF2 has been conceived and defined in the extension-based setting. The same semantic notion can, however, be expressed using the SCC-recursive scheme in the labelling context.

• • if |SCCS_AF| = 1, is a conflict-free labelling with maximal in among conflict-free labellings and such that ;

• • otherwise, ∀S ∈ SCCS_AF is a CF2 labelling of and all arguments in are labelled out,

  where all notations are as in Definition 33.

By inspection of Definitions 33 and 34, it can be seen that the bijective labellings–extensions correspondence through Ext2Lab (and Lab2Ext) holds for CF2 semantics.

2.11 Roundup

We now provide an overview of how the semantics that have been treated until now are related. In Figure 12, we graphically depict what can be seen as an ontology of argumentation semantics. The figure shows for instance that every stable labelling is also a stage labelling, a semi-stable labelling, and a CF2 labelling, that every semi-stable labelling is also a preferred labelling, etc. The same relations of Figure 12 also hold for the extension-based approach. In Table 1, we provide an overview of how the admissibility-based semantics can be expressed in terms of complete labellings.

Figure 12

Relations among alternative labelling notions

Table 1

Describing admissibility-based semantics in terms of complete labellings

3.1 Fundamental principles

A basic standpoint of abstract argumentation consists in the fact that semantics evaluation should only depend on the topology of the argumentation framework (i.e. on the attack relation between arguments) while being totally independent of any property of arguments at the underlying language level, which is abstracted away. Formally, this language independence principle corresponds to the fact that argumentation frameworks that are isomorphic give rise to the same semantics outcome (modulo the isomorphism relation). First, let us introduce a (quite natural) isomorphism relation between argumentation frameworks.

Then we can express the language independence principle for extension-based semantics in a straightforward way by requiring extension correspondence through the bijective mapping.

The formulation for labellings is conceptually similar and formally just slightly more articulated.

The language independence principle lies at the heart of the notion itself of abstract argumentation semantics and is satisfied by all literature semantics we are aware of.

Another basic standpoint in abstract argumentation concerns the fact that the attack relation represents a situation of ‘incompatibility’ between arguments, so that two arguments cannot stand together if there is an attack (either unidirectional or mutual) between them. This leads to the fundamental conflict-free principle, which states that any extension or labelling prescribed by a semantics should be conflict-free, according to Definitions 12 and 16, respectively. Its straightforward formulation is given below and, again, to our knowledge, it is satisfied by all semantics proposed in the literature.

3.2 Defense-related properties

The notion of defense of an argument A against its attackers by a set of arguments (possibly including A itself) is quite intuitive in the extension-based approach and has been formalized in Definition 11. One might then argue that defense against attackers is a necessary condition for extension membership: an argument that is not defended by an extension cannot have citizenship there. This corresponds to the admissibility property, which has an obvious formulation for both extension-based and labelling-based semantics.

The notion of defense plays a key role in Dung's complete, grounded, preferred, and stable semantics, which all satisfy the admissibility property. Subsequent proposals that are anyway related to Dung's ones, namely semi-stable and ideal semantics, also satisfy admissibility, while stage and CF2 semantics, relying on the more basic notion of conflict-freeness, do not respect this property.

With a dual reasoning, one might also argue that defense against attackers is a sufficient condition for extension membership: an argument that is defended by an extension should belong to the extension itself. This property is called reinstatement since the acceptance status of an argument is ‘reinstated’ thanks to defense against attackers.

Definition 40 An extension-based semantics satisfies the reinstatement property if and only if for any argumentation framework AF, and for any argument A it holds that

or, equivalently, F(E) ⊆ E.

In the labelling-based approach, the same idea can be expressed by requiring that if all attackers of an argument are labelled out then the argument is labelled in.

Definition 41 A labelling-based semantics satisfies the reinstatement property if and only if for any argumentation framework AF, and for any argument A it holds that

By inspection of Definitions 13, 19, and 40, it can be clearly seen that a complete extension is an admissible set with the addition of the reinstatement property. On the other hand, examining Definitions 10, 18, and 41, one can note that the reinstatement property is not sufficient to make an admissible labelling complete. In fact, in the labelling context, we also need an explicit statement about rejection: an argument that is attacked by an argument labelled in cannot be undecided and must be explicitly rejected.

Definition 42 A labelling-based semantics satisfies the rejection property if and only if for any argumentation framework AF, and for any argument A it holds that

Thus, in the labelling context, completeness is equivalent to the conjunction of admissibility, reinstatement, and rejection.

Reinstatement can be regarded as a further basic property in Dung's approach: it characterizes complete semantics, as remarked above, and is also featured by grounded, preferred, and stable semantics as their extensions are complete. The same holds for semi-stable and ideal semantics, while this is not the case for stage and CF2 semantics. In the labelling approach, it can be observed, in an analogous way, that grounded, preferred, stable, semi-stable, and idealFootnote 13 labellings are also complete labellings; therefore, they satisfy both reinstatement and rejection properties. On the other hand, stage and CF2 semantics do not feature the reinstatement property while satisfying rejection.

3.3 Forbidding subsumption

Considering a set of outcomes (either extensions or labellings) prescribed by a given semantics, the question arises as to whether it is possible that one of the outcomes in the set is ‘subsumed’ by another one. Consider the example of Figure 3. Here, one may consider a ‘resolute’ stance where A or B is accepted (giving rise to two alternative labellings/extensions) or adopt a more ‘cautious’ stance where everything is left undecided (giving rise to the empty extension or trivial labelling). Mixing the resolute and cautious stance in the same set of extensions/labellings produced by a reasoner may be considered undesirable. Moreover, if argument acceptance requires membership to all extensions or to the in part of all labellingsFootnote 14, the results of acceptance evaluation are determined only by the labellings/extensions corresponding to the cautious stance (in particular, if the empty set/trivial labelling is included in the set of outcomes, no argument can be accepted). In this case, the presence of extensions/labellings having no effects on acceptance results (due to the subsumption relation) might be regarded as somewhat redundant.

One can then consider a property, called I-maximality, requiring that there is no subsumption in the set of outcomes.

In the extension-based approach, the I-maximality property simply states that no extension is a strict subset of another one.

Note that I-maximality is a property of the set of extensions per se and does not imply that maximality is prescribed by the semantics-specific definition of what an extension is. For instance, any unique-status semantics (like grounded semantics) necessarily satisfies I-maximality according to Definition 43, despite the fact that (at least in the case of the grounded semantics) the unique extension is not maximal in any sense.

In the labelling-based approach, we can draw analogous considerations with the difference that both arguments labelled in and out should be considered in the definition.

Either in the extension-based or the labelling-based version, it can be checked that all semantics considered in this paper satisfy I-maximality, with the exception of complete semantics.

3.4 Allowing abstention

The considerations carried out about I-maximality are somewhat related to the assumption that a set of extensions/labellings corresponds to the positions of an individual reasoner adopting a definite stance, either resolute or cautious. In other contexts, however, it may be considered desirable that a set of extensions/labellings allows mixing both stances: this may even be necessary for applications such as argumentation-based judgment aggregation (Caminada & Pigozzi, Reference Caminada and Pigozzi2011). In this perspective, considering again the argumentation framework of Figure 3, if a set of extensions/labellings encompasses both the acceptance of A (with rejection of B) and the acceptance of B (with rejection of A), then it is also reasonable to allow for the position where one simply abstains from having an explicit opinion on A and B.

One can then consider a property of allowing abstention that can be expressed in a straightforward way for the labelling-based approach.

The same idea can be expressed in a slightly more complicated way in the extension-based approach.

It can be seen that only complete semantics satisfies this property, while all other multiple-status semantics considered in this paper do not. Technically, unique-status semantics comply with the allowing abstention property, because they simply do not admit dilemmas, but one might argue that assessment of this property only makes sense for multiple-status semantics.

3.5 Topology-related properties

As evidenced by the language-independence principle, semantics outcomes for an argumentation framework actually depend on the attack relation only, that is, on the topology of the corresponding directed graph. More specific relations between graph topology and semantics outcomes can then be considered, according to the basic idea that attacks are the ‘channels’ through which arguments affect each other.

On this basis, a first elementary consideration suggests that if an argumentation framework can be partitioned into several subgraphs that are not connected to each other, they should not affect each other at the semantics level. In order to better specify and formalize this intuition, we first need to introduce, in the obvious way, the operation of union of (disjoint) argumentation frameworks.

Note that, by definition, AF ₁ ⊎ AF ₂ consists of at least two subgraphs not connected to each other. Now, a first basic semantics requirement, called crash resistance, consists in excluding that there are cases of ‘contaminating’ argumentation frameworks, namely argumentation frameworks that determine the semantics outcomes for any union they are included in, as formally specified in Definition 48.

Clearly, the existence of contaminating argumentation frameworks for a given semantics can be regarded as undesirable and violates in the strongest possible way the intuition that disjoint subgraphs should not affect each other. Stable semantics does not satisfy crash resistance as any argumentation framework consisting of a simple self-attacking argument is contaminating and determines as outcome an empty set of either labellings or extensions. All other semantics considered in this paper are crash resistant.

Crash resistance excludes only the most ‘brutal’ form of interference between disjoint subgraphs but does not prevent them from affecting each other in less drastic (but still counterintuitive) ways: a stronger non-interference requirement can then be considered. We formally define this concept by introducing the notion of isolated set in Definition 49 and then requiring in Definitions 50 and 51 any isolated set to be unaffected by other parts of the argumentation framework as far as extensions (or labellings) are concerned.

In words, a set is isolated if it does not attack outside arguments nor receive attacks from them, that is, .

In words, the intersection with an isolated set of any extension prescribed by for AF is equal to one of the extensions prescribed by for the restriction of AF to , and vice versa. The same idea is expressed by the corresponding formalization in the labelling-based approach.

It holds that non-interference implies crash resistance. It follows that stable semantics does not satisfy non-interference. On the other hand, it can be shown that all other semantics considered in this paper feature the non-interference property.

Making a step further, one can consider the fact that arguments can affect each other only following the direction of attacks: if argument A attacks B then A affects B but not vice versa. Then, the considerations drawn above for isolated sets of arguments can also be applied to unattacked sets of arguments, which should be unaffected by the remaining part of the argumentation framework: in brief, this is the directionality property that is formalized in the following definitions:

It can clearly be seen that isolated sets are a special case of unattacked sets and therefore directionality implies non-interference. It is shown in Baroni and Giacomin (Reference Baroni and Giacomin2007) that complete, grounded, preferred, ideal, and CF2 semantics satisfy the directionality property, while it can be seen that stable, semi-stable, and stage semantics do not. This is illustrated in the example of Figure 8, where the set {A, B} is unattacked and it holds that for stable, semi-stable, and stage semantics while for the same semantics and hence . The counter-example runs in a fully analogous way in the labelling-based approach.

A synthetic view of the property satisfactionFootnote 15 by the semantics considered in this paper is given in Table 2, where complete, grounded, preferred, stable, semi-stable, ideal, and stage semantics are denoted, respectively, as . The last row specifies the possible values of the cardinality of the set of extensions/labellings (1 indicates a unique status and universally defined semantics, ≥0 indicates multiple status and not universally defined, and ≥1 indicates multiple status and universally defined)Footnote 16.

Table 2

Satisfaction of general properties by argumentation semantics

4.1 The notion of justification status

Either labellings or extensions provide the basis for the evaluation of the justification status of arguments: we assume, as in previous literature (Baroni & Giacomin, Reference Baroni and Giacomin2007, Reference Baroni and Giacomin2009b), that evaluating argument justification is meaningful only when the set of labellings or extensions is not empty; otherwise, the basis for evaluation is lacking. For this reason, we need to formally identify the argumentation frameworks where the evaluation basis is not empty.

Even when an argumentation framework belongs to or , the ‘final answer’ on argument justification is not directly determined. In fact, several choices are available as to the derivation of justification status from a set of labellings or extensions. At a basic level, two very simple (and, in a sense, extreme) alternatives for the notion of justification can be considered: skeptical justification requires that an argument is accepted in all labellings (or extensions), while credulous justification requires that an argument is accepted in at least one labelling (or extension). This is formalized in the following definitions:

Clearly, skeptical justification implies credulous justification; moreover, a third justification status can be derived: an argument is not justified (or rejected) if it is not credulously justified (and hence also not skeptically justified).

It can be noted that in any unique-status semantics skeptical and credulous acceptance coincide, so that an argument can only be accepted or rejected. In this context, it is possible, however, to consider two levels of rejection; in fact, a rejected argument can be attacked or not by the unique extension (or, analogously, can be labelled out or undec in the unique labelling). The former case corresponds to a stronger form of rejection (these arguments have sometimes been called defeated outright in the literature; Pollock, Reference Pollock1992) while in the latter case rejection is clearly weaker (these arguments being called provisionally defeated according to the same terminology).

While the brief remarks above correspond to the prevailing approaches to the notion of justification status in the literature, one may observe that a more systematic treatment is possible, by combining the ideas concerning the status of an argument with respect to a single labelling (or extension) and those referring to a plurality of them. In fact, an argument can be in one of three possible states with respect to a single labelling (namely, in, out, or undec) and correspondingly can be accepted, defeated outright, or provisionally defeated with respect to a single extension. If a plurality of labellings (or extensions) is considered, the argument can be in a given state in all, some, or none of them. Excluding impossible combinations (e.g. an argument is in in all labellings and out in some of them), seven justification states arise. For the labellings approach, these are summarized in Definition 58.

If we assume a labelling-based semantics to specify the reasonable positions (labellings) one can take in the presence of the conflicting information specified in the argumentation framework, then one can present an intuitive interpretation of the concept of a justification status. For instance, the justification status of {in} means that the argument has to be accepted in every reasonable position. Similarly, the justification status {in, undec} means that in every reasonable position, the argument is either accepted or abstained from having an explicit opinion on, but the argument cannot be rejected. Such an interpretation of the notion of justification status is for instance used by Wu and Caminada Reference Wu and Caminada(2010) and by Dvořák (2011).

It is also possible to define the notion of a justification status in terms of the extensions approach, as is done in Definition 59.

• • A ∈ E;

• • A ∈ E ⁺;

• • A ∉ (E ∪ E ⁺);

• • : A ∈ E ⁺, : A ∉ (E ∪ E ⁺), and : A ∈ E;

• • : A ∈ E, : A ∉ (E ∪ E ⁺), and : A ∈ E ⁺;

• • : A ∈ E, : A ∈ E ⁺, and : A ∉ (E ∪ E ⁺);

• • : A ∈ E, : A ∈ E ⁺, and : A ∈ (E ∪ E ⁺).

Correspondences with more ‘traditional’ definitions of justification states can be easily drawn, but a full adoption in the literature of the systematic Definitions 58 and 59 is still to comeFootnote 17.

4.2 Skepticism and skepticism relations

The term skepticism has been used in the literature (often in an informal way) to discuss argumentation semantics behavior, for example, by observing that a semantics is ‘more skeptical’ than another one. Intuitively, a skeptical attitude tends to make less committed choices about the justification of the arguments, as well exemplified by the traditional notions of skeptical and credulous acceptance recalled in Section 4.1. In other words, a skeptical behavior tends to leave arguments in an ‘undecided’ justification state and to accept (or reject) as least arguments as possible, while a less skeptical (or more credulous) behavior corresponds to more extensive acceptance (or rejection) of arguments. Note, in particular, that the notion of commitment (or decidedness) of a justification state must be clearly distinguished from the notion of acceptance: two justification states corresponding to definite acceptance and definite rejection, although reflecting antithetical choices about the state of an argument, have both the same highest level of commitment.

Which are the formal counterparts of these basic intuitions?

Starting from basic elements, we first need to define a criterion to compare extensions and labellings with respect to skepticism. As to extensions, this is quite simple: an extension E ₁ is ‘more skeptical’ than (to be precise, at least as skeptical as) an extension E ₂ if E ₁ ⊆ E ₂, since then E ₁ supports the acceptance of no more arguments than E ₂. As to labellings, we have to consider both the in and out labels as being both more committed choices than undec. We can then state that a labelling is at least as skeptical as a labelling according to the inclusion of both the sets of in and out labelled arguments. These intuitions are formalized in Definition 60.

While the above relations are sufficient to compare unique-status semantics, the next step is to introduce skepticism relations between non-emptyFootnote 18 sets of extensions or labellings in order to compare multiple-status semantics. As more extensively discussed in Baroni and Giacomin (Reference Baroni and Giacomin2009b), several alternatives can be considered for this issue.

As a first basic step, one can consider a comparison method based on inclusion of the sets of accepted arguments, either according to skeptical or credulous acceptance. This gives rise to the skepticism relations stated in the following definitions:

To exemplify the above notions, consider first the example of Figure 3. In the extension-based approach, the grounded and ideal semantics prescribe the set of extensions while all other semantics prescribe . Clearly, , while it is not the case that (denoted as ). For the same example in the labelling-based approach, grounded and ideal semantics prescribe the set of labellings while all other semantics prescribe . Again, it can be seen that , , while .

Considering the example of Figure 5, in the extension-based approach, the grounded and ideal semantics prescribe the set of extensions , while all other semantics prescribe . It turns out that , while . The case of labellings is perfectly analogous with for grounded and ideal semantics and for other semantics yielding and , while .

Figure 8 provides a more articulated case for comparison. In the extension-based approach, grounded and ideal semantics prescribe , preferred semantics prescribes , CF2 semantics prescribes , while stable, semi-stable, and stage semantics prescribe . It follows that for any i, j ∈ {1, 2, 3} , while for any i ∈ {1, 2, 3} . On the other hand, these sets are completely ordered according to . Again, the case of labellings is perfectly analogous.

As a further step in the analysis of skepticism relations, one may observe that explicitly rejected arguments should also be taken into account in a similar way as accepted arguments: this gives rise to the following definitions.

Consider again the example of Figure 3, and for a set of extensions , let us denote in the following . Then, referring to the already mentioned sets of extensions and we have . Clearly, , while . For the same example in the labelling-based approach, it can analogously be seen that .

In the example of Figure 5, we refer again to , yielding . Then and . The case of labellings is perfectly analogous with , while .

Figure 8 provides again a more articulated case. Considering the sets of extensions , , . It follows that for any i, j ∈ {1, 2, 3} , while for any i ∈ {1, 2, 3} . On the other hand, . Again, the case of labellings is perfectly analogous.

To have an example where the relations of the ⪯_∩ kind differ from those of the kind, consider the example of Figure 13. In the extension-based approach, all semantics except stableFootnote 19, CF2, and stage semantics prescribe the set of extensions , while CF2 and stage semantics prescribe . It follows that and . Similar considerations apply in the labelling-based approach.

Figure 13

Cycle of three attacking arguments in turn attacking another argument

Definitions 61–68 treat sets of extensions or labellings ‘as a whole’ by simply considering their intersection or union: for instance, very different sets of extensions are treated in the same way if they have an empty intersection. In order to take into account how single extensions or labellings are defined, a different kind of definition is needed: the skepticism relation between two sets (let say ) of extensions or labellings should be based on some comparison between their individual elements. In particular, according to a skeptical approach to argument justification, in order to state that is at least as skeptical as , one may require that every element in has a more skeptical counterpart in , while, according to a credulous approach, one may require dually that every element in has a less skeptical counterpart in . This general idea is formalized by the following definitions, which resort to the basic comparisons between single extensions and labellings identified in Definition 60.

Let us exemplify these relations.

In the example of Figure 3, referring to the already mentioned sets of extensions and we have but, different from the previously considered relations, . On the other hand, . As usual, analogous relations hold for the labelling-based approach.

Similarly, in the example of Figure 5, with it holds that . It goes without saying that the same holds in the labelling-based approach.

Finally, consider the case of Figure 8 with sets of extensions , . We can first observe that for i ∈ {2, 3, 4} and (different from previous relations) . Then we can note that and since the only element of (namely {B, D}) is a superset of (actually coincides with) an element of either or . Also, since the elements {A, C}, {A, D}, and {A, E} of are supersets of {A} in and {B, D} is present both in and in . With similar observations, it can be seen that . Turning to the relation corresponding to the credulous perspective, it can clearly be seen that for i ∈ {2, 3, 4} . Also, since {A} is included in some elements of and {B, D} is present both in and in . On the other hand, . Different from the skeptical perspective, (the only element of , namely {B, D} is present both in and in ), while it can clearly be seen that ({A} is not included in any element of ) and (as above for sets {A, C}, {A, D}, {A, E}). Again, the case of labellings is perfectly analogous.

A stronger skepticism relation, combining the skeptical and credulous perspectives, can be obtained by combining together the relations .

As also evident from their definitions, the various skepticism relations introduced above are related to each other by implication. In particular, two implication chains can be identified in correspondence with the skeptical or the credulous perspective. In fact, given two sets of extensions and of an argumentation framework AF, it holds that

(1)

(2)

The only non-trivial implications in (1) and (2) concern the fact that , and, similarly, : they have been proved in Baroni and Giacomin (Reference Baroni and Giacomin2009b).

Using Definitions 63, 64, 67, 68, 71, 72, 74, and the same kind of reasoning, it is possible to prove that the analogous relations hold in the labelling-based approach. In fact, given two sets of labellings and of an argumentation framework AF, it holds that

(3)

(4)

Turning to the comparison between semantics, for a given generic relation ⪯ concerning either extensions or labellings, it is quite natural to define an induced relation of skepticism between two semantics and , by requiring that ⪯ holds for their sets of extensions or labellings. As it may happen that either or prescribes an empty set of extensions (or labellings) in some cases, the induced relation has to refer to a set of argumentation frameworks where both and prescribe non-empty sets of extensions (or labellings).

Focusing on the extension-based approach, while Definition 75 applies to any set of argumentation frameworks , clearly, the most interesting case is when . Then, when considering a skepticism comparison concerning more than two semantics it is reasonable to consider a common reference . As to the semantics discussed in this paper, only stable semantics may prescribe an empty set of extensions/labellings. Therefore, two reference sets can be considered: the universe of all argumentation frameworks if stable semantics is not involved in the comparison or otherwise. Clearly, the same considerations hold in the labelling-based approach by replacing .

It is worth noting that, in general, two semantics and may not be comparable with respect to skepticism. For instance, it may be the case that there are two argumentation frameworks AF ₁ and AF ₂ such that behaves more skeptically than in the case of AF ₁ but behaves more skeptically than in the case of AF ₂, or that the two semantics yield incomparable sets of extensions for some given argumentation framework. Furthermore, the order between two semantics may be different according to the credulous or the skeptical perspective.

A detailed analysis of skepticism relations between extension-based semantics (except stage semantics, whose consideration is anyway not problematic and is included in this paper) has been carried out in Baroni and Giacomin (Reference Baroni and Giacomin2009b) to which the reader may refer for details: here, we report only the resulting partial orders, graphically presented as Hasse diagrams. As mentioned above, distinct Hasse diagrams are presented for the case where stable extensions exist and for the general one.

The partial ordersFootnote 20 induced by all the relations corresponding to the skeptical perspective, namely coincide. The Hasse diagram corresponding to the general case is shown in Figure 14: grounded semantics is the most skeptical one and since the grounded extension is the least complete extension, it turns out that . Ideal, preferred, and semi-stable semantics are all comparable among them and orderly less skeptical. CF2 semantics is comparable with but not with the other ones, while stage semantics is not comparable with any other, also due to its peculiar behavior in some cases, exemplified in the argumentation framework of Figure 11.

Figure 14

relations for any argumentation framework

The Hasse diagram for considering only the argumentation frameworks where stable extensions exist (and then coincide with semi-stable and stage extensions) is shown in Figure 15. It can be seen that in this context, CF2 semantics is comparable with (and less skeptical than) stable semantics.

Figure 15

relations for argumentation frameworks in )

Turning to skepticism relations based on the credulous perspective, namely , and , the Hasse diagram corresponding to the general case is shown in Figure 16. An almost complete ordering is achieved where, due to the change of perspective, in particular, complete semantics is in mutual relation with preferred semantics: since preferred extensions are maximal complete extensions. Moreover, one can note that CF2 is now comparable with any other (and is actually the least skeptical semantics) and that the ordering between is inverted with respect to Figure 14.

Figure 16

relations for any argumentation framework

The Hasse diagram for considering only the argumentation frameworks where stable extensions exist is shown in Figure 17: here, a total order is achieved, which obeys the same relations as the general case but where stable, semi-stable, and stage semantics coincide.

Figure 17

relations for argumentation frameworks in )

Finally, the Hasse diagrams for the relations arising from the conjunction of the skeptical and credulous perspective are shown in Figures 18 and 19, for the general case and for argumentation frameworks where stable extensions exist, respectively. As is obvious, stronger relations entail lesser comparability between semantics, but one can note in particular that the role of as the ‘bottom’ skeptical reference with respect to all other semantics (but ) is confirmed.

Figure 18

relation for any argumentation framework

Figure 19

relation for argumentation frameworks in )

4.3 Backwards compatibility

Another kind of relation between semantics concerns the ability of a semantics to ‘extend’ the behavior of another semantics to cases where has problems, while remaining identical to otherwise. This relation, called backwards compatibility, can be regarded as a special kind of skepticism comparison: on the one hand, it also considers cases where one of the compared semantics ‘crashes’, and on the other, it requires equality (rather than ⪯) between extensions (labellings).

It holds that both semi-stable semantics and stage semantics are backwards compatible with stable semantics. This is because for argumentation frameworks where at least one stable extension (labelling) exists, the semi-stable extensions (labellings) and the stage extensions (labellings) are the same as the stable extensions (labellings).

4.4 A note on infinite argumentation frameworks

As explicitly stated in Section 2.1, this paper is focused on finite argumentation frameworks and the analysis of semantics properties we have carried out relies on this assumption. One may wonder what is the impact of this restriction and what would be the implications of also considering infinite frameworks. While providing a full answer to this question is beyond the scope of this paper, we observe in particular that in infinite frameworks, the notion of maximality with respect to set inclusion is less immediate than in finite frameworks and the existence of maximal sets of arguments respecting some criterion, which is guaranteed in finite frameworks, may fail to be achieved in infinite ones. As an example of the consequences of this fact, a semantics that is universally defined in the context of finite frameworks may not be so when also considering infinite ones, implying (among other consequences) that the skepticism comparison we have carried out does not extend directly to the infinite case. In fact, we are not aware of any systematic literature analysis of argumentation semantics properties in the infinite case. Concerning in particular the issue of a universal definition, we may recall that the existence of complete, grounded, and preferred extensions is also guaranteed in the infinite case (Dung, Reference Dung1995; Caminada & Verheij, Reference Caminada and Verheij2010). Similarly, it can be proved that the existence of the ideal extension can be guaranteed in the infinite caseFootnote 21. On the other hand, there are examples of infinite frameworks where semi-stable, the eager, and stage extensions do not exist (see Verheij, Reference Verheij1996, Reference Verheij2003; Caminada & Verheij, Reference Caminada and Verheij2010; Weydert, 2011); finally, whether CF2 semantics is universally defined in the infinite case is, as to our knowledge, an open question.

5.1 Semantics for constraint satisfaction

The application domain of constraint satisfaction is mostly predominant in the field of logic programming and answer set programming (Gelfond & Lifschitz, Reference Gelfond and Lifschitz1988, Reference Gelfond and Lifschitz1991). Here, the idea is to provide a formalism that can take a declarative description of a constraint satisfaction problem, in order to calculate its set of solutions. As an example, one could write an answer set program for solving sudokus. The idea is that each resulting answer set of the ASP (answer set programming) program corresponds with a solution of the original problem (in this case: the sudoku). Also, if the original problem does not have any solutions, then one would like to obtain no answer sets. It then follows that one would like to apply a semantics that can yield zero or more extensions, explicitly keeping open the possibility of yielding zero extensions in case the problem that one is trying to model does not have solutions. This naturally leads to the application of stable semantics, and it should therefore not come as a surprise that stable semantics has become the standard in the field of logic programmingFootnote 22.

When one wants to carry out constraint satisfaction, but with the possibility of dealing with flaws and errors in the constraint specification, it makes sense to apply a semantics that satisfies the properties of crash resistance, non-interference, and backwards compatibility with stable semantics, as they were defined in Sections 3.5 and 4.3. In that case, semi-stable semantics and stage semantics would be suitable candidates. Like most semantics discussed in this paper, they satisfy crash resistance and non-interference. However, unlike many other semantics, they are also backwards compatible with stable semantics.

As an aside, it is also possible to define crash resistance, non-interference, and backwards compatibility not just for abstract argumentation, but for general logical formalisms, as is done in Caminada et al. (Reference Caminada2011). For general logical formalisms, crash resistance basically means that no set of formulas can make all syntactically disjoint sets of formulas irrelevant when being merged to it, non-interference means that syntactically disjoint sets of formulas cannot influence each other's entailment when being put together, and backwards compatibility means that a logical formalism yields the same outcome as another formalism in cases where the latter does not ‘crash’. Non-interference implies crash resistance, at least for logical formalisms that satisfy some minimal requirements described in Caminada et al. (Reference Caminada, Carnielli and Dunne2011). Crash resistance, however, does not imply non-interference. As explained in Caminada (Reference Caminada2005), an example of a formalism that satisfies crash resistance but violates non-interference is the oscar system (Pollock, Reference Pollock1995).

When applying the generalized versions of crash resistance, non-interference, and backwards compatibility (defined in Caminada et al., Reference Caminada2011), it can be observed that classical logic violates crash resistance, since every inconsistent set of formulas is contaminating. The research field of paraconsistent logic has been aimed at defining forms of entailment that use the same logical language as classical logic, but satisfy the postulates of crash resistance, non-interference, and backwards compatibility. A paraconsistent logic as proposed in Carnielli et al. (Reference Carnielli, Coniglio and Marcos2002), for instance, satisfies crash resistance and non-interference (implying that inconsistency does not affect totally unrelated formulas) and is backwards compatible with classical logic (meaning that for each set of formulas that is consistent under classical logic, the paraconsistent logic entails the same consequences as classical logic).

An alternative approach to deal with the issue of crash resistance in classical logic would be to consider the models of all maximal consistent subsets of the knowledge base, since this approach also satisfies (the generalized versions of) crash resistance and non-interference, while remaining backwards compatible with classical logic (it yields the same outcome as classical logic in case the knowledge base is consistent).

To some extent, the approach of stage semantics is comparable with the approach of taking maximal consistent subsets of a classical logic knowledge base. In both cases, one applies the original semantics (stable semantics or classical logic semantics) while ignoring part of the original problem description in order to successfully apply these semantics. The approach of semi-stable semantics, on the other hand, can be compared with paraconsistent logic, in that one takes into account the entire problem description and applies a different semantics instead.

5.2 Semantics for reasoning with rules of thumb

When applying reasoning for constraint satisfaction, one starts with a problem that is well understood, and then aims to write a perfect representation in a particular constraint satisfaction formalism (like Answer Set Programming), so that the original problem can be solved in an automated way. However, in many cases, one would like to reason about issues that are perhaps not perfectly understood (like for instance which treatment to give to a patient) and where one has to deal with rules of thumb, which can give reasons in favor of or against drawing a particular conclusion. These rules of thumb are not necessarily perfect, nor do they have to be complete. The challenge, then, is to come up with a reasonable position one can adopt based on imperfect information. This makes it desirable to apply a semantics that satisfies crash resistance and non-interference, since we do not want problems in one part of the knowledge base to affect other, possibly totally unrelated parts of the knowledge base. Stable semantics is therefore not an option.

Would the semantics have to be admissibility based? That is, is it desirable that each extension (labelling) is an admissible (or even complete) one? Again, it is difficult to provide an ultimate answer in general: one has to refer to specific contexts. In particular, in the context of instantiated arguments generated from an underlying logical knowledge base, admissibility can be regarded as advantageous in relation to consistency requirements, as explained in the following.

Suppose one generates an argumentation framework based on a set of propositional formulas and a set of defeasible rules . The idea is that the propositional formulas express information that is beyond doubt and the defeasible rules express rules of thumb that can be subject to exceptions. Now consider the following knowledge base:

This example can be interpreted as follows: John, Mary, and Suzy want to go cycling on a tandem. The fact that John wants to get on the tandem (jw) is a reason to believe that John will be on the tandem (jt). The same holds for Mary and Suzy. However, since the tandem only has two seats, they cannot be on it with the three of them: ¬(jt ∧ mt ∧ st). From this knowledge base, we can then construct the 10 following arguments, based on an argument construction scheme as presented in Caminada and Amgoud (Reference Caminada and Amgoud2007) and Prakken (Reference Prakken2010):

A ₁ = ¬(jt ∧ mt ∧ st)

A ₂ = jw

A ₃ = mw

A ₄ = sw

A ₅ = A ₂ ⇒jt

A ₆ = A ₃⇒mt

A ₇ = A ₄⇒st

A ₈ = A ₆, A ₇, A ₁ → ¬jt

A ₉ = A ₅, A ₇, A ₁ → ¬mt

A ₁₀ = A ₅, A ₆, A ₁ → ¬st

Assuming the principle of restricted rebutting Footnote 23 it would then follow that A ₈ attacks A ₅, A ₉, and A ₁₀, that A ₉ attacks A ₆, A ₈, and A ₁₀, and that A ₁₀ attacks A ₇, A ₈, and A ₉. This yields the argumentation framework of Figure 20.

Figure 20

Conflict-freeness is not enough to obtain consistent conclusions

In the argumentation framework of Figure 20, there are four complete extensions: {A ₁, A ₂, A ₃, A ₄}, {A ₁, A ₂, A ₃, A ₄, A ₆, A ₇, A ₈}, {A ₁, A ₂, A ₃, A ₄, A ₅, A ₇, A ₉}, and {A ₁, A ₂, A ₃, A ₄, A ₅, A ₆, A ₁₀}. The first of these is the grounded extension; the other three are stable extensions (and therefore also semi-stable and preferred extensions). It should be mentioned that the sets of conclusions associated with these extensions are consistent: {jw; mw; sw; ¬(jt ∧ mt ∧ st)}, {jw; mw; sw; ¬(jt ∧ mt ∧ st); mt; st; ¬jt}, {jw; mw; sw; ¬(jt ∧ mt ∧ st); jt; st; ¬mt}, and {jw; mw; sw; ¬(jt ∧ mt ∧ st); jt; mt; ¬st}. Now let us examine what happens if one lowers the requirement of admissibility to the mere property of conflict-freeness. In that case, we lose consistency, since the set of arguments {A ₅, A ₆, A ₇, A ₁} is conflict-free and yet its associated set of conclusions {jt; mt; st; ¬(jt ∧ mt ∧ st)} is inconsistent. It is therefore important to notice that conflict-freeness by itself does not imply consistency; in order to yield consistent conclusions, something stronger is needed. In Caminada and Amgoud (Reference Caminada and Amgoud2007), it is proved that, under the right procedure of argument construction, admissibility of a set of arguments is a condition that is strong enough to yield consistent conclusions of this set.

What does this mean for non-admissibility-based semantics, such as stage or CF2? First of all, it should be mentioned that the above-described example is not a counter example against stage semantics or CF2 semantics. This is because the stage extensions (and CF2 extensions) are {A ₁, A ₂, A ₃, A ₄, A ₆, A ₇, A ₈}, {A ₁, A ₂, A ₃, A ₄, A ₅, A ₇, A ₉}, and {A ₁, A ₂, A ₃, A ₄, A ₅, A ₆, A ₁₀}, which yield consistent conclusions.

For stage semantics, it is possible to come up with a slightly more complex example where a stage extension does yield inconsistent conclusions. Such an exampleFootnote 24 could be constructed by adopting the argumentation framework of Figure 20 and adding three self-attacking arguments A ₈, A ₉, and A ₁₀, where A ₈ is also attacked by A ₅, A ₉ by A ₆, and A ₁₀ by A ₇. Such arguments could be constructed by using the notion of self-undercut, like is done in Caminada (Reference Caminada2005).

As for CF2 semantics, a counterexample against its consistency has been discovered by Wolfgang Dvořák (private communication). Basically, the idea is to add three defeasible rules . This yields three additional arguments in the argumentation framework of Figure 20: . It then follows that A ₅ attacks attacks . In the resulting argumentation framework, will be one of the CF2 extensions, yielding the inconsistent set of conclusions . For those applications where consistency is important, it could have advantages to be on the safe side and choose a semantics that is guaranteed to yield consistent conclusions, hence to choose a semantics that is admissibility based.

On the other hand, as discussed in Section 2.10, admissibility is incompatible with a ‘balanced’ treatment of even-length and odd-length attack cycles. An example of a formalization where this kind of balanced behavior is desirable has been given in Baroni et al. (Reference Baroni, Giacomin and Guida2005). In these contexts, one might prefer to give up admissibility and then adopt CF2 semantics.

When using argumentation for reasoning with rules of thumb, it also seems reasonable that the status of an argument depends only on the arguments that are ‘upstream’ in the argumentation framework (attackers, attackers of attackers, etc.) and that the semantics should therefore satisfy the directionality principle (Section 3.5). If one restricts oneself to admissibility-based semantics, the candidates are complete, grounded, preferred, and ideal semantics; otherwise, CF2 can also be considered. In the former case, which of these semantics to choose is to some extent a matter of taste. If one would like to entail as much as possible, preferred semantics would be the most obvious choice, since this semantics is the least skeptical among the four. Similarly, if one would like to entail as little as possible, grounded semantics would be selected.