Solving Weighted Argumentation Frameworks with Soft Constraints

Abstract

We suggest soft constraints as a mean to parametrically represent and solve \weighted" Argumentation problems: di®erent kinds of preference levels related to arguments, e.g. a score representing a \fuzziness", a \cost" or a probability level of each argument, can be represented by choosing di®erent semiring algebraic structures. The novel idea is to provide a common computational and quantitative framework where the computation of the classical Dung's extensions, e.g. the admissible extension, has an associated score representing \how much good" the set is. Preference values associated to arguments are clearly more informative and can be used to prefer a given set of arguments over others with the same characteristics (e.g. admissibility). Moreover, we propose a mapping from weighted Argumentation Frameworks to Soft Constraint Satisfaction Problems (SCSPs); with this mapping we can compute Dung semantics (e.g. admissible and stable) by solving the related SCSP. To implement this mapping we use JaCoP, a Java constraint solver.

-

Interactions are a core part of all multi-party systems (e.g. multi-agent systems). Argumentation [ 12 ] is based on the exchange and the evaluation of interacting arguments which may represent information of various kinds, especially beliefs or goals. Argumentation can be used for modeling some aspects of reasoning, decision making, and dialogue. For instance, when an agent has con°icting beliefs (viewed as arguments), a (nontrivial) set of plausible consequences can be derived through argumentation from the most acceptable arguments for the agent. Argumentation can be seen as the process emerging from exchanges of among agents to persuade each other and and bring about a change in intentions [ 21, 19 ]. Argumentation has become an important subject of research in Arti¯cial Intelligence and it is also of interest in several disciplines, such as Logic, Philosophy and Communication Theory [ 23 ].

Many theoretical and practical developments build on Dung's seminal theory of argumentation. A Dung Argumentation Framework (AF ) is a directed graph consisting of a set of arguments and a binary con°ict based attack relation among them. The sets of arguments to be considered are then de¯ned under di®erent semantics, where the choice of semantics equates with varying degrees of scepticism or credulousness.

The other ingredient in our research is Constraint Programming [ 24 ], which is a powerful paradigm for solving combinatorial search problems that draws on a wide range of techniques from arti¯cial intelligence, computer science, databases, programming languages, and operations research. The idea of the semiring-based formalism [ 7, 5 ] was to further extend the classical constraint notion by adding the concept of a structure representing the levels of satis¯ability of the constraints. Such a structure (see Sec. 3 for further details) is a set with two operations: one + is used to generate an ordering over the preference levels, while £ is used to combine these levels. Because of the properties required on such operations, this structure is similar to a semiring (see Sec. 3). Problems de¯ned according to this semiring-based framework are called Soft Constraint Satisfaction Problems (SCSPs).

In this paper we show that di®erent weighted AFs based on fuzziness, probability or a preference in general (and already studied in literature, e.g. in [ 23, 3 ]), can be modeled and solved with the same soft constraint framework by only changing the related semiring in order to optimize the di®erent criteria. Also classical AFs can be represented inside the soft framework by adopting the Boolean semiring. We provide a mapping from AFs to (S)CSPs in a way that the solution of the SCSP consists in the \best" desired extension, where \best" is computed by aggregating (with £) the preference scores of all the chosen arguments, and comparing the ¯nal values (with +). The classical extensions of Dung can be found with our mapping, i.e. admissible, preferred, complete, stable and grounded ones. At last, we show an implementation of a CSP with JaCoP [ 22 ], a Java Constraint Programming solver.

Clearly, the classical attack relationship is not enough informative to deal with problems where we however need to take a decision: suppose a judge must decide between the arguments of two parties, and often no conclusive demonstration of the rightness of one side is possible. The arguments will not have equal value for the judge and the case will be decided by the judge preferring one argument over the other [ 23 ]. Moreover, having a quantitative framework permits us to quantify the aggregation of chosen arguments and to prefer a set of arguments over another. Examples in the real world are represented by scores given to comments in Youtube or news in Slashdot, or topics in Discussion Fora in general [ 18 ]. As the set of arguments gets wider, the search of the best solutions becomes a demanding task, and constraint-based frameworks come with many and powerful solving techniques: notice that deciding if a set is a preferred extension is a CO-N P -complete problem [ 4 ]. Moreover, preference score can be used to cut not promising solutions during the search and, however, to re¯ne it by ¯nding the only the best solutions. In this paper we start from qualitative argumentation [ 23, 3, 2 ] and we move towards a quantitative solution.

The remainder of this paper is organized as follows. In Sec. 2 we report the theory behind Dung Argumentation, while in Sec. 3 we summarize the background about soft constraints. Section 4 shows the basic idea of weighted AF based on semirings; in Sec. 5 we propose the mapping from AFs to SCSPs, the proofs of their solution equivalence and we show a practical encoding in JaCoP. A comparison with related work is given in Sec. 6. Finally, Sec. 7 presents our conclusions. 2

