In this chapter, we introduce two approaches for defining the semantics of an abstract argumentation framework: extension-based approach and labelling-based approach. The idea underlying the extension-based approach is to identify sets of arguments, called extensions, that can be regarded as collectively acceptable according to some criterion. The idea underlying the labelling-based approach is to assign a label to each argument, according to a certain criterion. It has been verified that under most of argumentation semantics, there exists a bijective correspondence between sets of extensions and a set of labellings of an argumentation framework.
abstract argumentation frameworks; argumentation semantics; extensions; justification status; labellings; status of arguments
Given a set of conflicting arguments, whether an argument can be accepted depends on the existence of some counter arguments, which may in turn have counter arguments, and so on. In order to capture the attack relation between arguments and facilitate the status evaluation of arguments, Phan Minh Dung proposed abstract argumentation theory in 1995 [1]. He introduced a notion of abstract argumentation framework. An abstract argumentation framework can be regarded as a directed graph where the nodes represent arguments and the arcs represent attacks. Given such a graph, a fundamental problem is to determine which arguments can be regarded as acceptable. According to existing literature, there are mainly two approaches to deal with this problem: extension-based approach and labelling-based approach. Both approaches aim at defining argumentation semantics. An argumentation semantics can be viewed as a pre-defined criterion, according to which the acceptability of arguments in an argumentation framework can be determined.
In this chapter, after the notion of an abstract argumentation framework is introduced, some mainstream semantics defined by the two approaches are formulated.
The notion of abstract argumentation frameworks (briefly, argumentation frameworks, or AFs) is central to abstract theory of argumentation. As mentioned above, in order to reflect the conflicting relation of arguments and facilitate the status evaluation of arguments, the structures of arguments and the origins of attacks that are irrelevant to the status evaluation of arguments are omitted. As a result, an argumentation framework is simply represented as a directed graph (called a defeat graph) where nodes represent arguments and arcs represent attacks between them. Formally, an argumentation framework is defined as follows.
In Definition 2.1, we use to denote that attacks (with respect to ). Meanwhile, throughout this book, we assume that is generated by a reasoner at a given time point, and therefore is finite.
Let be a set of arguments, and be an argument. As usual, we say that attacks if and only if there exists such that attacks . Meanwhile, we say that attacks if and only if there exists such that attacks .
In a defeat graph, the nodes that attack a given argument are called defeaters (or parents) of [2]. Given and a set of arguments, we use to denote the set of outside parents of the arguments in (when is called an unattacked set).
(2.1)
Since there exist conflicts between arguments, to determine whether or not an argument is acceptable, the status of all its defeaters should be considered, while the status of each defeater is in turn determined by the status of its defeaters, and so on. When an argument is attacked by an argument , and is in turn attacked by an argument , then we say that reinstates . Whether an argument is able to reinstate another argument (or itself) is related to some specific criterion, which is called argumentation semantics. Given an argumentation framework, under a certain argumentation semantics, zero or more sets of arguments are considered acceptable.
In existing literature, there are two approaches to formulate the status of arguments in an argumentation framework: extension-based approach and labelling-based approach. The idea underlying the extension-based approach is to identify sets of arguments, called extensions, that can be regarded as collectively acceptable according to some criterion. The idea underlying the labelling-based approach is to assign a label to each argument, according to a certain criterion.
In this chapter, we will introduce some basic notions related to argumentation semantics, defined by the above-mentioned two approaches. Readers may refer to [3] for an excellent introduction.
In the extension-based approach, under different semantics which represent different evaluation criteria, an argumentation framework may have different sets of extensions. In this section, the following semantics will be introduced: admissible, complete, grounded, preferred, stable, semi-stable, eager and ideal.
The notion of admissible is fundamental to the definitions of other semantics. It is defined on the basis of the following two notions: conflict-free and acceptable.
Conflict-freeness is viewed as a minimal requirement of any argumentation semantics.
However, conflict-freeness is too weak a condition to justify that a set of arguments is “collectively acceptable”, since such a set could be attacked by arguments not among its members.
Acceptability is another important requirement for the arguments that constitute an admissible extension.
Based on the notions of conflict-freeness and acceptability, an admissible extension can be defined as follows.
As illustrated in Example 2.2, it is not the case that each admissible extension contains all arguments that are acceptable with respect to the extension. For instance, with respect to , the argument is acceptable, but it is not in .
Given an argumentation framework and an admissible extension , if there exists an argument such that is acceptable with respect to , then we add to , and get a new set . Then, with respect to , if there exists an argument such that is acceptable with respect to , then we add to , and get a new set . In this way, if is a finite set, then we will finally get a set that is admissible and contains all arguments that are acceptable with respect to this set. This process can be defined by a function, called characteristic function, defined as follows.
Given an admissible set , if , then is called a complete extension. Formally, we have the following definition.
Under complete semantics, some argumentation frameworks may have more than one extension. Let us consider the following example.
As mentioned above, under complete semantics, there might exist several extensions. The arguments in different extensions might be conflicting, and therefore questionable. If we only accept those arguments that are least questionable, then we get an extension (called grounded extension) that is the most skeptical among all complete extensions. On the contrary, if we want to accept as many arguments as reasonably possible, then we get sets of extensions (called preferred extensions) that are more credulous than some other complete extensions.
According to Example 2.4, the argument is acceptable with respect to all extensions, while the arguments and are not. So, under grounded semantics, one may only regard as an acceptable argument, while under preferred semantics, one may regard and (or and ) as acceptable arguments.
According to [1], for any argumentation framework, there exists a unique grounded extension, while for some argumentation frameworks, there might exist multiple preferred extensions.
Grounded extension can be obtained by recursively applying characteristic function from an empty set.
Hence, the grounded extension of is .
Alternatively, the grounded extension of an argumentation framework can be defined as follows.
Under the above-mentioned semantics, with respect to a given extension, the status of some arguments could be undecided, which means that they are neither accepted, nor rejected, with respect to the extension. Here, we say that an argument is accepted with respect to an extension, if it belongs to this extension; an argument is rejected with respect to an extension if it is attacked by the extension.
Now, given a set of conflict-free arguments, if we require that there are no arguments that are undecided with respect to this set, then it is called a stable extension. Formally, we have the following definition.
In [1], it has been proved that every stable extension is a preferred extension, but not vice versa.
Stable semantics is interesting, since it exactly corresponds to the extensions defined in some traditional non-monotonic formalisms, such as Reiter’s default logic, Moore’s autoepistemic logic and logic programming. However, some argumentation frameworks may have no stable extension.
Since under stable semantics there is a possibility that stable extensions may not exist, Martin Caminada proposed a revised semantics, called semi-stable semantics. This semantics is “backward compatible” to stable semantics in the sense that it is equivalent to stable semantics in situations where stable extensions exist, and still yields a reasonable result in situations where stable extensions do not exist [4]. Compared to stable semantics, semi-stable semantics does not require that the set of undecided arguments is empty, but merely requires that the set of undecided arguments is minimal.
It has been verified that every stable extension is a semi-stable extension, and every semi-stable extension is a preferred extension.
As illustrated in Example 2.5, an argumentation framework may have several preferred extensions, and some arguments in different extensions might conflict. More specifically, and are respectively in and , but they are conflicting. This is because preferred semantics is credulous. In many cases, it is better to adopt a semantics that is more skeptical. The above-mentioned grounded semantics is skeptical. However, it is often overly skeptical, in that in many cases, the grounded extension could be an empty set. In order to treat this problem, another skeptical semantics, called ideal semantics, was proposed in [5]. It defines an ideal extension as an admissible extension that is a subset of every preferred extension. Generally, ideal semantics is less skeptical than grounded semantics, but more skeptical than preferred semantics. Formally, we have the following definition.
Example 2.10 shows that the ideal extension is the same as the grounded extension. Meanwhile, the intersection of the preferred extensions is equal to the ideal extension. However, this coincidence does not happen in all cases. Please consider the following example (Figure 2.4).
Besides grounded semantics and ideal semantics, the third skeptical semantics that is very close to ideal semantics is eager semantics. While the ideal extension is the biggest admissible subset of each preferred extension, the eager extension is the biggest admissible subset of each semi-stable extension.
In labelling-based approaches, there are usually three labels: IN, OUT and UNDEC, where the label IN means the argument is accepted, the label OUT means the argument is rejected and the label UNDEC means one abstains from an opinion on whether the argument is accepted or rejected [3]. Meanwhile, there could be some other choices for the set of labels. For instance, in [6], four-valued labelling is considered. In this book, we choose three-valued labelling. Formally, labelling is defined as follows [7].
The set of all labellings of is denoted as .
Let , and . A labelling is often represented as a triple of the form .
One of the criteria for labelling-based semantics is whether a label assigned to an argument is legal. According to Definition 2.12, given a labelling , the status assigned to each argument might not be legal. We say that assigning the IN label to an argument is legal if and only if all its attackers have been assigned the OUT label; assigning the OUT label to an argument is legal if and only if one of its attackers has been assigned the IN label; and assigning the UNDEC label to an argument is legal if and only if not all its attacks are labelled OUT and it does not have an attacker that is labelled IN. Based on [8], we have the following definition.
According to the notion of legal labelling, the notion of illegal labelling can be defined as follows.
Based on the notions of labelling as well as legal/illegal labelling, various labelling-based semantics corresponding to the above-mentioned extension-based semantics can be defined as follows.
Admissible labeling is defined on the basis of conflict-free labelling. According to Definition 2.2, when a set of arguments is conflict-free, there exists no attack between the arguments in the set. So, given a labelling , each argument in should not have an attacker in . Meanwhile, only those arguments that are attacked by at least one argument in are labelled OUT. So, all OUT-labelled arguments are legally OUT.
From this example, we may observe that a conflict-free set might correspond to several conflict-free labellings.
According to Definition 2.15, not all IN-labelled arguments are legally IN. Given a conflict-free labelling, if each IN-labelled argument is legally IN, then it is called an admissible labelling.
Given an admissible labelling, if each UNDEC-labelled argument is legally UNDEC, then it is called a complete labelling. Formally, we have the following definition.
Given a complete labelling, if the set of IN-labelled arguments is minimal (respectively, maximal), then it is called a grounded labelling (respectively, preferred labelling). Formally, we have the following definition.
The definition of ideal labelling is more complex. According to [9], in order to define the ideal labelling of an argumentation framework, we need to introduce the following notion [10].
The relation “” defines a partial order (reflective, anti-symmetric, transitive) on the labellings of an argumentation framework.
As introduced in [3], under most of argumentation semantics, there is a bijective correspondence between the set of labellings and sets of extensions of an argumentation framework. On the one hand, given an argumentation framework, the labels IN can be understood as identifying the members of an extension. According to [3], we have the following definition.
On the other hand, given an extension of an argumentation framework, if it is conflict-free, then we may construct a labelling such that the arguments belonging to are labelled IN, those attacked by some arguments of are labelled OUT, and those which neither belong to E nor are attacked by are labelled UNDEC. Formally, we have the following definition.
As proved in [8], there is a correspondence between admissible sets and admissible labellings.
It should be noticed that the correspondence between admissible sets and admissible labellings is not bijective. This is because different admissible labellings may correspond to the same admissible set. For instance, with respect to in Example 2.4, and are two admissible labellings. Both of them give rise to the same admissible set .
Except admissible semantics, under other semantics introduced above, there exists a bijective correspondence between sets of extensions and a set of labellings, of an argumentation framework.
In this book, we use to denote a semantics, which could be admissible , complete , preferred , grounded , stable , semi-stable , ideal or eager . Based on these notations, we have the following proposition.
With respect to the extension-based approach, the relations between different argumentation semantics introduced above can be illustrated in Figure 2.5. According to Definitions 2.4 and 2.6, it holds that a complete extension is an admissible set. According to Definition 2.7, a grounded extension (respectively, a preferred extension) is a complete extension. Meanwhile, as proved in [10], an ideal extension (respectively, eager extension) is also a complete extension. Finally, according to [4], every stable extension is also a semi-stable extension, which in turn is a preferred extension. Given an argumentation framework, its eager extension is a superset of its ideal extension, which is in turn a superset of its grounded extension. So, the grounded semantics is the most skeptical semantics mentioned above. On the other hand, as to the labelling-based approach, we have similar results.
According to the extensions (labellings) of an argumentation framework, the status of arguments can be determined. Given a labelling, the status of each argument with respect to this labelling is IN, OUT, or UNDEC.
On the other hand, from the perspective of the extension-based approach, the status of arguments is determined by an extension, rather than a labeling. As presented in Definition 2.23, when an extension is conflict-free, it can be mapped to a labelling. Hence, given an argumentation framework and a conflict-free extension of it, for each argument within the argumentation framework, we may differentiate three status: accepted, rejected and undecided, corresponding to IN, OUT and UNDEC in the labelling-based approach.
Informally, an argument is accepted with respect to an extension, if and only if it belongs to this extension; an argument is rejected with respect to an extension, if and only if it is attacked by another argument that is accepted with respect to this extension; an argument is undecided with respect to an extension, if and only if it is neither accepted nor rejected with respect to this extension. Here, the extension should be conflict-free. Otherwise, the above three classes of status could not be differentiated. For instance, consider an argumentation framework . Suppose that is an extension. It follows that is both accepted (because it belongs to ) and rejected (because it is attacked by that is accepted with respect to ).
Beside the status of arguments with respect to an extension or a labelling, we may evaluate the status of arguments with respect to sets of extensions or a set of labellings, call the justification status of arguments. Since under some argumentation semantics, an argumentation framework might have multiple extensions (labellings), the justification status of an argument could be sceptically justified, credulously justified, and indefensible. An argument is sceptically justified, if it belongs to each extension (labelling); an argument is credulously justified, if it belongs to some (at least one) extensions (labellings) and does not belong to some other (at least one) extensions (labellings); an argument is indefensible, if it does not belong to any extension (labelling). Formally, we have the following definition.
In this chapter, we have introduced the notion of abstract argumentation frameworks and the semantics of an argumentation framework from the perspective of an extension-based approach and that of a labelling-based approach, respectively. Under most semantics (complete, preferred, grounded, stable, semi-stable, ideal and eager), there is a bijective correspondence between sets of extensions and a set of labellings.
Under a given semantics, an argumentation framework may have a unique extension or multiple extensions. If under a semantics , any argumentation framework has only one extension, then it is called a unique-status semantics; otherwise, it is called a multiple-status semantics. Grounded, ideal and eager are three unique-status semantics introduced in this chapter. Among them, the grounded semantics is the most skeptical one, the ideal semantics is the second, and the eager semantics is the third. On the other hand, admissible, complete, preferred, stable and semi-stable are multiple-status semantics. Under stable semantics, an argumentation framework might have an empty set of extension. Semi-stable semantics was proposed to handle this problem.
Based on the definition of argumentation semantics, given an argumentation framework, an important problem is to efficiently compute the status of arguments. In the subsequent chapters, we will focus on this problem.
1. Dung PM. On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. Artificial Intelligence. 1995;77(2):321–357.
2. Baroni P, Giacomin M. On principle-based evaluation of extension-based argumentation semantics. Artificial Intelligence. 2007;171(10–15):675–700.
3. Baroni P, Caminada M, Giacomin M. An introduction to argumentation semantics. The Knowledge Engineering Review. 2011;26(4):365–410.
4. Caminada M. Semi-stable semantics. In: Proceedings of First International Conference on Computational Models of Argument. 2006;121–130.
5. Dung PM, Mancarella P, Toni F. Computing ideal sceptical argumentation. Artificial Intelligence. 2007;171(10–15):642–674.
6. Jakobovits H, Vermeir D. Robust semantics for argumentation frameworks. Journal of Logic and Computation. 1999;9(2):215–261.
7. Caminada M. On the issue of reinstatement in argumentation. In: Proceedings of the 10th European Conference on Logics in Artificial Intelligence. 2006;111–123.
8. Caminada M, Gabbay Dov. A logical account of formal argumentation. Studia Logica. 2009;93(2–3):109–145.
9. Caminada M. A labelling approach for ideal and stage semantics. Argument & Computation. 2011;2(1):1–21.
10. Caminada M, Pigozzi G. On judgment aggregation in abstract argumentation. Journal of Autonomous Agents and Multi-Agent Systems. 2011;22(1):64–102.