Solving Weighted Argumentation Frameworks with Soft Constraints Stefano Bistarelli1,2 , Daniele Pirolandi1 and Francesco Santini2,3 1 Dipartimento di Matematica e Informatica, Università di Perugia, Italy [bista,pirolandi]@dmi.unipg.it 2 Istituto di Informatica e Telematica (CNR), Pisa, Italy [stefano.bistarelli,francesco.santini@]iit.cnr.it 3 Dipartimento di Scienze Università “G. d’Annunzio”, Pescara, Italy santini@sci.unich.it Abstract. We suggest soft constraints as a mean to parametrically rep- resent and solve “weighted” Argumentation problems: different kinds of preference levels related to arguments, e.g. a score representing a “fuzzi- ness”, a “cost” or a probability level of each argument, can be represented by choosing different 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 ex- tension, 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 map- ping from weighted Argumentation Frameworks to Soft Constraint Sat- isfaction 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. 1 Introduction 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, de- cision making, and dialogue. For instance, when an agent has conflicting beliefs (viewed as arguments), a (nontrivial) set of plausible consequences can be de- rived 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 Artificial In- telligence 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 the- ory of argumentation. A Dung Argumentation Framework (AF ) is a directed graph consisting of a set of arguments and a binary conflict based attack rela- tion among them. The sets of arguments to be considered are then defined under different 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 artificial 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 no- tion by adding the concept of a structure representing the levels of satisfiability 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 defined according to this semiring-based framework are called Soft Constraint Satisfaction Problems (SCSPs). In this paper we show that different weighted AFs based on fuzziness, prob- ability 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 different 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 argu- ments, and comparing the final 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 demon- stration 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 solu- tions 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 refine it by finding 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 back- ground 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 definition of the status of arguments. For that purpose, it can be assumed that a set of arguments is given, as well as the different conflicts among them. An argument is an abstract entity whose role is solely determined by its relations to other arguments. Definition 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. ∀ai , aj ∈ A, ai R 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 ∈ B which attacks an argument c ∈ 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 c d a Fig. 1. An example of Dung Argumentation Framework; e.g. c attacks 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 define the concepts of conflict- free and stable extensions: Definition 2. A set B ⊆ Args is conflict-free iff it does not exist two arguments a and b in B such that a attacks b. A conflict-free set B ⊆ Args is a stable extension iff 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: Definition 3. An argument b is defended by a set B ⊆ Args (or B defends b) iff for any argument a ∈ Args , if a attacks b then B attacks a. An admissible set of arguments according to Dung must be a conflict-free set which defends all its elements. Formally: Definition 4. A conflict-free set B ⊆ Args is admissible iff each argument in B is defended by B. Besides the stable semantics, three semantics refining admissibility have been introduced by Dung [12]: Definition 5. A preferred extension is a maximal (w.r.t. cardinality) admissible subset of Args . An admissible B ⊆ Args is a complete extension iff 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 ∈ A) and with two operations + and × that satisfy certain properties: + is defined over (possibly infinite) 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 definition, please refer to [7]). The + operation defines a partial order ≤S over A such that a ≤S b iff 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 finite 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 finite 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 {x, y} ⊆ V (the support of the constraint, or scope). Note that cη[v := d1 ] means cη 0 where η 0 is η modified 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 ā function returns the semiring value a). Given the set C, the combination function ⊗ : C × C → C is defined 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 ∈ C and a variable v ∈ V , the projectionP [7, 5, 6] of c over V − {v}, written c ⇓(V \{v}) is the constraint c0 such that c0 η = d∈D cη[v := d]. Informally, projecting means eliminating some variables from the support. A SCSP [5] defined 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” iff there exists α >S 0 such that P is α- consistent [5]. P is inconsistent if it is not consistent. The bestNlevel of consistency notion defined as blevel(P ) = Sol(P ) ⇓∅ , where Sol(P ) = ( C) ⇓con [5]. 1 5 5 9 1 5 2 c1 2 c3 X Y c2 Fig. 2. A soft CSP based on a Weighted semiring. 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, +̂, ∞, 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 first 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 argumen- tation 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 different admissible extensions repre- sented by the sets {A} and {B}, but neither argument is sceptically justified. One solution is to provide some means for preferring one argument to another in order to find 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 {A} with a score of 0.9 over {B} with a score of 0.7, i.e. forecast from BBC than from CCN. 0.9 0.7 BBC CNN sunshine rain Fig. 3. The CNN /BBC example with trust scores. In some works [17] the preference score is associated with the attack rela- tionship 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 compos- ing 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 defined 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)\2 = 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]. 0.9 0.5 FOX BBC CNN sunshine rain sunshine Fig. 4. A fuzzy Argumentation Framework with fuzzy scores modeling the attack strength. Notice that in [23, 3, 2] the preference among arguments is given in a quali- tative 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 fulfil these different tasks. An argument can be seen as a chain of possible events that makes the hy- pothesis 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 ˆ 0, 1i, where the problem consists in the Probabilistic semiring [5]: h[0..1], max, ×, ˆ arithmetic multiplication (i.e. ×) is used to compose the probability values to- gether. 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 arith- metic 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 efforts or resources he should spend to counteract an argument of the opposing party. At last, with the Boolean semiring h{true, f alse}, ∨, ∧, f alse, truei we can cast the classic AFs originally defined by Dung [12] in the same semiring-based framework. Moreover, notice that the cartesian product of two semirings is still a semir- ing [7, 5], and this can be fruitfully used to describe multi-criteria constraint satisfaction and optimization problems. For example, we can have both a prob- ability and a fuzzy score given by a couple ht, f i; we can optimize both costs at the same time. We can extend the definitions provided in Sec. 3 in order to express all these weights of the attack relations with a semiring based environment. The following definitions model the semiring-based problem. Definition 6. A semiring-based Argumentation Framework (AFS ) is a quadru- ple 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. ∀a ∈ Args , W (a) = s means that a has a preference level s ∈ A. Therefore, the weight function W associates each argument with a semir- ing value (s ∈ 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 {A} (with a score of 0.9) is better than the other admissible extension {B} (with a s.core of 0.7) since 0.9 > 0.7. There- fore, with an AFS our goal is to find 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, +̂, ∞, 0i and Args = {a, b, c, d, e}, 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 define a variable for each argument ai ∈ Args , i.e. V = {a1 , a2 , . . . , an } and each of these argument can be taken or not, i.e. the domain of each variable is D = {1, 0}, 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 7 20 6 a b c e d 12 10 Fig. 5. An example of a weighted interaction graph. modeling, for example, the conflict-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 define specific sets of constraints: 1. Preference constraints. The weight function W (ai ) = s (s ∈ 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. Conflict-free constraints. Since we want to find the conflict-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 conflict. 3. Admissible constraints. For the admissibility, we need that, if child ar- gument 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 par- ents 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 satisfied; 0 otherwise. 5. Stable constraints. If we have a child node ai with multiple parents af 1 , af 2 , . . . , af k , we need to add the constraint cai ,af 1 ,...,af k (ai = 0, af 1 = 0, . . . , af k = 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, af j = 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 con- straints 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 find over AFS the best(according to +) – conflict-fee extensions by using preference and conflict-free constraint classes. – admissible extensions by using preference, conflict-free and admissible con- straint classes. – complete extensions by using preference, conflict-free and admissible con- straint classes. – stable extensions by using preference, conflict and stable constraint classes. By using the Boolean semiring the solutions of the (S)CSP respectively corre- spond to all the classical admissible, complete and stable extensions of Dung [12]. Moreover, to find the preferred extension (see Sec. 2) we simply need to find all the maximal (w.r.t. set inclusion) admissible extensions of Args , that is to find all the admissible sets (using the first 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 find all the complete extensions (the first 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, +̂, ∞, 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 Different interpretations of grounded/preferred extensions can be given by consider- ing 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 find further requirements on the sets of arguments which are expected as extensions, like “extensions must contain ar- gument 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 li- brary, which provides Java user with Finite Domain Constraint Programming paradigm. It provides different type of constraints: most commonly used prim- itive constraints, such as arithmetical constraints, equalities and inequalities, logical, reified and conditional constraints, combinatorial (global) constraints. The last version of JaCoP proposes many features, such as pruning events, mul- tiple constraint queues, special data structures to handle efficiently 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 definition in JaCoP of all the conflict-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 first conflict-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 satisfied if both variables are taken in the set. Considering the example in Fig. 5 the admissible sets are: {a}, {c}, {d}, {a, c}, {a, d}. Dung’s semantics induce the following acceptable sets: one stable exten- sion {a, d}, two preferred extensions P E1 = {a, c}, P E2 = {a, d}, three complete extensions CE1 = {a, c}, CE2 = {a, d}, CE3 = {a} and the grounded extension ≡ {a}. With our quantitative interpretation of AFs with preferences and con- sidering the Fuzzy semiring hR+ , min, +̂, ∞, 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 unification and incor- porated it into a novel fuzzy argumentation framework for extended logic pro- gramming: 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 Frame- works (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 preference- based argumentation frameworks. Preferences are represented with a preordering relationships (partial or total) that resembles the ordering defined 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 ques- tions (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 pre- served, 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 inves- tigate 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 difficult 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 ). Different agents represent the distributed points in the problem. The paper shows the ap- propriateness of constraints in solving large-scale argumentation systems. How- ever, 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 exten- sions for a broad range of formalizations of Dung’s argumentation framework and generalizations thereof, e.g. value-based AFs [3] or preference-based [2]. AS- PARTIX relies on a fixed 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 specified 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 conflict-free extensions to α-conflict-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 as- sociate the argument preference with a weight (taken from a semiring structure) that represents the “goodness” of the argument in terms of cost, fuzziness, prob- ability 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 finding the solution of the related AF. We have proposed an unifying computa- tional framework with strong mathematical foundations and solving techniques, where by only parametrically changing the semiring we can deal with different weighted (or not) AFs. By having a uniform framework, it may be possible to see more clearly the relationships between different proposals. It may also offer 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 efficiently satisfy the constraints. Constraint solving techniques prove to be able to deal with large scale problems [19], even if the treated problems are difficult: for example, deciding if a set is a preferred extension is a CO- N 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 negotia- tion process, inside different 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 argu- mentation frameworks. Int. J. Intell. Syst., 23(10):1062–1093, 2008. 2. L. Amgoud and C. Cayrol. Inferring from inconsistency in preference-based argu- mentation frameworks. J. Autom. Reasoning, 29(2):125–169, 2002. 3. T. J. M. Bench-Capon. Persuasion in practical argument using value-based argu- mentation 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 frame- works with soft constraints. Technical report, Dipartimento di Scienze, Uni- versità 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 semiring- based argumentation systems. In European Conference on Artificial Intelligence (ECAI10), 2010. 11. S. Coste-Marquis, C. Devred, and P. Marquis. Constrained argumentation frame- works. 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. Inconsis- tency 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. Incon- sistency 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 Sys- tems, 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. Jü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 argumenta- tion: 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. In- tell., 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és, and M. Osorio. Possibilistic-based argumentation: An answer set programming approach. In Mexican International Conference on Com- puter 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.