Dung Argumentation

In [ 12 ], the author has proposed an abstract framework for argumentation in which he focuses on the de¯nition of the status of arguments. For that purpose, it can be assumed that a set of arguments is given, as well as the di®erent con°icts among them. An argument is an abstract entity whose role is solely determined by its relations to other arguments.

De¯nition 1. An Argumentation Framework (AF) is a pair hArgs; Ri of a set Args of arguments and a binary relation R on Args called the attack relation. 8ai; aj 2 A, aiR aj means that ai attacks aj . An AF may be represented by a directed graph (the interaction graph) whose nodes are arguments and edges represent the attack relation. A set of arguments B attacks an argument a if a is attacked by an argument of B. A set of arguments B attacks a set of arguments C if there is an argument b 2 B which attacks an argument c 2 C.

The \acceptability" of an argument [ 12 ] depends on its membership to some sets, called extensions. These extensions characterize collective \acceptability". Let AF = hArgs; Ri; B µ Args. The main characteristic properties are: b a c d

In Fig. 1 we show an example of AF represented as an interaction graph: the nodes represent the arguments and the directed arrow from c to d represents the attack of c towards d, that is c R d. Dung [ 12 ] gave several semantics to \acceptability". These various semantics produce none, one or several acceptable sets of arguments, called extensions. In Def. 2 we de¯ne the concepts of con°ictfree and stable extensions: De¯nition 2. A set B µ Args is con°ict-free i® it does not exist two arguments a and b in B such that a attacks b. A con°ict-free set B µ Args is a stable extension i® for each argument which is not in B, there exists an argument in B that attacks it.

The other semantics for \acceptability" rely upon the concept of defense: De¯nition 3. An argument b is defended by a set B µ Args (or B defends b) i® for any argument a 2 Args, if a attacks b then B attacks a.

An admissible set of arguments according to Dung must be a con°ict-free set which defends all its elements. Formally: De¯nition 4. A con°ict-free set B µ Args is admissible i® each argument in B is defended by B.

Besides the stable semantics, three semantics re¯ning admissibility have been introduced by Dung [ 12 ]: De¯nition 5. A preferred extension is a maximal (w.r.t. cardinality) admissible subset of Args. An admissible B µ Args is a complete extension i® each argument which is defended by B is in B. The least (w.r.t. cardinality) complete extension is the grounded extension.

A stable extension is also a preferred extension and a preferred extension is also a complete extension. Stable, preferred and complete semantics admit multiple extensions whereas the grounded semantics ascribes a single extension to a given argument system.

Notice that deciding if a set is a stable extension or an admissible set can be computed in polynomial time, but deciding if a set is a preferred extension is a CO-N P -complete problem [ 4 ]. 3

Soft Constraints

A c-semiring [ 7, 5 ] S (or simply semiring in the following) is a tuple hA; +; £; 0; 1i where A is a set with two special elements (0; 1 2 A) and with two operations + and £ that satisfy certain properties: + is de¯ned over (possibly in¯nite) sets of elements of A and thus is commutative, associative, idempotent, it is closed and 0 is its unit element and 1 is its absorbing element; £ is closed, associative, commutative, distributes over +, 1 is its unit element, and 0 is its absorbing element (for the exhaustive de¯nition, please refer to [ 7 ]). The + operation de¯nes a partial order ·S over A such that a ·S b i® a + b = b; we say that a ·S b if b represents a value better than a. Other properties related to the two operations are that + and £ are monotone on ·S , 0 is its minimum and 1 its maximum, hA; ·S i is a complete lattice and + is its lub. Finally, if £ is idempotent, then + distributes over £, hA; ·S i is a complete distributive lattice and £ its glb.

A soft constraint [ 7, 5 ] may be seen as a constraint where each instantiation of its variables has an associated preference. Given S = hA; +; £; 0; 1i and an ordered set of variables V over a ¯nite domain D, a soft constraint is a function which, given an assignment ´ : V ! D of the variables, returns a value of the semiring. Using this notation C = ´ ! A is the set of all possible constraints that can be built starting from S, D and V . Any function in C involves all the variables in V , but we impose that it depends on the assignment of only a ¯nite subset of them. So, for instance, a binary constraint cx;y over variables x and y, is a function cx;y : V ! D ! A, but it depends only on the assignment of variables fx; yg µ V (the support of the constraint, or scope). Note that c´[v := d1] means c´0 where ´0 is ´ modi¯ed with the assignment v := d1. Note also that c´ is the application of a constraint function c : V ! D ! A to a function ´ : V ! D; what we obtain, is a semiring value c´ = a. 0¹ and 1¹ respectively represent the constraint functions associating 0 and 1 to all assignments of domain values (i.e. the a¹ function returns the semiring value a).

