Existing Approaches for Computing Argumentation Semantics
Abstract
In this chapter, we introduce two existing approaches for computing argumentation semantics. One is a reduction approach, based on answer set programming, the other is a direct approach, called labelling-based algorithms. These two approaches will be used in the empirical studies of the efficient approaches for computing the semantics of argumentation.
Keywords
answer set programming; direct apporach; labelling-based algorithms; reduction approach; semantics computation
3.1 Introduction
Given an argumentation framework, an important problem is to determine the status of arguments, i.e., to compute the extensions or labellings of the argumentation framework. In recent years, various approaches for computing the semantics of argumentation have been developed, including reduction approaches and direct approaches, as summarized in [1].
The basic idea of the reduction approaches is to exploit existing efficient methods that have been developed for other purposes. By translating the problems of finding extensions or labellings to the problems within other formalisms (such as propositional logic and answer-set programming, etc.), the sophisticated problem solvers dedicated to these formalisms could be exploited. On the other hand, the direct approaches (such as labelling-based algorithms, dialogue games, etc.) are developed from scratch.
In this chapter, we introduce a reduction approach that is based on answer-set programming (ASP), and a direct approach, called labelling-based algorithms.
3.2 Approaches Based on Answer Set Programming
Since many natural argumentation problems are in general intractable, one way to resolve them is to translate them to another language, for which sophisticated systems already exist. Answer set programming is a very good candidate for this purpose. This is because advanced solvers such as Smodels, DLV and Clasp which are able to deal with large problem instances are available. In other words, after we encode solutions to an argumentation problem into the intended models of a logic program, the existing ASP solvers can be exploited to compute some or multiple answer set(s) of the program together with the input, and the solutions of the problem can then be easily read off from the answer sets [2].
3.2.1 Answer Set Programming
Answer set programming (or briefly, ASP) is a declarative problem-solving paradigm, rooted in logic programming and non-monotonic reasoning [3]. Its syntax and semantics are introduced as follows.
3.2.1.1 Syntax
A term is a constant symbol or a variable symbol. An atom is an expression 
, where 
is a predicate of arity 
and each 
is a term. An atom is ground if it is free of variable. A literal is an atom 
or a strongly negated atom 
. Negation as failure is represented as 
. A disjunctive rule 
is a rule of the form:
(3.1)
where 
(
) is a literal, and 
represents epistemic disjunction. The head of a rule 
is the set 
, and the body of 
is 
. Furthermore, the positive body and negative body of 
are denoted by 
and 
, respectively.
A rule 
is normal if 
and a constraint if 
. A rule 
is safe if each variable in 
occurs in 
. A rule 
is ground if every atom in 
is ground. A fact is a ground rule without disjunction and empty body. A program is a finite set of disjunctive rules. If each rule in a program is normal (respectively, ground), we call the program normal (respectively, ground).
3.2.1.2 Answer Set Semantics
Let 
be a ground disjunctive logic program and 
be the set of ground literals in the language of 
. First, let us consider the case that each rule in 
does not contain 
. An answer set of 
is any minimal subset of 
such that,
from 
, if 
, then for some 
, it holds that 
;
contains a pair of complementary literals, then 
.Second, when the rules in 
contain 
, for any set 
, let 
be the logic program obtained from 
by deleting: (1) each rule that has a formula 
in its body with 
, and (2) all formulas of the form 
in the bodies of the remaining rules. After this treatment, 
does not contain 
. Then, 
is called an answer set of 
if and only if 
is an answer set of 
.
3.2.2 ASP for Argumentation
As summarized by [4], several approaches have been proposed for computing extensions of argumentation frameworks by using ASP solvers. All of them rely upon the mapping of an argumentation framework into a logic program whose answer sets are in one-to-one correspondence with the extensions of the original argumentation framework. These approaches are classified into two groups: those which result in an argumentation-dependent logic program, and those which result in a logic program with an argumentation framework-dependent component and an argumentation framework-independent (meta-)logic program. In this book, we only introduce Egly at al’s approach [2], which belongs to the second group. Readers may refer to [4] for a more comprehensive introduction.
In Egly et al’s approach, an argumentation framework 
is mapped to a set of facts 
to be included in logic programs defined for computing extensions under various semantics.
For conflict-free sets, the logic program consists of 
together with 
, which is defined as follows (here, we abuse the notation “;” as “,” in a set):
For stable extensions, two additional rules for stability test are required, and we have the following definition for 
:
The first rule of 
computes those arguments attacked by the current guess, while the constraint in 
eliminates those guesses where some argument not contained in the guess remains undefeated.
For admissible extensions, the logic program 
is defined as follows:
The first rule is the same as the one in 
. The new constraint rules out sets containing a non-defended argument.
For complete extensions, the logic program 
is defined as follows:
For grounded extensions, the logic program 
is obtained by mirroring the characteristic function presentation of this semantics. The program makes use of an arbitrary ordering 
over arguments (such an order is provided by all ASP-solvers). The program consists of three components. The first component 
uses the given ordering 
over arguments to derive corresponding predicates for infimum 
, supremum 
and successor 
:
The second component computes all arguments defended (by all arguments currently IN) in the layers obtained using 
and 
, as follows:
The third component simply imposes that all defended arguments should be IN:
Hence, 
.
For preferred extensions, the so-called saturation technique is used: Having computed admissible extension 
(characterized via predicates in(
) and out(
)), we perform a second guess using new predicates, say inN(
) and outN(
), to represent a further guess 
. In order to check whether the first guess (via in(
) and out(
)) characterizes a preferred extension, we have to ensure that no guess of the second form (i.e., via inN(
) and outN(
)) characterizes an admissible extension. The saturation model is defined as follows:
Then, we still need to define the rules for the predicates eq and undefeated(
), which are computed via predicates eq_upto(
) (respectively, undefeated_upto(
)) in the same manner as we used defended_upto(
) for defended(
) in the module 
.
Then, the logic program for preferred extensions is 
.
It has been proved that the answer sets of 
(
) are in one-to-one correspondence with the extensions of the argumentation framework 
under semantics 
[5].
3.3 Labelling-Based Algorithms
Labelling-based algorithms are a type of direct approach. They are based on the concept of argument labellings. In existing literature, various algorithms have been proposed for computing argument labellings. In recent years, Modgil and Caminada’s labelling-based algorithms (or briefly, MC algorithms) [6] have received much attention and been compared with some newly proposed algorithms [7,8]. Now, let us introduce the MC algorithm for computing the grounded labelling and the preferred labellings of an argumentation framework.
3.3.1 The Computation of Grounded Labellings
As presented in [6], given an argumentation framework 
, an algorithm for generating the grounded labelling of 
starts by assigning IN to all arguments that are not attacked, and then iteratively: OUT is assigned to any argument that is attacked by an argument that has just been made IN, and then IN to those arguments all of whose attackers are OUT. Thus, the arguments assigned IN on each iteration, are those that are reinstated by the arguments assigned IN on the previous iteration. The iteration continues until no more new arguments are made IN or OUT. Any arguments that remain unlabelled are then assigned UNDEC.
3.3.2 The Computation of Preferred Labellings
The MC algorithm for computing preferred labellings is realized by computing admissible labellings that maximize the number of arguments that are legally IN.
3.3.2.1 Generating Admissible Labellings
The approach to generate an admissible labelling is to start with the all-in labelling (the labelling in which every argument is labelled IN). This labelling trivially satisfies the absence of arguments that are illegally OUT. In order to satisfy another requirement of an admissible labelling (without arguments that are illegally IN), we need a way of changing the label of an argument that is illegally IN, preferrably without creating any arguments that are illegally OUT. This is done using a sequence of transition steps.
A transition step basically takes an argument that is illegally IN and relabels it to OUT. It then checks if, as a result of this, one or more arguments have become illegally OUT. If this is the case, then these arguments are relabelled to UNDEC. More precisely, a transition step can be described as follows.
Definition 3.1
Transition step
Let 
be a labelling for 
and 
be an argument that is illegally IN in 
. A transition step on 
in 
consists of the following:
is changed from IN to OUT;
, if 
is illegally OUT, then the label of 
is changed from OUT to UNDEC.It has been proved that each transition step preserves the absence of arguments that are illegally out [9]. In other words, during the transition, no arguments that are illegally OUT are generated.
Given an initial labelling 
, a sequence of successive transition steps applied on 
is called a transition sequence, which is defined as follows [9].
Definition 3.2
Transition sequence
A transition sequence is a list 
where each 
is an argument that is illegally IN in labelling 
and every 
is the result of doing a transition step of 
on 
. A transition sequence is called terminated if and only if 
does not contain any argument that is illegally IN.
Example 3.1
Consider Figure 2.3 in Example 2.7. Let 
. According to Definition 2.14, 
and 
are illegally IN. There are several transition sequences. A possible sequence is 
, detailed as follows.
It has been verified that for any finite argumentation framework, only a finite number of transition steps can be performed, and the final labelling is an admissible labelling.
3.3.2.2 Generating Preferred Labellings
The generation of preferred labellings is based on the generation of admissible labellings. Since a preferred labelling is an admissible labelling that maximizes the number of arguments that are legally IN, we need some mechanisms to compare and choose the labellings we have generated, in that some admissible labellings are not preferred labellings. First, consider the following example presented in [6].
Example 3.2
Let 
be an argumentation framework (Figure 3.1). Given 
, we have the following two possible transition steps. The first one is 
, which is an admissible and complete labelling. The second one is 
, which is an admissible labelling, but not a complete labelling (see Figure 3.2).
According to the above example, when we have 
, if we choose 
rather than 
, then we could avoid getting a non-complete labelling (that is not a preferred labelling), and improve the efficiency of computation. For this purpose, in terms of [6], we may choose an argument that is super-illegally IN, if such an argument is available.
Definition 3.3
Super-illegally IN
Let 
be a labelling for 
. An argument 
in 
that is illegally IN, is also super-illegally IN if and only if it is attacked by an argument 
that is legally IN in 
, or UNDEC in 
.
.
According to Definition 3.3, in Example 3.2, in 
is illegally IN, while 
is not.
Based on the notion of super-illegally IN, an algorithm for preferred labellings is shown in Algorithm 3.2 [6].
The initial labelling 
, i.e., all arguments of the argumentation framework 
are labelled IN. With this initial labelling, the procedure 
iteratively applies transitions steps in an attempt to generate terminated transition sequences that update the global variable 
. The algorithm preferentially selects from amongst super-illegally IN arguments for performing transition steps, if such arguments are available. If at any stage in the generation of a transition sequence, the arguments that are IN in the labelling 
thus far obtained are a strict subset of 
for some 
, then no further transition steps on 
can result in a preferred labelling (that maximizes the arguments that are IN). This follows from the result that during the course of a transition sequence, the set of IN labelled arguments monotonically decreases. Thus, any further transition steps on 
will only reduce the arguments that are IN. In such cases, the algorithm backtracks to 
and, if possible, selects another argument on which to perform a transition step. In the case that a transition sequence terminates, the obtained labelling 
is compared with all labellings 
in 
. If for any 
is a strict subset of 
, then 
is removed from 
. Thus, given a finite argumentation framework 
, the algorithm calculates the preferred labellings and so preferred extensions.
3.4 Conclusions
In this chapter, we have introduced two approaches for computing argumentation semantics. Other approaches also exist. Among them, the methods based on dialogue games are famous. In a dialogue game, there are two players, a proponent and an opponent. The former argues in favour of an argument in question, and the latter argues against it. If the proponent has a winning strategy, then the argument is accepted. Some algorithms based on dialogue games can be found in [6] and [10].
References
1. G. Charwat, W. Dvorak, S.A. Gaggl, J.P. Wallner, S. Woltran, Implementing Abstract Argumentation: A Survey, DBAI Technical Report, 2013.
2. Egly U, Gaggl SA, Woltran S. ASPARTIX: implementing argumentation frameworks using answer-set programming. In: Proceedings of the 24th International Conference on Logic Programming. Elsevier 2009;734–738.
3. M. Gelfond, Answer Sets, Handbook of Knowledge Representation, 2007, pp. 285–316.
4. Toni F, Sergot M. Argumentation and answer set programming. Lecture Notes in Computer Science Volume. 2011;6565:164–180.
5. Egly U, Gaggl SA, Woltran S. Answer-set programming encodings for argumentation frameworks. Argument & Computation. 2010;1(2):147–177.
6. Modgil S, Caminada M. Proof theories and algorithms for abstract argumentation frameworks Argumentation in Artificial Intelligence Springer 2009.
7. Baumann R, Brewka G, Wong R. Splitting argumentation frameworks: an empirical evaluation. In: Proceedings of the 1st International Workshop on Theory and Applications of Formal Argumentation. 2012;17–31.
8. Nofal S, Dunne P, Atkinson K. On preferred extension enumeration in abstract argumentation. In: Proceedings of the 4th International Conference on Computational Models of Argument. 2012;205–216.
9. Caminada M. An algorithm for computing semi-stable semantics. In: Proceedings of the European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty. 2007;222–234.
10. Thang PM, Dung PM, Hung ND. Towards a common framework for dialectical proof procedures in abstract argumentation. Journal of Logic and Computation. 2009;19(6):1071–1109.