An Approach for Partial Semantics of Argumentation
Abstract
In various argumentation systems, under most situations, only the status of some arguments of the systems should be evaluated, while that of others does not necessarily need to be figured out. Based on this observation, we first introduce an efficient method to evaluate the status of a part of arguments in an abstract argumentation framework. Given an argumentation framework and a subset of arguments within it, the minimal set of arguments that are relevant to this subset (called the set of relevant arguments of the subset) is identified. The set of extensions of the sub-framework induced by the set of relevant arguments of the given subset (called a partial semantics of the argumentation framework with respect to this subset) is evaluated locally. Then, we introduce three basic properties of the partial semantics of argumentation: monotonicity, extensibility and combinability, which lay a foundation for developing efficient algorithms for the status evaluation of a part of arguments in an argumentation framework. Finally, we conduct an empirical investigation on the properties of computing the partial semantics of argumentation using answer-set programming. The average results show that the computational benefits of this method are closely related to the edge density of the defeat graph of a given argumentation framework.
Keywords
abstract argumentation frameworks; answer set programming; argumentation semantics; computational complexity; local computation
8.1 Introduction
When querying the status of some arguments in an abstract argumentation framework, we may only take into consideration a subset of arguments in the argumentation framework that are relevant to these arguments. This phenomenon appears in many situations. Let us consider the following two examples.
First, when developing proof theories and algorithms for argumentation frameworks [1], for a given semantics, there are some “local” questions concerning the existence of extensions with respect to a subset 
of arguments, such as:
(a) Is 
contained in an extension? (credulous membership question)
(b) Is 
contained in all extensions? (skeptical membership question)
attacked by an extension?
attacked by all extensions?When answering these “local” questions, we might not have to figure out the extensions of a whole framework, but the extensions of a part of the framework.
Example 8.1
Let 
be an abstract argumentation framework (Figure 8.1). Given 
, according to the directionality of argumentation semantics, only the status of 
and 
may affect the status of 
and 
. In other words, when computing the status of arguments in 
, we may only consider the set 
of arguments.
.Second, when agents engage in dialogues, they have goals to make some arguments (say, a set 
of arguments) acceptable or unacceptable [2]. At each turn, an agent may choose some arguments from a set of available arguments, and add them to the framework. For each addition, the status of arguments of the framework may change accordingly. However, since only the status evolution of arguments in 
is necessary to be figured out, other arguments that are irrelevant to 
may not be taken into consideration.
Example 8.2
For the 
in Example 8.1, suppose that an agent wants to make 
skeptically accepted under preferred semantics, and she owns a set of arguments 
and the set of associated attacks 
. Since only the status of 
and 
may affect the status of 
, the agent may not consider 
, which has no effect on the status of 
. Meanwhile, when 
and the associated attacks 
and 
are added to 
, although the status of arguments 
and 
is also affected by the addition, they may not be involved in the computation, in that they have no effect on the status of 
(and therefore are irrelevant to 
).
Inspired by the above phenomenon, we propose a general approach to efficiently evaluate the status of a part of arguments in an argumentation framework. The basic idea of this method is as follows.
Given an argumentation framework and a subset 
of arguments within it, we firstly identify the minimal set of arguments that are relevant to the arguments in 
(called the set of relevant arguments of 
). Then, under a semantics under which the mappings between global semantics and local semantics are sound and complete, the set of extensions of the sub-framework that is induced by the set of relevant arguments of 
(called a partial semantics of the argumentation framework with respect to 
) can be evaluated locally.
8.2 The Definition of Partial Semantics of Argumentation
As illustrated in Example 8.1, given 
and 
, only those arguments, each of which is in 
or has a path to the arguments in 
, might be relevant to the status of arguments in 
. For convenience, we call them the set of relevant arguments of 
, denoted as 
.
Definition 8.1
Given 
and 
, the set of relevant arguments of 
is defined as follows:
Example 8.3
Continue Example 8.1. Given 
, according to Definition 8.1, 
. In addition, given 
and 
, we have 
, and 
.
Based on Definition 8.1, some basic properties of the set of relevant arguments of a given subset are formulated in the following proposition.
be an abstract argumentation framework, and 
sets of arguments. It holds that:
;
, i.e., 
is an unattacked set;
, then 
;
.Proof
(2) Assume the contrary. Then, 
, such that 
attacks an argument 
in 
. It follows that there is a path from 
to 
. If 
, according to Definition 8.1, 
, contradicting “
” (i.e., 
). Otherwise, if 
, then: according to Definition 8.1, 
, such that there is a path from 
to 
. It follows that there is a path from 
to 
, and therefore 
, contradicting “
”.
(3) Given 
, according to Definition 8.1, it is obvious that 
.
and 
, it holds that 
.On the other hand, 
, according to Definition 8.1, there are two possible cases:
(a) 
. In this case, since 
, it holds that 
.
(b) 
, such that there is a path from 
to 
. In this case, 
(when 
) or 
(when 
), i.e., 
.
In both cases, it holds that 
. It follows that 
.
Since 
and 
, we have 
.
Since 
is an unattacked set, we may use 
to induce an unconditioned sub-framework of 
, in which 
. Under a semantics 
, the extensions of 
can be computed locally. We call 
a partial semantics of 
with respect to 
.
Definition 8.2
Let 
be an abstract argumentation framework, 
a set of arguments, and 
the set of relevant arguments of 
. Under a semantics 
, the partial semantics of 
with respect to 
is defined as 
.
Proposition 8.2
Let 
be an abstract argumentation framework, and 
a set of arguments. Under a semantics 
, for every argument 
is skeptically justified (respectively, credulously justified and indefensible) with respect to 
, if and only if 
is skeptically justified (respectively, credulously justified and indefensible) with respect to 
.
Proof
• If 
is skeptically justified with respect to 
, then 
. Assume that 
, such that 
. Since 
, according to the theories presented in Chapter 5, 
. It follows that 
, such that 
. Since 
and 
, it holds that 
, contradicting “
”. Therefore, 
, i.e., 
is skeptically justified with respect to 
.
• If 
is credulously justified with respect to 
, then 
, such that 
. According to the theories presented in Chapter 5, 
. Since 
and 
, it holds that 
. In other words, there exists an extension in 
, such that 
is in this extension, i.e., 
is credulously justified with respect to 
.
• If 
is indefensible with respect to 
, then 
. Assume that 
, such that 
. As mentioned in the first item, 
. It follows that 
, such that 
. Since 
, it holds that 
, contradicting “
”. Therefore, 
, i.e., 
is indefeasible with respect to 
.
• If 
is skeptically justified with respect to 
, then for all 
. Assume that 
, such that 
. According to the theories presented in Chapter 5, 
. Since 
, it holds that 
, contradicting “
”. Therefore, 
, i.e., 
is skeptically justified with respect to 
.
• If 
is credulously justified with respect to 
, then there exists 
, such that 
. Assume that 
, such that 
. Since 
, according to the theories presented in Chapter 5, 
. It follows that 
, such that 
. Since 
, it holds that 
, contradicting “
”. Therefore, 
, such that 
, i.e., 
is credulously justified with respect to 
.
• If 
is indefeasible with respect to 
, then for all 
. Assume that 
, such that 
. According to the theories presented in Chapter 5, 
. Since 
and 
, it holds that 
, contradicting “
”. Therefore, 
, i.e., 
is indefeasible with respect to 
.
According to this proposition, when querying the justification status of some arguments in an argumentation framework, we only need to compute the partial semantics of the argumentation framework with respect to these arguments.
Example 8.4
Continue Example 8.3. Let us consider the following two approaches.
Firstly, use the partial semantics of 
to evaluate the status of arguments in 
and 
, respectively.
Under preferred semantics,
According to these partial semantics, it holds that 
and 
are credulously justified with respect to 
is skeptically justified with respect to 
, and 
is indefensible with respect to 
.
Secondly, use the (whole) semantics of 
to evaluate the status of the above-mentioned arguments. Under preferred semantics,
It holds that 
and 
are credulously justified, 
is skeptically justified, and 
is indefensible, with respect to 
. According to Proposition 8.2, the results of these two approaches are the same. However, the latter is obviously more complex.
8.3 Basic Properties of Partial Semantics of Argumentation
According to the previous section, given 
and 
, we may compute the partial semantics of 
with respect to 
independently, without computing the status of other arguments that are irrelevant to 
. Furthermore, it is desirable that after the partial semantics of 
with respect to some sets of arguments obtained, they can be reused in the subsequent computation. This vision is embodied by the following three basic properties of partial semantics of argumentation: monotonicity, combinability and extensibility.
8.3.1 Monotonicity of Partial Semantics
Given 
and 
, the monotonicity of partial semantics of argumentation can be informally expressed as:
If 
, then the justification status of each argument in 
evaluated with respect to 
is the same as the one evaluated with respect to 
.
Since 
and 
is an unattacked set (according to Proposition 8.1), 
is an unconditioned sub-framework of 
. Given a semantics 
under which there exist sound and complete mappings between global semantics and local semantics, 
can be regarded as a partial semantics of 
with respect to 
. According to Proposition 8.2, we directly have the following corollary.
Corollary 8.1
Given 
and 
, if 
, then: under a semantics 
, for every argument 
is skeptically justified (respectively, credulously justified and indefensible) with respect to 
, if and only if 
is skeptically justified (respectively, credulously justified and indefensible) with respect to 
.
The above property indicates that after we get the partial semantics of 
with respect to 
(i.e., 
), we may evaluate the justification status of arguments in 
with respect to 
directly, and do not need to compute the partial semantics of 
with respect to 
.
8.3.2 Extensibility of Partial Semantics
Given 
and 
, the extensibility of partial semantics of argumentation can be informally expressed as follows:
If 
, then the partial semantics of 
with respect to 
can be extended to form the partial semantics of 
with respect to 
.
Let 
denote the complement of 
in 
. Given that the partial semantics of 
with respect to 
has been obtained, is it feasible to first compute the partial semantics of 
with respect to 
, and then combine it with the former to form the partial semantics of 
with respect to 
?
As we know, under a semantics 
, if 
is an unattacked set, then the partial semantics of 
with respect to 
can be computed independently. However, this condition might not hold in many cases. Let us consider the following example.
Example 8.5
With respect to 
in Figure 8.1, let 
and 
. It follows that 
and 
. Let 
. We have 
, and 
. So, 
is not an unattacked set, and the sub-framework induced by 
is a conditioned sub-framework (as shown in Figure 8.2(b)). In other words, since the status of arguments in 
is related to the status of some arguments outside 
(i.e., 
), the extensions of the sub-framework induced by 
can not be computed independently.
Figure 8.2 Two sub-frameworks of 
: the sub-framework induced by 
(a) is an unconditioned sub-framework, whose extensions can be computed according to Definition 2.2, while the sub-framework induced by 
(b) is a conditioned sub-framework, which is conditioned by some arguments outside the sub-framework.
Then, we may first construct a conditioned sub-framework for 
. Since 
is contained in 
(in other words, 
), the set of conditioning arguments of 
is equal to 
. So, the conditioned sub-framework for 
is 
, in which 
and 
.
Then, we need to prove that 
is contained in 
, so that the status of arguments in 
can be assigned according to the extensions of 
. For this purpose, we have the following proposition.
Proposition 8.3
Let 
be an abstract argumentation framework, 
sets of arguments, and 
the complement of 
in 
. If 
, then 
.
Proof
Assume that 
, such that 
. Since 
and 
, according to Formula 2.1, it holds that 
, and 
, such that 
.
Since 
, and 
, it holds that 
, and therefore 
.
Since 
and 
, it holds that 
and 
. By 
, we have the following two possible cases:
(a) 
. In this case, since 
(there is a path from 
to 
with respect to 
) and 
, according to Definition 8.1, 
, contradicting 
.
(b) 
. In this case, 
, such that there is a path from 
to 
. It follows that there is a path from 
to 
. According to Definition 8.1, 
, contradicting 
.
So, 
, i.e., 
.
Since 
is contained in 
is a conditioned sub-framework with respect to 
. For all 
, we get a partially assigned sub-framework: 
. After the extensions of all partially assigned sub-frameworks are obtained, we combine them with the extensions of 
to form the extensions of 
. Formally, for all 
, we have
(8.1)
Formula 8.1 indicates that the partial semantics of 
with respect to 
is obtained by extending the partial semantics of 
with respect to 
.
Example 8.6
Continue Example 8.5. The conditioned sub-framework for 
is represented as 
.
Under preferred semantics, 
, in which 
, and 
.
According to every extension of 
, each argument in 
is assigned with a unique status, and we get 
and 
, in which 
and 
. The corresponding two partially assigned sub-frameworks (Figure 8.3) are represented as follows:
Under preferred semantics, the extensions of the two partially assigned sub-frameworks are computed:
According to Formula 8.1, the partial semantics of 
with respect to 
is as follows: 
, where 
.
is assigned with “accepted” (according to 
) in the first PASF, and with “rejected” (according to 
) in the second PASF.8.3.3 Combinability of Partial Semantics
Given 
and 
, the combinability of partial semantics of argumentation can be informally expressed as follows:
The combination of partial semantics of 
with respect to 
and the one with respect to 
is equal to the partial semantics of 
with respect to 
.
Definition 8.3
Given 
, let 
denote the intersection of 
and 
. Under a semantics 
, the combination of partial semantics of 
with respect to 
and the one with respect to 
, denoted as 
, is defined as follows:
According to Proposition 5.2, under a semantics 
, it holds that 
. According to this property, after we get the partial semantics of 
with respect to some subsets of 
respectively, we may get the partial semantics of a larger subset of arguments by means of semantics combination.
Example 8.7
Given 
, according to Examples 8.4 and 8.6, we have:
Let 
. 
. Under preferred semantics, the partial semantics of 
with respect to 
can be obtained by means of semantics combination:
8.4 Empirical Investigation
In this section, we conduct an empirical investigation on the properties of using ASP to compute the partial semantics of argumentation.
As presented in Chapter 3, different encodings for various argumentation semantics have been proposed, including [3–5]. In this chapter, we take Egly et al’s encodings [4] as an example, and consider the encoding under preferred semantics.
In order to evaluate the properties of computing the partial semantics of argumentation, we developed a Java program based on a Java wrapper for DLV.1 The DLV Wrapper is an Object-Oriented library that “wraps” up the DLV system2 in a Java program. In other words, the DLV Wrapper acts as an interface between Java programs and the DLV system.
The program first generates at random an argumentation framework (a defeat graph) with a given edge density (1%, 2%, 
, 20%) and a given size of the graph (50, 55, 
, 100). Here, the edge density of a defeat graph 
can be defined as follows:
(8.2)
Informally, the edge density of a given defeat graph denotes the percentage of its edges out of all possible edges between nodes.
Then, given the number of arguments to be queried (1, 10 percent of the number of nodes, or 20 percent of the number of nodes), the set of arguments to be queried is generated at random. And then, according to the set of arguments to be queried, the set of arguments belonging to the unattacked set is generated, and the sub-framework induced by the unattacked set is constructed subsequently. Finally, the preferred extensions of the argumentation framework, and of the sub-framework induced by the unattacked set, are computed respectively.
This program was tested on a machine with an Intel CPU running at 1.86 GHz and 1.98 GB RAM. The following three aspects of execution time were measured: the time for generating an unattacked set and constructing a sub-framework induced by the unattacked set, the time for computing the extensions of the argumentation framework, and the time for computing the extensions of the sub-framework induced by the unattacked set.
For convenience, the following notions are used: “
%-whole [
]”, denoting the time for computing the extensions of the (whole) argumentation framework whose edge density is 
% and the number of nodes is 
; “
%-part-q1 [
]” (respectively “
%-part-q10% [
]”, and “
%-part-q20% [
]”), denoting the time for generating an unattacked set, constructing a sub-framework induced by the unattacked set, and computing the extensions of the sub-framework, of the argumentation framework whose edge density is 
% and the number of nodes is 
, when the number of arguments to be queried is 1 (respectively, 10 percent of the number of nodes, and 20 percent of the number of nodes).
For each configuration with a certain edge density and node number, the program was executed 20 times, and the average execution time of different aspects was obtained.
Table 8.1 shows the execution time in the case where the edge density of argumentation frameworks is 2% and the number of nodes is 85. We found that in some cases, the execution time might be much higher than the ones in other cases (in Table 8.1, the execution time of rows 5 and 8 is much higher than that of others). In order to reflect the situations in most cases, the average execution time is revised by dropping the cases where the execution time of computing the extensions of the (whole) argumentation framework is 3 times more than the average of remaining cases.
Table 8.1
The execution time of the case where the edge density of argumentation frameworks is 2% and the number of nodes is 85.
In Figure 8.4, we present the execution time when the number of nodes is from 50 to 100 and the edge density of argumentation frameworks is 1%, 2%, 3% and 20%, respectively. When the edge density of an argumentation framework is 1%, which means that when the size of the argumentation framework is 100, the ratio of nodes to edges is 1:1, the average time for computing the partial semantics is much lower than that of computing the semantics of the whole argumentation framework. With the increase of edge density, the average time for computing the partial semantics becomes closer and closer to that of computing the semantics of the whole argumentation framework. When the number of nodes is from 50 to 100 and the edge density is no less than 6%, the average time for computing the partial semantics is almost equal to that of computing the semantics of the whole argumentation framework. Then, with the increase of edge density, the relation between these two kinds of execution time remains the same. This phenomenon can be well explained by Figure 8.5 and Table 8.2.
Figure 8.4 Plots showing the average execution time (revised by dropping some cases where the execution time of computing the extensions of the whole argumentation framework is 3 times more than the average execution time in remaining cases) when the edge density of argumentation frameworks is 1%, 2%, 3% and 20%, respectively.
Figure 8.5 Plots showing the relation between the ratio of the average size of the unattacked set to the number of the nodes, of an argumentation framework, and the edge density of the argumentation framework. The notation “q1 [
]” (“q10% [
]”) denotes the case where the number of nodes in the argumentation framework is 
, and the number of arguments to be queried is 1 (respectively, 10 percent of the number of nodes).
Table 8.2
The execution time for generating an unattacked set and constructing a sub-framework induced by the unattacked set. The notation “
-q10%” denotes the time for generating an unattacked set and constructing a sub-framework induced by the unattacked set, of the argumentation framework whose edge density is 
%, when the number of arguments to be queried is 10 percent of the number of nodes.
Figure 8.5(a) and (b) shows that in the cases where the edge density of an argumentation framework is no less than 6%, the size of the unattacked set is equal to the number of all nodes in the argumentation framework. In these cases, it is obvious that the execution time of computing the partial semantics is no less than that to compute the semantics of the whole argumentation framework. Meanwhile, as shown in Table 8.2, since in various cases, the execution time for generating an unattacked set and constructing a sub-framework induced by the unattacked set is very low, it can be neglected. As a result, in Figure 8.4(d), when the edge density is 20%, the four kinds of execution time overlap.
In addition, it is interesting to note that when the number of nodes is from 500 to 1000 and the edge density of an argumentation framework is no less than 0.6%, the size of the unattacked set is nearly equal to the number of all nodes in the argumentation framework (as shown in Figure 8.5(c) and (d)). The reason behind this phenomenon is the fact that when the number of nodes is 1000 and the edge density is 0.6%, the ratio of the number of edges to the number of nodes is 6:1, which is equal to the one in the case where the number of nodes is 100 and the edge density is 6%.
According to the above analysis, we may conclude that the computation of partial semantics of argumentation has the following two properties:
(i) The method of computing the partial semantics of argumentation is efficient when the defeat graphs of argumentation frameworks are sparse, especially when the ratio of the number of edges to the number of nodes is less than 2:1.
(ii) When the ratio of the number of edges to the number of nodes is more than 6:1, the average time for computing the partial semantics is almost equal to that of computing the semantics of the whole argumentation framework.
8.5 Conclusions
In this chapter, based on the idea of local computation, we have presented the definition and three basic properties of the partial semantics of argumentation, and conducted an empirical investigation on the properties of computing the partial semantics of argumentation. Since in many situations, only the status of some part of arguments in an argumentation framework is necessary to be figured out, when the defeat graphs of argumentation frameworks are sparse (more specifically, when the ratio of the number of edges to the number of nodes, of a defeat graph, is less than 2:1), the partial computation of argumentation semantics is apparently more efficient.
References
1. Modgil S, Caminada M. Proof theories and algorithms for abstract argumentation frameworks. In: Argumentation in Artificial Intelligence. Springer 2009;105–129.
2. Boella G, Gabbay DM, Perotti A, van der Torre L, Villata S. Conditional labelling for abstract argumentation. In: Proceedings of the First International Workshop on the Theory and Applications of Formal Argumentation. 2012;232–248.
3. Wakaki T, Nitta K. Computing argumentation semantics in answer set programming. In: Proceedings of the 22nd Annual Conference of the Japanese Society for Artificial Intelligence. 2008;254–269.
4. Egly U, Gaggl SA, Woltran S. Answer-set programming encondings for argumentation frameworks. Argument and Computation. 2010;1(2):147–177.
5. Nieves JC, Cortés U, Osorio M. Preferred extensions as stable models. Theory and Practice of Logic Programming. 2008;8(4):527–543.
1http://www.dlvsystem.com/dlvsystem/index.php/DLV_WRAPPER.
2DLV is an efficient ASP solver. Please refer to the following web page for details: http://www.dbai.tuwien.ac.at/proj/dlv/.