Given the set C, the combination function ­ : C £ C ! C is de¯ned as (c1 ­ c2)´ = c1´ £ c2´ (see also [ 7, 5 ]). Informally, performing the ­ or between two constraints means building a new constraint whose support involves all the variables of the original ones, and which associates with each tuple of domain values for such variables a semiring element which is obtained by multiplying the elements associated by the original constraints to the appropriate sub-tuples.

Given a constraint c 2 C and a variable v 2 V , the projection [ 7, 5, 6 ] of c over V ¡ fvg, written c +(V nfvg) is the constraint c0 such that c0´ = Pd2D c´[v := d]. Informally, projecting means eliminating some variables from the support.

A SCSP [ 5 ] de¯ned as P = hC; coni (C is the set of constraints and con µ V , i.e. a subset the problem variables). A problem P is ®-consistent if blevel(P ) = ® [ 5 ]; P is instead simply \consistent" i® there exists ® >S 0 such that P is ®consistent [ 5 ]. P is inconsistent if it is not consistent. The best level of consistency notion de¯ned as blevel(P ) = Sol(P ) +;, where Sol(P ) = (N C) +con [ 5 ]. c1 <a> 1 <b> 9

X <a,a> 5 <a,b> 1 <b,a> 2 <b,b> 2 c2 <a> 5 <b> 5 Y c3

A SCSP Example. Figure 2 shows a weighted CSP as a graph: the semiring used for this problem is the Weighted semiring, i.e. hR+; min; +^ ; 1; 0i (+^ is the arithmetic plus operation). Variables and constraints are represented respectively by nodes and by undirected arcs (unary for c1 and c3, and binary for c2), and semiring values are written to the right of each tuple. The variables of interest (that is the set con) are represented with a double circle (i.e. variable X). Here we assume that the domain of the variables contains only elements a and b. For example, the solution of the weighted CSP of Fig. 2 associates a semiring element to every domain value of variable X. Such an element is obtained by ¯rst combining all the constraints together. For instance, for the tuple ha; ai (that is, X = Y = a), we have to compute the sum of 1 (which is the value assigned to X = a in constraint c1), 5 (which is the value assigned to hX = a; Y = ai in c2) and 5 (which is the value for Y = a in c3). Hence, the resulting value for this tuple is 11. We can do the same work for tuple ha; bi ! 7, hb; ai ! 16 and hb; bi ! 16. The obtained tuples are then projected over variable x, obtaining the solution hai ! 7 and hbi ! 16. The blevel for the example in Fig. 2 is 7 (related to the solution X = a, Y = b). 4

Weighted Argumentation

Weighted argumentation systems [ 10, 13 ] extend Dung-style abstract argumentation systems by adding numeric weights to every node (or attack) in the attack graph, intuitively corresponding to the strength of the attack, or equivalently, how reluctant we would be to disregard it. To illustrate the need to extend the classical AF with preferences, we consider two individuals P and Q exchanging arguments A and B about the weather forecast (the example is taken from [ 23 ]): P: Today will be dry in London since BBC forecast sunshine = A Q: Today will be wet in London since CNN forecast rain = B

A and B claim contradictory conclusions and so attack each other. Under Dung's preferred semantics, there are two di®erent admissible extensions represented by the sets fAg and fBg, but neither argument is sceptically justi¯ed. One solution is to provide some means for preferring one argument to another in order to ¯nd a more informative answer, for example, the most trustworthy extension. For example, one might reason that A is preferred to B because the BBC are deemed more trustworthy than CNN. Suppose to have a fuzzy trust score associated with each argument, as shown in Fig. 3. This score, (between 0 and 1 that is between low and high trustworthiness) can be then used to prefer fAg with a score of 0:9 over fBg with a score of 0:7, i.e. forecast from BBC than from CCN.

BBC sunshine 0.7 CNN rain

In some works [ 17 ] the preference score is associated with the attack relationship instead of with the argument itself and, thus, it models the \strength" of the attack, e.g. a fuzzy attack. This model can be cast in ours by composing these strengths in a value representing the preference of the argument, as in Fig. 4, where the trustworthiness of argument CNN-rain can be computed as the mathematical mean (or in general a function ±, as de¯ned also in [ 9 ] for computing the trust of a group of individuals) of the values associated with the attack towards it, i.e. (0:9 + 0:5)n2 = 0:7. Computing a trust evaluation of a node by considering a function of the links ending in it is a well-known solution, e.g. the PageRank of Google [ 18 ]. By composing attack and support values, it is also possible to quantitatively study bipolar argumentation frameworks [ 1 ].

