Finding Partitions of Arguments with Dung’s Properties via SCSPs Stefano Bistarelli1,2 , Paola Campli3 , and Francesco Santini1 1 Dipartimento di Matematica e Informatica, Università di Perugia, Italy [bista,francesco.santini]@dmi.unipg.it 2 Istituto di Informatica e Telematica (CNR), Pisa, Italy [stefano.bistarelli]@iit.cnr.it 3 Dipartimento di Scienze, Università G.d’Annunzio di Chieti-Pescara, Italy campli@sci.unich.it Abstract. Forming coalition structures allows agents to join their forces to achieve a common task. We suggest it would be interesting to look for homogeneous groups which follow distinct lines of thought. For this reason, we extend the Dung Argumentation Framework in order to deal with coalitions of arguments. The initial set of arguments is partitioned into subsets (or coalitions). Each coalition represents a different line of thought, but all the found coalitions show the same property inherited by Dung, e.g. all the coalitions in the partition are admissible (or conflict- free, complete, stable). Some problems in weighted argumentation are NP complete; we use (soft) constraints as a formal approach to reason about coalitions and to model all these problems in the same framework. Semiring algebraic structures can be used to model different optimiza- tion criteria for the obtained coalitions. To implement this mapping and practically find its solutions we use JaCoP, a Java constraint solver, and we test the code over a small-world network. 1 Introduction and Motivations A coalition structure is a temporary alliance or partnering of groups in order to achieve a common purpose. Forming coalitions with other members of similar values, interests and goals, allow agents to combine their resources and become more powerful than when they each acted alone [12]. To form a successful coali- tion, the recognition of compatible interests and common lines of thought is needed, since the goal of different agents can be shared by multiple parties. The abstract nature of Dung’s seminal theory [9] of argumentation accounts for its widespread application for various species of non-monotonic reasoning. A Dung argumentation framework (see Sect. 2) is classically instantiated by argu- ments and a binary conflict based attack relation, defined by some underlying logical theory. The justified arguments under different extensional semantics (e.g. conflict-free ones) are then evaluated, and the claims of these arguments define the inferences of the underlying theory. The aim of this paper is to partition a set of arguments into coalition structures of arguments [8, 1, 6]. A classical scenario could be represented by the need to aggregate a set of distinct arguments into different lines of thought. Suppose, for example, to have some statements belong- ing to candidates of different political parties; it would be interesting to check how consistent their ideas are. For 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”. In general, cooperating groups, referred to as coalition structures [16], have been thoroughly investigated in AI and Game Theory and have proved to be useful in both real-world economic scenarios and Multi-agent Systems [16, 19, 2]. The basic idea behind this work is to start from a single set of arguments and partition them to several agents, with the condition that each subset has to show the same properties defined by Dung, e.g. admissibil- ity [9]. Some applications might be task allocation problem (let tasks be the agents), sensor network problems (agents must form groups), distributed winner determination in combinatorial auctions, agents grouping to handle work-flows (just-in-time incorporation) [16, 19, 2]. In order to model and solve the proposed extended problems we use (Soft) Constraint Programming ((S)CP ) [18] (see Sect. 3), which is a powerful paradigm for solving combinatorial problems that draws on a wide range of techniques from AI, Databases, Programming Lan- guages, and Operations Research [18]. The idea of the semiring-based constraint formalism presented in [4, 3] was to further extend the classical constraint notion by adding the concept of a structure representing the levels of satisfiability of the constraints. Such a structure is similar to a semiring (see Sec. 3). Problems defined according to the semiring-based framework are called Soft Constraint Satisfaction Problems (SCSPs) [4, 3, 18]. There already exist many efficient tech- niques, as constraint propagation [18], to solve such complex problems. The solu- tion of the obtained SCSP represents the partition of the arguments (see Sec. 4) where each subset (i.e. coalition) of arguments has the same property originally defined by Dung in [9], e.g. each coalition in the partition is admissible. Semi- rings can be used to relax conflict-free partitions, by allowing a certain degree of conflicts inside the coalitions, by representing a weight (or preference) associ- ated with each attack between arguments (see Sec. 5 - 6). At last (in Sec. 7), we show an implementation of a crisp CSP (equivalent to use a Boolean semiring in SCSPs) with the Java Constraint Programming solver (JaCoP ) [15] and we test it over a small-world network randomly generated with the Java Universal Network/Graph Framework (JUNG) [17]. 2 Dung Argumentation Dung proposed an abstract framework for argumentation in which he focuses on the definition of the status (attacked / defended ) of arguments [9]. It can be assumed that a set of arguments and the different conflicts among them are given. Definition 1 ([9]). An Argumentation Framework (AF) is a pair hA, Ri of a set A of arguments and a binary relation R on A 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. a b c Rainy and Mild Sunny Breeze windy Fig. 1: A classical AF using weather forecast; e.g. b attacks c and viceversa. In Fig. 1 we show an example of AF represented as an interaction graph. Dung [9] gave several semantics of “acceptability”, which produce none, one or several acceptable sets of arguments, called extensions. The stable semantics is only defined via the notion of attacks: Definition 2 ([9]). A set B ⊆ A is conflict-free iff for no two arguments a and b in B, a attacks b. A conflict-free set B ⊆ A is a stable extension iff each argument not in B is attacked by an argument in B. The other semantics for “acceptability” rely upon the concept of defense. An admissible set of arguments according to Dung must be a conflict-free set which defends all its elements. Formally: Definition 3 ([9]). An argument b is defended by a set B ⊆ A (or B defends b) iff for any argument a ∈ A, if a attacks b then B attacks a. A conflict-free set B ⊆ A is admissible iff each argument in B is defended by B Besides the stable semantics, one semantics refining admissibility has been introduced by Dung [9]. Definition 4 ([9]). An admissible B ⊆ A is a complete extension iff each ar- gument which is defended by B is in B. In Fig. 2 we show an example of a stable (A), admissible (B) but not complete (due to x6 ) and complete (C) extension. 3 Semirings and Soft Constraints A semiring [4, 3] S is a tuple hA, +, ×, 0, 1i where A is a set with two special elements 0, 1 ∈ A (respectively the bottom and top elements of A) and with two operations + and × that satisfy certain properties: + is defined over (possibly infinite) sets of elements of A and is commutative, associative and idempotent; (A) (B) (C) X2 X2 X2 X5 X5 X5 X4 X4 X4 X1 X1 X1 X6 X6 X6 X3 X3 X3 X7 X7 X7 Fig. 2: A stable (A), an admissible (B) and a complete (C) extension (clearly also conflict-free). it is closed, 0 is its unit element and 1 is its absorbing element; × is closed, associative, commutative and distributes over +, 1 is its unit element and 0 is its absorbing element (for the exhaustive definition, please refer to [4]). 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. Moreover, + and × are monotone on ≤S , 0 is its min and 1 its max, hA, ≤S i is a complete lattice and + is its lub. A soft constraint [4, 3] 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 depends on the assignment of only a finite subset of V . 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, or scope, of the constraint). Note that cη[v := d1 ] means cη 0 where η 0 is η modified with the assignment v := d1 . Notice 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. ā represents the constraint functions associating a to all assignments of domain values. Given the set C, the combination function ⊗ : C × C → C is defined as (c1 ⊗ c2 )η = c1 η × c2 η [4, 3]. The ⊗ builds a new constraint 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 projection P[4, 3] 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. An SCSP [3] is defined as P = hCi where C is the set of constraints. The best level N of consistency notion defined as blevel(P ) = Sol(P ) ⇓∅ , where Sol(P ) = C [3]. A problem P is α-consistent if blevel(P ) = α [3]; P is instead simply “consistent” iff there exists α >S 0 such that P is α-consistent [3]. P is inconsistent if it is not consistent. An SCSP Example. Figure 3 shows a weighted SCSP as a graph: the Weighted semiring is used, i.e. hR+ ∪ ∞, min, +̂, ∞, 0i (+̂ is the arithmetic plus operation). Variables and constraints are represented respectively by nodes and arcs (unary for c1 and c3 , and binary for c2 ), and semiring values are written to the right of each tuple, D = {a, b}. The solution of the CSP in Fig. 3 associates 1 5 5 9 1 5 2 c1 2 c3 X Y c2 Fig. 3: An SCSP based on a Weighted semiring. a semiring element to every domain value of N variables X and Y by combining all the constraints together, i.e. Sol(P ) = C. 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. For the other tuples, ha, bi → 7, hb, ai → 16 and hb, bi → 16. The blevel for the example in Fig. 3 is 7, related to the solution X = a, Y = b. 4 Extending Dung Argumentation to Coalitions Given the set of arguments A, the problem of coalition formation consists in selecting an appropriate partition of A, G = {B1S, . . . , Bn } (|G| = |A| if each ar- gument forms a coalition on its own), such that Bi ∈G Bi = A and Bi ∩ Bj = ∅, if i 6= j; clearly, ∀i.Bi 6= ∅. In this section we extend Dung’s semantics (see Sec. 2) in order to deal with a partition of arguments, that is, we cluster the arguments into different subsets representing distinct lines of thought. An ex- ample representing the difference between the original framework [9] and our extension is illustrated in Fig. 4: Fig. 4 (A) represents a conflict-free extension as described in Def. 3, while Fig. 4 (B) represents a conflict-free partition of coalitions, since each coalition is conflict-free (see Def. 5). Thus, while in Dung it is sufficient to find only one set with the conflict-free property, we want to find a set of conflict-free sets that represents a partition of the given arguments; we can compute partitions by considering the other properties as well, i.e. ad- missible, complete and stable semantics. Notice that, in general, we can have a combinatorial number of partitions for a given set of arguments [7, 16]. For example, instead of P1 = {{x1 , x2 , x3 }, {x4 , x5 , }, {x6 , x7 , x8 , x9 }} we can have P2 = {{x1 , x2 , x3 , x4 }, {x5 }, {x6 , x7 , x8 , x9 }}. We can have 21147 different par- titions for the 9 elements in Fig. 4 (B): this number is called Bell Number and X n µ ¶ n is recursively computed as Bn+1 = Bk [7] (with B0 = B1 = 1). Clearly, k k=0 not all of these partition are (e.g.) conflict-free. In the following, we extend the definitions given in Sec. 2 to deal with coali- tions. X2 (A) (B) X2 X6 X6 X4 X8 X4 X8 X3 X3 X7 X7 X5 X5 X9 X9 X1 X1 Fig. 4: Differences between classical Dung AF (A) and the extended partitioned framework (B). Definition 5. A partition of coalitions G = {B1 , B2 , . . . , Bn } is conflict-free iff for each Bi ∈ G, Bi is conflict-free, i.e. ∀a, b ∈ Bi .(a, b) 6∈ R: no attacking arguments inside the same coalition. From the argumentation theory point of view, finding a conflict-free partition of coalitions corresponds to partitioning the arguments into coherent subsets, in order to find feasible lines of thought which do not internally attack themselves. Now we revise the concept of attack/defence among coalitions and arguments and the notion of stable partitions of coalitions: (A) B3 X2 X5 X1 X7 X3 X6 X8 B1 X4 B2 (B) (C) X2 X1 X4 X5 X7 X1 X2 X3 X5 X3 X6 B1 B4 B2 X8 X4 X6 X7 B1 B2 B3 Fig. 5: A stable (A), an admissible and complete (B) and an admissible but not complete (C) partitions of coalitions. Definition 6. A coalition Bi attacks another coalition Bj if one of its elements attacks at least one element in Bj , i.e. ∃a ∈ Bi , b ∈ Bj s.t. a R b. Bi defends an attacked argument a, e.g. b R a, if ∃c ∈ Bi s.t. c R b. Definition 7. A conflict-free partition G = {B1 , B2 , . . . , Bn } is stable iff for each coalition Bi ∈ G, all its elements a ∈ Bi are attacked by all the other coalitions Bj with j 6= i, i.e. ∀a ∈ Bi , ∃b ∈ Bj .b R a (∀j 6= i). Fig. 5 (A) represents a stable partition: each argument in B2 (i.e. x4 ) is at- tacked by at least one argument in B1 (i.e. x3 ) and one argument in B3 (i.e. x6 ), and the same also holds for the arguments in B2 and B3 . To have a stable partition means that each of the arguments cannot be moved from one coali- tion to another without inducing a conflict in the new coalition. In the next two definitions we respectively extend the concept of admissible and complete extensions. However different definitions for stable partitions can also be defined, for instance one could require that each argument has to be attacked by some (rather than all of the) other coalitions. Definition 8. A conflict-free partition G = {B1 , B2 , . . . , Bn } of coalitions is admissible iff for each argument a ∈ Bi attacked by b ∈ Bj (i.e. b R a), ∃c ∈ Bi that attacks b ∈ Bj (i.e. c R b), that is each Bi defends all its arguments. According to Dung’s definition of admissible extension, “the set of all argu- ments accepted by a rational agent is a set of arguments which can defend itself against all attacks on it” [9]. Notice that if only one argument a in the interac- tion graph has no grandparents, it is not possible to obtain even one admissible partition: no argument in A is able to defend a. In Def. 8, we have naturally extended the definition of admissible extension [9] to coalitions: since each coali- tion represents the line of thought of an agent, each rational agent is able to defend its line of thought because it counter-attacks all its attacking lines. Fig. 5 (B) represents an admissible partition as it is conflict-free and both B1 and B2 defend themselves: x5 is defended by x6 and for the attack performed by x6 ∈ B2 , x2 and x3 are defended by x2 . Definition 9. An admissible partition G = {B1 , B2 , . . . , Bn } is a complete partition of coalitions iff each argument a which is defended by Bi is in Bi (i.e. a ∈ Bi ). Fig. 5 (B) is a complete partition because all the elements defended by B2 (i.e. x5 , x8 ) belong to B2 and all elements defended by B1 (x2 , x3 ) belong to B1 . Figure 5 (C) represents an admissible but not complete partition because x6 is defended also by coalitions B1 (via x1 ) and B2 (via x4 ) but belongs to B3 (defending it via x7 ). Intuitively, the notion of complete partition captures the rational agents who believe in every argument they can defend [9]. In Th. 1 we prove that each of the coalitions in every possible conflict-free partition is a conflict-free extension as defined by Dung [9]. Respectively, we can prove the same property for admissible, complete and stable partitions. Theorem 1. Given an AF hA, Ri as in Def. 1 and – given the set of all CF E conflict-free extensions which can be obtained over an interaction graph by using Dung’s semantics [9] (see also Sec. 2), each CF P conflict-free partition as defined in Def. 5 is a subset of them, i.e. CF P ⊆ CF E. – given the set of all AE admissible extensions [9], each AP admissible parti- tion as defined in Def. 8 is a subset of them, i.e. AP ⊆ AE. – given the set of all CE complete extensions [9], each CP complete partition as defined in Def. 9 is a subset of them, i.e. CP ⊆ CE. – given the set of all SE stable extensions [9], each SP stable partition as defined in Def. 7 is a subset of them, i.e. SP ⊆ SE. We can now define the hierarchy of the set inclusions among the proposed partitions like Dung has shown for set inclusions among classical extensions [9]: Theorem 2. Given the CF P S, AP S, CP S and SP S respectively the set of all conflict-free, admissible, complete and stable partitions, we have that SP S ⊆ CP S ⊆ AS ⊆ CF P S. These two theorems can be proved by reasoning on the sets of classical exten- sions defined in [9]: the partitions, as defined in this paper, directly inherit their properties. Notice that since our aim is to find partitions and not classical exten- sions, it is possible that, given the same set of arguments, a stable (for example) extension exists, but a stable partition may not be possible. Let us consider the following example: A = {a, b, c, d, e} and R = {(b, c), (c, d), (d, e), (e, b)}. Ac- cording to Dung’s stable semantics, this framework has two stable extensions: {a, b, d} and {a, c, e}; however, it has no stable partition since the argument a is not attacked and it cannot be in two sets. Even if the situation in which more agents agree about an argument might be possible in several scenarios, we want an argument to be held by exactly one agent, that is, the one who first declared it. This is not a limitation, because our goal is to simultaneously form distinct stable extensions within the same set of arguments, which represent different lines of thought to be assigned to different agents. An application in the real world corresponds to the partitioning of arguments to find the difference among political parties. Indeed, even if an argument might be put forward by several political parties, it is necessary that this argument belongs only to one coalition. 5 Weighted Partitions Weighted AFs extend Dung’s AFs by adding weight values to every edge in the attack graph, intuitively corresponding to the strength of the attack, or equiva- lently, how reluctant we would be to disregard it [5, 10]. In this section we define a quantitative framework where attacks have an associated preference/weight and, consequently, also the computation of the coalitions as presented in this paper has an associated weight representing the level of inconsistency we toler- ate in the solution: more specifically, “how much conflict” we tolerate inside a conflict-free partition, which can now include attacking arguments in the same coalition. Modeling this kind of problems as SCSPs (see Sec. 3) leads to a par- tition that optimizes the criteria defined by the chosen semiring, which is used to mathematically represent the attack weights. Fig. 6 represents weighted attack relationships among arguments; in this example A = {a, b, c}, a R b and c R b, moreover, each of these two attack rela- tionships is associated with a fuzzy weight (in [0, 1]) representing the strength of the attack: a attacks b with more strength (i.e. 0.5) than c attacks b (i.e. 0.9). In this case 0 represents the strongest possible attack and 1 the weakest one. Many other classical weighted AFs in literature can be modeled with semirings [5]. An argument can be seen as a chain of possible events that makes the hypothesis true. The credibility of a hypothe- 0.5 0.9 sis can then be measured by the total probability A B C that it is supported by arguments. The proper se- miring to solve this problem consists in the Proba- ˆ 0, 1i, where the bilistic semiring [3]: h[0..1], max, ×, arithmetic multiplication (i.e. ×)ˆ is used to compose the probability values together (assuming that the Fig. 6: A fuzzy Argumentation probabilities being composed are independent). The Framework with fuzzy scores modeling the attack strength. Fuzzy Argumentation [5] approach enriches the ex- pressive 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], max, min, 0, 1i can be used (e.g. in Fig. 6). In addition, the Weighted semiring hR+ ∪ ∞, min, +̂, ∞, 0i, where +̂ is the arithmetic plus (0 = ∞ and 1 = 0), can model the (e.g. money) cost of the attack: for example, the number of votes in support of the attack [10]. By using the Boolean semiring h{true, f alse}, ∨, ∧, f alse, truei we can cast the classic AF originally defined by Dung [9] in the same semiring-based framework (0 = f alse, 1 = true). The implementation in Sec. 7 models the use of a Boolean semiring, since it adopts crisp constraints. Definition 10 rephrases the notion of AF given by Dung (see Sec. 2) into semiring-based AF, i.e. an AFS : Definition 10 ([5]). A semiring-based Argumentation Framework (AFS ) is a quadruple hA, R, W, Si, where S is a semiring hA, +, ×, 0, 1i, A is a set of ar- guments, R the attack binary relation on A, and W : A × A −→ A a binary function called the weight function. Given a, b ∈ A, ∀(a, b) ∈ R, W (a, b) = s means that a attacks b with a strength level s ∈ A. In Def. 11 we define the notion of α-conflict-free partition: conflicts inside the same coalition can be now part of the solution until a cost threshold α is met, and not worse: Definition 11. Given a semiring-based Y AFS , a partition of coalitions G = {B1 , B2 , . . . , Bn } Q is α-conflict-free for AFS iff W (b, c) ≥S α (the uses the × of the ∀Bi ∈G.b,c∈Bi semiring). In Fig. 7 there is an example of a 0.5-conflict-free partition using a Fuzzy semiring, i.e. the × used to compose the weights corresponds to min. Notice that only the attacks within the same coalition are considered: min(0.6, 0.7, 0.5) = 0.5. Proposition 1. If a partition is α1 -conflict-free, then the same partition is also α2 -conflict-free if α1