Notice that in [ 23, 3, 2 ] the preference among arguments is given in a qualitative way, that is argument a is better than argument b, which is better than argument c; in this section we study the problem from a quantitative point of view, with scores associated with arguments. We suggest the algebraic semiring structure (see Sec. 3) as a mean to parametrically represent and solve all the \weighted" AFs presented in literature (see Sec. 6), i.e. to represent the scores; in the following we provide some examples on how semirings ful¯l these di®erent tasks.

An argument can be seen as a chain of possible events that makes the hypothesis true. The credibility of a hypothesis can then be measured by the total probability that it is supported by arguments. The proper semiring to solve this problem consists in the Probabilistic semiring [ 5 ]: h[0::1]; max; £^ ; 0; 1i, where the arithmetic multiplication (i.e. £^ ) is used to compose the probability values together.

The Fuzzy Argumentation [ 27 ] approach enriches the expressive power of the classical argumentation model by allowing to represent the relative strength of the attack relationships between arguments, as well as the degree to which arguments are accepted. In this case, the Fuzzy semiring h[0::1]; min; max; 0; 1i can be used.

In addition, the Weighted semiring hR+; min; +^ ; 0; 1i, where +^ is the arithmetic plus, can model the (e.g. money) cost of the attack: for example, during an electoral campaign, a candidate could be interested in how many e®orts or resources he should spend to counteract an argument of the opposing party.

At last, with the Boolean semiring hftrue; f alseg; _; ^; f alse; truei we can cast the classic AFs originally de¯ned by Dung [ 12 ] in the same semiring-based framework.

Moreover, notice that the cartesian product of two semirings is still a semiring [ 7, 5 ], and this can be fruitfully used to describe multi-criteria constraint satisfaction and optimization problems. For example, we can have both a probability and a fuzzy score given by a couple ht; f i; we can optimize both costs at the same time.

We can extend the de¯nitions provided in Sec. 3 in order to express all these weights of the attack relations with a semiring based environment. The following de¯nitions model the semiring-based problem.

De¯nition 6. A semiring-based Argumentation Framework (AFS ) is a quadruple hArgs; R; W; Si of a semiring S = hA; +; £; 0; 1i, a set Args of arguments, the attack binary relation R on Args, and a unary function W : Args ¡! A called the weight function. 8a 2 Args, W (a) = s means that a has a preference level s 2 A.

Therefore, the weight function W associates each argument with a semiring value (s 2 A) that represents the preference expressed for that argument in terms of cost, fuzziness and so on. For example, using the Fuzzy semiring h[0::1]; min; max; 0; 1i semiring for the problem represented in Fig. 3 allows us to state that the admissible extension fAg (with a score of 0:9) is better than the other admissible extension fBg (with a s.core of 0:7) since 0:9 > 0:7. Therefore, with an AFS our goal is to ¯nd the extensions proposed by Dung (e.g. the admissible extensions), but with an associated preference value. Therefore, soft constraints can be used to solve these problems while considering also the best solution(s) (according to the notion of blevel, and to cut the solutions with a preference below a threshold ®.

Example 1. Concerning the interaction graph in Fig. 5, it represents the Weighted AFS W = (Args; R) with S = hR+; min; +^ ; 1; 0i and Args = fa; b; c; d; eg, R(a; b) = 0:7; R(c; b) = 0:8; R(c; d) = 0:9; R(d; c) = 0:8; R(d; e) = 0:5; R(e; e) = 0:6 and W (a) = 7; W (b) = 20; W (c) = 6; W (d) = 10; W (e) = 12. Notice that e attacks itself, that is in contrast with itself, e.g. \We have sunshine and it's raining" (it may be possible). 5

Mapping AFs to SCSPs

Our second result is a mapping from AF (and AFS ) to (S)CSPs. Given an AFS = hArgs; R; W; Si, we de¯ne a variable for each argument ai 2 Args, i.e. V = fa1; a2; : : : ; ang and each of these argument can be taken or not, i.e. the domain of each variable is D = f1; 0g, and if it is taken, a cost in the semiring can be assigned, mapping the level of preference of this argument.

To represent the quantitative preference over arguments, in this mapping we need only unary soft constraints on each variable, while the other constraints modeling, for example, the con°ict-free relationship (see Sec. 2) are crisp even if represented in the soft framework. We plan to extend also these constraints to properly-said soft ones as suggested in Sec. 7. In the following explanation, notice that b attacks a meas that b is a parent of a in the interaction graph, and c attacks b attacks a means that c is a grandparent of a. To compute the (weighted) extensions of Dung we need to de¯ne speci¯c sets of constraints: 1. Preference constraints. The weight function W (ai) = s (s 2 A) of an AFS can be modeled with the unary constraints cai (ai = 1) = s, otherwise, when ai is assigned to 0), the argument is not taken in the considered extension an so its cost must not be computed. 2. Con°ict-free constraints. Since we want to ¯nd the con°ict-free sets, if R(ai; aj ) is in the graph we need to prevent the solution to include both ai and aj in the considered extension: cai;aj (ai = 1; aj = 1) = 0. For the other possible assignment of the variables ((a = 0; b = 1)(a = 1; b = 0) and (a = 0; b = 0)), cai;aj = 1, since these assignments are permitted: in these cases we are choosing only one argument between the two (or none of the two) and thus, we have no con°ict. 3. Admissible constraints. For the admissibility, we need that, if child argument ai has a parent node af but ai has no grandparent node ag (parent of af ), then we must avoid to take ai in the extension because it is attacked and cannot be defended by any ancestor: expressed with a unary constraint, cai (ai = 1) = 0.

Moreover, if ai has several grandparents ag1; ag2; : : : ; agk and only one parents af (child of ag1; ag2; : : : ; agk), we need to add a k + 1-ary constraint cai;ag1;:::;agk (ai = 1; ag1 = 0; : : : ; agk = 0) = 0. The explanation is that at least a a grandparent must be taken in the admissible set, in order to defend ai from one of his parents af . Notice that, if a node is not attacked (i.e. he has no parents), he can be taken or not in the admissible set. 4. Complete constraints. To compute a complete extension B, we need that each argument ai which is defended by B is in B (see Sec. 2). This can be enforced by imposing that for each ai taken in the extension, also all its as1; as2; : : : ; ask grandsons must be taken in the extension, i.e. cai;as1;:::;ask (ai = 1; as1 = 1; : : : ; ask = 1) = 1 and also if ai = 0 this constraint is satis¯ed; 0 otherwise. 5. Stable constraints. If we have a child node ai with multiple parents af1; af2; : : : ; afk, we need to add the constraint cai;af1;:::;afk (ai = 0; af1 = 0; : : : ; afk = 0) = 0. In words, if a node is not taken in the extension (i.e. ai = 0), then it must be attacked by at least one of the taken nodes, that is at least a parent of ai needs to be taken in the stable extension (that is, afj = 1).

Moreover, if a node ai has no parent in the graph, it has to be included in the stable extension (notice ai cannot be attacked by nodes inside the extension, since he has no parent). The corresponding unary constraint is cai (ai = 0) = 0.

Notice that by using the Boolean semiring, also the class of preference constraints becomes crisp and we can consequently model classical Dung AFs, that is not weighted frameworks. The following proposition states the equivalence between solving an AFS and its related SCSP.

Proposition 1 (Solution equivalence). Given an AFS = hArgs; R; W; Si and S = hA; +; £; 0; 1i, the solutions of the related SCSP obtained with the mapping corresponds to ¯nd over AFS the best(according to +) { con°ict-fee extensions by using preference and con°ict-free constraint classes. { admissible extensions by using preference, con°ict-free and admissible constraint classes. { complete extensions by using preference, con°ict-free and admissible constraint classes.

{ stable extensions by using preference, con°ict and stable constraint classes. By using the Boolean semiring the solutions of the (S)CSP respectively correspond to all the classical admissible, complete and stable extensions of Dung [ 12 ].

Moreover, to ¯nd the preferred extension (see Sec. 2) we simply need to ¯nd all the maximal (w.r.t. set inclusion) admissible extensions of Args, that is to ¯nd all the admissible sets (using the ¯rst three classes of constraints) and then returning only those subsets with the highest number of variables assigned to 1. Similar considerations hold for the grounded extension (see Sec. 2), that is we need to ¯nd all the complete extensions (the ¯rst four classes of constraints) and then to return only those subsets with the lowest number of variables assigned to 1 4.

As suggested in Sec. 4, an AFS can be represented as a weighted interaction graph as in Fig. 5, where we instead suppose to use a Weighted semiring, i.e. hR+; min; +^ ; 1; 0i, e.g. the argument a has received 7 negative comments. The goal in this case is to choose the extensions of Dung and to minimize the sum of the negative comments at the same time. 4 Di®erent interpretations of grounded/preferred extensions can be given by considering their cost instead of their the cardinality.

Notice that the presented soft constraint framework can be easily used to solve argumentation problems with additional constraints, as proposed in [ 11 ] only for boolean constraints. We can ¯nd further requirements on the sets of arguments which are expected as extensions, like \extensions must contain argument a when they contain b" or \extensions must not contain one of c or d when they contain a but do not contain b".

Solving with JaCoP The Java Constraint Programming solver [ 22 ], JaCoP in short, is a Java library, which provides Java user with Finite Domain Constraint Programming paradigm. It provides di®erent type of constraints: most commonly used primitive constraints, such as arithmetical constraints, equalities and inequalities, logical, rei¯ed and conditional constraints, combinatorial (global) constraints. The last version of JaCoP proposes many features, such as pruning events, multiple constraint queues, special data structures to handle e±ciently backtracking, iterative constraint processing, and many more [ 22 ]. Moreover, it can run also large examples, e.g. ca. 180000 constraints.

// Defining the Variables of the SCSP v[0] = new BooleanVariable(store, "a"); v[ 1 ] = new BooleanVariable(store, "b"); v[ 2 ] = new BooleanVariable(store, "c"); v[ 3 ] = new BooleanVariable(store, "d"); v[ 4 ] = new BooleanVariable(store, "e");

// conflict-free constraints public static void imposeConstraintConflictFree(Store store, BooleanVariable[] v) { store.impose(new ExtensionalConflictVA(new BooleanVariable[]{v[0], v[ 1 ]}, new int[][]{{1, 1}})); store.impose(new ExtensionalConflictVA(new BooleanVariable[]{v[ 2 ], v[ 1 ]}, new int[][]{{1, 1}})); store.impose(new ExtensionalConflictVA(new BooleanVariable[]{v[ 2 ], v[ 3 ]}, new int[][]{{1, 1}})); store.impose(new ExtensionalConflictVA(new BooleanVariable[]{v[ 3 ], v[ 2 ]}, new int[][]{{1, 1}})); store.impose(new ExtensionalConflictVA(new BooleanVariable[]{v[ 3 ], v[ 4 ]}, new int[][]{{1, 1}})); store.impose(new ExtensionalConflictVA(new BooleanVariable[]{v[ 4 ], v[ 4 ]}, new int[][]{{1, 1}})); } // stable constraints public static void imposeConstraintStableExtensions(Store store, BooleanVariable[] v) { store.impose(new ExtensionalConflictVA(new BooleanVariable[]{v[0]}, new int[][]{{0}})); store.impose(new ExtensionalConflictVA(new BooleanVariable[]{v[0], v[ 2 ], v[ 1 ]}, new int[][]{{0, 0, 0}})); store.impose(new ExtensionalConflictVA(new BooleanVariable[]{v[ 2 ], v[ 3 ]}, new int[][]{{0, 0}})); store.impose(new ExtensionalConflictVA(new BooleanVariable[]{v[ 3 ], v[ 4 ]}, new int[][]{{0, 0}})); }

Fig. 6. The constraint in JaCoP for the mapping of Fig. 5.

In Fig. 6 we show the de¯nition in JaCoP of all the con°ict-free and stable constraints used to solve the AFS example in Fig. 5. The full description of the code can be found in [ 8 ]. Considering for example the ¯rst con°ict-free constraint in Fig. 5, v[0]; v[ 1 ], means that the constraint is between a and b and (1; 1) that the the constraint is not satis¯ed if both variables are taken in the set.

Considering the example in Fig. 5 the admissible sets are: fag; fcg; fdg; fa; cg; fa; dg. Dung's semantics induce the following acceptable sets: one stable extension fa; dg, two preferred extensions P E1 = fa; cg; P E2 = fa; dg, three complete extensions CE1 = fa; cg; CE2 = fa; dg; CE3 = fag and the grounded extension a . With our quantitative interpretation of AFs with preferences and con´ f g sidering the Fuzzy semiring hR+; min; +^ ; 1; 0i, we can prefer P E1 over P E2 (W (a)+^ W (c)) = 13, W (a)+^ W (d) = 17 and CE3 over CE1 and CE2, since W (a) = 7. All these best solutions are obtained by using JaCoP. 6

Related Work

In [ 27 ], the authors have developed the notion of fuzzy uni¯cation and incorporated it into a novel fuzzy argumentation framework for extended logic programming: the attacks are associated to a fuzzy strength value, i.e. a V -attack. As well, a V -argument A is V -acceptable w.r.t. the set Args of V -arguments if each argument V -attacked A is V -attacked by an argument in Args.

In [ 3 ], AFs have been also extended to Value Based Argumentation Frameworks (VAF ) where V is a generic nonempty set of values and Val is a function which maps from elements of Args to elements of V .

The work in [ 2 ] concerns the \acceptability" of arguments in preferencebased argumentation frameworks. Preferences are represented with a preordering relationships (partial or total) that resembles the ordering de¯ned by the + operator of semirings (see Sec. 3).

Probabilistic Argumentation [ 16, 20 ]. This theory is an alternative approach for non-monotonic reasoning under uncertainty. It allows to judge open questions (hypotheses) about the unknown or future world in the light of the given knowledge. From a qualitative point of view, the problem is to derive arguments in favor and against the hypothesis of interest.

In [ 23 ] the author has extended Dung's theory of argumentation to integrate metalevel argumentation about preferences. Dung's level of abstraction is preserved, so that arguments expressing preferences are distinguished by being the source of a second attack relation that abstractly characterizes application of preferences by attacking attacks between the arguments that are the subject of the preference claims.

A close work is represented by [ 14 ]: there the authors introduce and investigate a natural extension of Dungs well known model of argument systems in which attacks are associated with a weight, indicating the relative strength of the attack. A key concept in that framework is the notion of an inconsistency budget, which characterizes how much inconsistency we are prepared to tolerate: given an inconsistency budget ¯, we would be prepared to disregard attacks up to a total cost of ¯.

Comparison. The framework proposed in this paper is able to solve all the above reported AFs (including the classical Dung framework [ 12 ]), both from the qualitative and (main novelty) quantitative point of view. Since in this paper we mainly propose a solving framework, we compare it with other related works.

In [ 14 ] weights are associated with attacks instead of arguments, as in our proposal. Moreover, no solving mechanism is proposed to solve the problems presented in the paper, even if their solution is proved to be di±cult in the paper (e.g. NP-Complete). Moreover, in [ 14 ] the combination of the weights and the preference of the solution correspond to our Weighted semiring, while other possibilities are not considered.

In [ 19 ] crisp constraint have been used to model argumentation as constraint propagation in Distributed Constraint Satisfaction Problem (DSCP ). Di®erent agents represent the distributed points in the problem. The paper shows the appropriateness of constraints in solving large-scale argumentation systems. However, it seems to only solve classical problems, (i.e. no qualitative or quantitative extensions).

The are some frameworks based on Logic Programming-like languages. For example, the system ASPARTIX [ 15 ] is a tool for computing acceptable extensions for a broad range of formalizations of Dung's argumentation framework and generalizations thereof, e.g. value-based AFs [ 3 ] or preference-based [ 2 ]. ASPARTIX relies on a ¯xed disjunctive datalog program which takes an instance of an argumentation framework as input, and uses the answer-set solver DLV for computing the type of extension speci¯ed by the user. However, ASPARTIX does not solve any quantitative argumentation case, as well as other Answer Set Programming systems [ 25 ].

In [ 10 ] the authors solve over-constrained weighted AF problems, where weights are associated with arcs and represent the cost of the attack between two arguments. to relax the notion of con°ict-free extensions to ®-con°ict-free ones (and also for hte other extensions of Dung), in order to include in the same set also attacking arguments, whose attack costs are not worse than a threshold ®. 7

Conclusions and Future Work

In the paper we have revised the notions provided by Dung [ 12 ] in order to associate the argument preference with a weight (taken from a semiring structure) that represents the \goodness" of the argument in terms of cost, fuzziness, probability or else. Further on, we have suggested the Dung's semantics in their soft version. Moreover, we have presented a mapping from SCSPs to AFs and solved the obtained SCSP with JaCoP, a Java Constraint Programming solver, thus ¯nding the solution of the related AF. We have proposed an unifying computational framework with strong mathematical foundations and solving techniques, where by only parametrically changing the semiring we can deal with di®erent weighted (or not) AFs. By having a uniform framework, it may be possible to see more clearly the relationships between di®erent proposals. It may also o®er the possibility to identify new results concerning classes of these proposals.

The user only needs to state the problem, while the underlying machinery is able to e±ciently satisfy the constraints. Constraint solving techniques prove to be able to deal with large scale problems [ 19 ], even if the treated problems are di±cult: for example, deciding if a set is a preferred extension is a CON P -complete problem [ 4 ]. Practical applications may consist, for example, in automatically study Discussion Fora where arguments are rated by users.

In the future, we would like to cluster arguments according to their (for example) coherence, still using soft constraints as the framework to obtain the solution. This can be useful to check the discrepancies/likeness during a negotiation process, inside di®erent interviews to the same political candidate or during discussions in general. As an example, \We do not want immigrants with the right to vote" is clearly closer to \Immigration must be stopped", than to \We need a multicultural and open society in order to enrich the life of everyone and boost our economy", and should belong to the same cluster.

At last, we want to generate a small-world network, for example with the Java Universal Network/Graph Framework (JUNG ) [ 26 ] in order to test automatically give an interaction graph as input and test the related performance. Acknowledgements We would like to thank Massimiliano Giacomin for the important suggestions.

References

1. L. Amgoud , C. C. , M.-C. Lagasquie-Schiex, and P. Livet . On bipolarity in argumentation frameworks . Int. J. Intell. Syst. , 23 ( 10 ): 1062 { 1093 , 2008 .

2. L. Amgoud and C. Cayrol . Inferring from inconsistency in preference-based argumentation frameworks . J. Autom. Reasoning , 29 ( 2 ): 125 { 169 , 2002 .

3. T. J. M. Bench-Capon . Persuasion in practical argument using value-based argumentation frameworks . J. Log. Comput. , 13 ( 3 ): 429 { 448 , 2003 .

4. P. Besnard and S. Doutre . Checking the acceptability of a set of arguments . In Workshop on Non-Monotonic Reasoning , pages 59 { 64 , 2004 .

5. S. Bistarelli . Semirings for Soft Constraint Solving and Programming , volume 2962 of LNCS . Springer, 2004 .

6. S. Bistarelli , U. Montanari , and F. Rossi . Soft concurrent constraint programming . ACM Trans. Comput. Logic , 7 ( 3 ): 563 { 589 , 2006 .

7. S. Bistarelli , U. Montanari , and F. Rossi . Semiring-based Constraint Solving and Optimization . Journal of the ACM , 44 ( 2 ): 201 { 236 , March 1997 .

8. S. Bistarelli , D. Pirolandi , and F. Santini . Solving weighted argumentation frameworks with soft constraints . Technical report, Dipartimento di Scienze , Universitaµ G. d'Annunzio , Pescara, December 2009 . Number R- 2009 -003, http: //www.sci.unich.it/~tecrep/2009/R-2009-003.pdf.

9. S. Bistarelli and F. Santini . Propagating multitrust within trust networks . In ACM Symposium on Applied Computing , pages 1990 { 1994 . ACM, 2008 .

10. S. Bistarelli and F. Santini . A common computational framework for semiringbased argumentation systems . In European Conference on Arti¯cial Intelligence (ECAI10) , 2010 .

11. S. Coste-Marquis , C. Devred , and P. Marquis . Constrained argumentation frameworks . In Knowledge Representation and Reasoning (KR) , pages 112 { 122 . AAAI Press, 2006 .

12. P. M. Dung . On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games . Artif . Intell., 77 ( 2 ): 321 { 357 , 1995 .

13. P. E. Dunne , A. Hunter , P. McBurney , S. Parsons , and M. Wooldridge . Inconsistency tolerance in weighted argument systems . In Conf. on Autonomous Agents and Multiagent Systems , pages 851 { 858 . IFAAMS , 2009 .

14. P. E.Dunne , A. Hunter , P. McBurney , S. Parsons , and M. Wooldridge . Inconsistency tolerance in weighted argument systems . In AAMAS '09: Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems , pages 851 { 858 . International Foundation for Autonomous Agents and Multiagent Systems , 2009 .

15. U. Egly, S. Alice Gaggl , and S. Woltran . ASPARTIX: Implementing argumentation frameworks using answer-set programming . In International Conference on Logic Programming (ICLP) , pages 734 { 738 . LNCS, Springer, 2008 .

16. R. Haenni . Probabilistic argumentation . J. Applied Logic , 7 ( 2 ): 155 { 176 , 2009 .

17. J. Janssen , M. De Cock , and D. Vermeir . Fuzzy argumentation frameworks . In Information Processing and Management of Uncertainty in Knowledge-based Systems , pages 513 { 520 , 2008 .

18. Audun J ¿sang, Roslan Ismail, and Colin Boyd . A survey of trust and reputation systems for online service provision . Decis. Support Syst ., 43 ( 2 ): 618 { 644 , 2007 .

19. H. Jung , M. Tambe , and S. Kulkarni . Argumentation as distributed constraint satisfaction: applications and results . In Conference on Autonomous agents (AGENTS) , pages 324 { 331 , New York, NY, USA, 2001 . ACM.

20. JuÄrg Kohlas . Probabilistic argumentation systems a new way to combine logic with probability . J. of Applied Logic , 1 ( 3 -4): 225 { 253 , 2003 .

21. S. Kraus , K. Sycara , and A. Evenchik . Reaching agreements through argumentation: a logical model and implementation . Artif. Intell., 104 ( 1-2 ):1{ 69 , 1998 .

22. K. Kuchcinski and R. Szymanek . Jacop - java constraint programming solver , 2001 . http://jacop.osolpro.com/.

23. S. Modgil . Reasoning about preferences in argumentation frameworks . Artif . Intell., 173 ( 9 -10): 901 { 934 , 2009 .

24. U. Montanari. Networks of constraints: Fundamental properties and applications to picture processing . Inf. Sci. , 7 : 95 { 132 , 1974 .

25. J. C. Nieves , U. Cort¶es, and M. Osorio . Possibilistic-based argumentation: An answer set programming approach . In Mexican International Conference on Computer Science(ENC) , pages 249 { 260 . IEEE Computer Society, 2008 .

26. J. O'Madadhain , D. Fisher, S. White , and Y. Boey. The JUNG ( Java Universal Network/Graph) framework . Technical report, UC Irvine , 2003 .

27. M. Schroeder and R. Schweimeier . Fuzzy argumentation for negotiating agents . In AAMAS , pages 942 { 943 . ACM, 2002 .