Finding Partitions of Arguments with Dung's Properties via SCSPs

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 di®erent 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 con°ictfree, 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 di®erent optimization criteria for the obtained coalitions. To implement this mapping and practically ¯nd its solutions we use JaCoP, a Java constraint solver, and we test the code over a small-world network.

-

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 coalition, the recognition of compatible interests and common lines of thought is needed, since the goal of di®erent 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 arguments and a binary con°ict based attack relation, de¯ned by some underlying logical theory. The justi¯ed arguments under di®erent extensional semantics (e.g. con°ict-free ones) are then evaluated, and the claims of these arguments de¯ne 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 di®erent lines of thought. Suppose, for example, to have some statements belonging to candidates of di®erent 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 de¯ned by Dung, e.g. admissibility [ 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-°ows (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 Languages, 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 satis¯ability of the constraints. Such a structure is similar to a semiring (see Sec. 3). Problems de¯ned according to the semiring-based framework are called Soft Constraint Satisfaction Problems (SCSPs) [ 4, 3, 18 ]. There already exist many e±cient techniques, as constraint propagation [ 18 ], to solve such complex problems. The solution 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 de¯ned by Dung in [ 9 ], e.g. each coalition in the partition is admissible. Semirings can be used to relax con°ict-free partitions, by allowing a certain degree of con°icts inside the coalitions, by representing a weight (or preference) associated 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 de¯nition of the status (attacked / defended ) of arguments [ 9 ]. It can be assumed that a set of arguments and the di®erent con°icts among them are given.

De¯nition 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. 8ai; aj 2 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 2 B which attacks an argument c 2 C. a

Sunny b

Rainy and windy c

Mild Breeze

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 de¯ned via the notion of attacks: De¯nition 2 ([ 9 ]). A set B µ A is con°ict-free i® for no two arguments a and b in B, a attacks b. A con°ict-free set B µ A is a stable extension i® 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 con°ict-free set which defends all its elements. Formally: De¯nition 3 ([ 9 ]). An argument b is defended by a set B µ A (or B defends b) i® for any argument a 2 A, if a attacks b then B attacks a. A con°ict-free set B µ A is admissible i® each argument in B is defended by B

Besides the stable semantics, one semantics re¯ning admissibility has been introduced by Dung [ 9 ].

De¯nition 4 ([ 9 ]). An admissible B µ A is a complete extension i® each argument 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 2 A (respectively the bottom and top elements of A) and with two operations + and £ that satisfy certain properties: + is de¯ned over (possibly in¯nite) sets of elements of A and is commutative, associative and idempotent; X1

X2

X3

X4

X7 (A) X5 X6

X1

X2

X3

X4

X7 (B) X5 X6

X2 X1 X6

X3 X4

X7 (C) X5 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 de¯nition, please refer to [ 4 ]). 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. 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 ¯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 depends on the assignment of only a ¯nite 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 fx; yg µ V (the support, or scope, of the constraint). Note that c´[v := d1] means c´0 where ´0 is ´ modi¯ed 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. a¹ represents the constraint functions associating a to all assignments of domain values. Given the set C, the combination function ­ : C £ C ! C is de¯ned 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 2 C and a variable v 2 V , the projection [ 4, 3 ] 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.

An SCSP [ 3 ] is de¯ned as P = hCi where C is the set of constraints. The best level of consistency notion de¯ned as blevel(P ) = Sol(P ) +;, where Sol(P ) = N C [ 3 ]. A problem P is ®-consistent if blevel(P ) = ® [ 3 ]; P is instead simply \consistent" i® 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+ [ 1; min; +^ ; 1; 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 = fa; bg. The solution of the CSP in Fig. 3 associates c1 a semiring element to every domain value of variables X and Y by combining all the constraints together, i.e. Sol(P ) = N 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 = fB1; : : : ; Bng (jGj = jAj if each argument forms a coalition on its own), such that SBi2G Bi = A and Bi \ Bj = ;, if i 6= j; clearly, 8i: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 di®erent subsets representing distinct lines of thought. An example representing the di®erence between the original framework [ 9 ] and our extension is illustrated in Fig. 4: Fig. 4 (A) represents a con°ict-free extension as described in Def. 3, while Fig. 4 (B) represents a con°ict-free partition of coalitions, since each coalition is con°ict-free (see Def. 5). Thus, while in Dung it is su±cient to ¯nd only one set with the con°ict-free property, we want to ¯nd a set of con°ict-free sets that represents a partition of the given arguments; we can compute partitions by considering the other properties as well, i.e. admissible, 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 = ffx1; x2; x3g; fx4; x5; g; fx6; x7; x8; x9gg we can have P2 = ffx1; x2; x3; x4g; fx5g; fx6; x7; x8; x9gg. We can have 21147 di®erent partitions for the 9 elements in Fig. 4 (B): this number is called Bell Number and n µn¶ is recursively computed as Bn+1 = X Bk [ 7 ] (with B0 = B1 = 1). Clearly, k=0 k not all of these partition are (e.g.) con°ict-free.

In the following, we extend the de¯nitions given in Sec. 2 to deal with coalitions. X3

X1

X4 X5

X6 X7

(A) X8 X9 X3 X1

X4 X5

X6 X7

X8 X9 (B) De¯nition 5. A partition of coalitions G = fB1; B2; : : : ; Bng is con°ict-free i® for each Bi 2 G, Bi is con°ict-free, i.e. 8a; b 2 Bi:(a; b) 62 R: no attacking arguments inside the same coalition.

From the argumentation theory point of view, ¯nding a con°ict-free partition of coalitions corresponds to partitioning the arguments into coherent subsets, in order to ¯nd 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:

X1 B1

X2

X3 X4

X1 B1 (B)

X2 X3 B2 X5 X6 (A) X4 X7 X8

B2

X5 X6 B1

X1 X2

B3 X7 X8 (C)

X3 B4 X6

X7

X4 X5 B3

B2

De¯nition 6. A coalition Bi attacks another coalition Bj if one of its elements attacks at least one element in Bj , i.e. 9a 2 Bi; b 2 Bj s.t. a R b. Bi defends an attacked argument a, e.g. b R a, if 9c 2 Bi s.t. c R b.

De¯nition 7. A con°ict-free partition G = fB1; B2; : : : ; Bng is stable i® for each coalition Bi 2 G, all its elements a 2 Bi are attacked by all the other coalitions Bj with j 6= i, i.e. 8a 2 Bi; 9b 2 Bj :b R a (8j 6= i).

Fig. 5 (A) represents a stable partition: each argument in B2 (i.e. x4) is attacked 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 coalition to another without inducing a con°ict in the new coalition. In the next two de¯nitions we respectively extend the concept of admissible and complete extensions.

However di®erent de¯nitions for stable partitions can also be de¯ned, for instance one could require that each argument has to be attacked by some (rather than all of the) other coalitions.

De¯nition 8. A con°ict-free partition G = fB1; B2; : : : ; Bng of coalitions is admissible i® for each argument a 2 Bi attacked by b 2 Bj (i.e. b R a), 9c 2 Bi that attacks b 2 Bj (i.e. c R b), that is each Bi defends all its arguments.

According to Dung's de¯nition of admissible extension, \the set of all arguments 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 interaction 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 de¯nition of admissible extension [ 9 ] to coalitions: since each coalition 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 con°ict-free and both B1 and B2 defend themselves: x5 is defended by x6 and for the attack performed by x6 2 B2, x2 and x3 are defended by x2.

De¯nition 9. An admissible partition G = fB1; B2; : : : ; Bng is a complete partition of coalitions i® each argument a which is defended by Bi is in Bi (i.e. a 2 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 con°ict-free partition is a con°ict-free extension as de¯ned 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 con°ict-free extensions which can be obtained over an interaction graph by using Dung's semantics [ 9 ] (see also Sec. 2), each CF P con°ict-free partition as de¯ned 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 partition as de¯ned 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 de¯ned 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 de¯ned in Def. 7 is a subset of them, i.e. SP µ SE.

We can now de¯ne 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 con°ict-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 extensions de¯ned in [ 9 ]: the partitions, as de¯ned in this paper, directly inherit their properties. Notice that since our aim is to ¯nd partitions and not classical extensions, 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 = fa; b; c; d; eg and R = f(b; c); (c; d); (d; e); (e; b)g. According to Dung's stable semantics, this framework has two stable extensions: fa; b; dg and fa; c; eg; 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 ¯rst 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 di®erent lines of thought to be assigned to di®erent agents. An application in the real world corresponds to the partitioning of arguments to ¯nd the di®erence 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 equivalently, how reluctant we would be to disregard it [ 5, 10 ]. In this section we de¯ne 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 tolerate in the solution: more speci¯cally, \how much con°ict" we tolerate inside a con°ict-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 partition that optimizes the criteria de¯ned 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 = fa; b; cg, a R b and c R b, moreover, each of these two attack relationships 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 tshise chaynptohthenesibsetrmueea.sTurheed cbryedtibhielittyotoafl aprhoybpabotilhitey- A 0.5 B 0.9 C that it is supported by arguments. The proper semiring to solve this problem consists in the Probabilistic semiring [ 3 ]: h[0::1]; max; £^ ; 0; 1i, where the 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 Fmroadmeeliwnogrkthewaittthackfusztzreyngstcho.res Fuzzy Argumentation [ 5 ] 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]; max; min; 0; 1i can be used (e.g. in Fig. 6). In addition, the Weighted semiring hR+ [ 1; min; +^ ; 1; 0i, where +^ is the arithmetic plus (0 = 1 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 hftrue; f alseg; _; ^; f alse; truei we can cast the classic AF originally de¯ned 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. De¯nition 10 rephrases the notion of AF given by Dung (see Sec. 2) into semiring-based AF, i.e. an AFS : De¯nition 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 arguments, R the attack binary relation on A, and W : A £ A ¡! A a binary function called the weight function. Given a; b 2 A, 8(a; b) 2 R, W (a; b) = s means that a attacks b with a strength level s 2 A.

In Def. 11 we de¯ne the notion of ®-con°ict-free partition: con°icts inside the same coalition can be now part of the solution until a cost threshold ® is met, and not worse: De¯nition 11. Given a semiring-based AFS , a partition of coalitions G = fB1; B2; : : : ; Bng is ®-con°ict-free for AFS i® Y W (b; c) ¸S ® (the Q uses the £ of the semiring).

8Bi2G:b;c2Bi

In Fig. 7 there is an example of a 0:5-con°ict-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-con°ict-free, then the same partition is also ®2-con°ict-free if ®1 <S ®2.

For instance, in Weighted semirings a 3-con°ict-free partitions is also 4con°ict-free. In Def. 12 we extend with weights also the other kinds of partitions. De¯nition 12. Given an AFS , a partition of coalitions G = fB1; B2; : : : ; Bng can be de¯ned as ®-stable (or ®-admissible or ®-complete) by only replacing con°ict-free partitions with ®-con°ict-free partitions in Def. 7 (or Def. 8 or Def. 9).

In Prop. 2 we relate the weighted partitions with those not weighted presented in Sec. 4.

Proposition 2. I® a partition is 1-con°ict-free (or 1-stable, 1-admissible, 1complete), then the same partition is also con°ict-free (or stable, admissible, complete) as shown in Sec. 4.

As a proof sketch, no attacks are present in the same coalition since 1 means \no attack", being the top element of the semiring.

B1 0.6 X2 X1

X3 0.2

X5 0.7

X6

X7

Mapping Partition Problems to SCSPs

In this section we show a mapping from the AFS extended to coalitions (see Sec. 5) to SCSPs (see Sec. 3), i.e. M : AFS ! SCSP . M is described as follows: given an AFS as described in Sec. 5, we de¯ne a variable for each argument ai 2 A, i.e. V = fa1; a2; : : : ; ang. The value of a variable represents the coalition to which argument ai belongs: i.e. each variable domain is D = f1; ng. For example if a1 = 2 it means that the ¯rst argument belongs to the second coalition. We can have a maximum of n coalitions, that is all singletons.

In the following explanation, \b attacks a" means that b is a parent of a in the corresponding interaction graph, and \c attacks b attacks a" means that c is a grandparent of a. For the following constraint classes we consider a AFS = hA; R; W; Si where S = hA; +; £; 0; 1i and s 2 A: 1. Con°ict-free constraints. Since we want to ¯nd an ®-con°ict-free partition, if ai R aj and W (ai; aj ) = s we need to assign a s preference to the solution that includes both ai and aj in the same coalition of the partition: cai;aj (ai = k; aj = k) = s. Otherwise cai;aj (ai = k; aj = l) = 1 (with l 6= k). 2. Admissible constraints. For the admissibility of a partition, if ai has several grandparents ag1; ag2; : : : ; agk the parent af , we need to add a k + 1ary constraint cai;ag1;:::;agk (ai = h; ag1 = j1; : : : ; agk = jk) = 0 if 8ji; ji 6= h (1 otherwise). This is because at least a grandparent must be taken in the same coalition, in order to defend ai from his parent af . Notice that, if an argument is not attacked (i.e. has no parents), it can be taken or not in any admissible set. Moreover, if ai has a parent but no grandparents, it is not possible to ¯nd any admissible partition, that is the SCSP is inconsistent (see Sec. 3). 3. Complete constraints. If we have an argument ai with multiple grandchildren as1; as2; : : : ; ask, we need to add the constraint cai;as1;:::;ask (ai = j; as1 = j; : : : ; ask = j) = 1 (0 otherwise). In words, if ai is taken in a coalition j, all of its grandchildren must be included in the same coalition because j has to include all the defended arguments. 4. Stable constraints. They can be represented with a constraint such that for each pair of arguments ai; aj belonging to two di®erent coalitions, respectively k and z, at least one of the attacks to aj has to come from an argument in coalition k: if b1; b2; : : : bn are all the arguments that attack aj , cai=k;aj6=k;b1;b2;:::;bn ((b1 = k) _ (b2 = k) _ ¢ ¢ ¢ _ (bn = k)) = 1 (0 otherwise). Therefore, we model stable constraints with disjunctive constraints, which are di±cult to solve.

Notice that in M only con°ict-free constraints are soft in the strict sense, while the other constraints are associated with 0 (not admitted) or 1 (admitted) values of the semiring set.

Theorem 3 (Solution equivalence). Given an AFS = hA; R; W; Si, the solutions of the related SCSP obtained with the mapping M correspond to: { all the ®-con°ict-free partitions of coalitions by using con°ict-free constraints; { all the ®-stable partitions by using stable and con°ict-free constraints; { all the ®-admissible partitions by using admissible, and con°ict-free constraints; { all the ®-complete partitions by using complete and con°ict-free constraints.

Con°ict-free, stable, admissible and complete partitions can be found by searching for 1-consistent solutions in the respective problems de¯ned in Th. 3, as de¯ned in Prop. 2. Notice that ¯nding 1-con°ict-free partitions is equivalent to well-known graph coloring problems which have been deeply studied also in constraint programming [ 18 ], where no two adjacent vertices share the same color: Proposition 3. The problem of ¯nding a con°ict-free partition of coalitions corresponds to ¯nding a vertex-coloring partition of a graph [ 18 ], where each node of the same color belongs to the same coalition in a 1-con°ict-free partition. The minimum number of colors needed to solve the problem corresponds to the minimum number of coalitions in a possible partition.

In Fig. 8 we can see an example of classical (i.e. the attacks are not weighted) interaction graph. Only for this example we have 15 con°ict-free partitions reported in Tab. 1. Among these con°ict-free partitions, P1; P2; P3; P4; P5 are also admissible partitions and P1 is also the only one complete and stable partition; these partitions have been obtained with the implementation in Sec. 7.

X1

X2 X4

X5 Fig. 8: An interaction graph. The Java Constraint Programming solver [ 15 ] (JaCoP) is a Java library which provides a Finite Domain Constraint Programming paradigm [ 18 ].

To practically develop and test our model, we adopted the Java Universal Network/Graph Framework (JUNG ) [ 17 ], a software library for the modeling, generation, analysis and visualization of graphs. Interaction graphs, where nodes are arguments and edges are attacks (see Sec. 2), clearly represent a kind of social network and consequently show the related properties [ 6 ]. Therefore, for the following tests we used the KleinbergSmallWorldGenerator class [ 17, 14 ] in JUNG, which randomly generates a m£n lattice with small-world properties [ 14 ]; each node has 4 local connections and 1 long range connection chosen randomly. An example of such random graphs with 25 nodes is shown in Fig. 9.

In this ¯rst implementation we decided to only implement 1-con°ict-free partitions, i.e. we do not consider weights on the attacks, and therefore we only need the crisp constraints of JaCoP. With this tool we can immediately check if a given partition is con°ict-free, admissible, complete or stable. Moreover, we can exhaustively generate the partitions with such given properties: since the problem is O(nn) [ 16 ] (where n is the number of arguments) we limit the implementation to a partial search. In particular, we used the Limited Discrepancy Search (LDS ), which is a kind of Depth First Search procedure adopting the method proposed in [ 11 ]. If a given number of di®erent decisions along a search path is exhausted, then backtracking is initiated [ 15, 11 ]. Each time during the search, we select the variable which has most constraints assigned to it and we try the median from its current domain. Moreover, we set a timeout of 60 sec. to interrupt the search procedure and to report the number of solutions found only in that interval; we ran our experiments over 3 di®erent random graphs with 9, 25 and 100 nodes. The results are shown in Tab. 2: it reports the number of found con°ict-free and stable partitions (which limit the number of the other admissible and complete partitions as de¯ned in Th. 2), the number of constraints used to represent the problem and the measured max depth of the search tree. Notice that, within the 60 sec. timeout, the proposed partial search is able to ¯nd only one stable partition for 100 nodes; also the reported number of con°ict-free solutions in Tab. 2 is less for 100 than for 25 nodes. Therefore, further constraint solving techniques need to be used to improve these performance (left to future work in Sec. 9).

Notice that, in order to prevent symmetrically equivalent solutions we have also implemented symmetry breaking constraints for graph coloring as explained in [ 13 ] (see Prop. 3 for the analogies): any value permutation is a value symmetry in the coalition assignment of arguments. 8

Related Work and Comparison

The framework of Dung for argumentation is extended by Amgoud in [ 1 ] with a preference relation between elements; more in detail, Amgoud [ 1 ] provides the semantics (con°ict-free, stable and preferred ones) of a coalition structure and a proof theory for testing whether a coalition is in the set of acceptable coalitions. An application of the model is also provided for the problem of task allocation among partitions of autonomous agents. With respect to the work in this paper, the view in [ 1 ] is not focused on generating partitions of arguments, but on directly checking the property of already given coalition structures. Furthermore, [ 1 ] has no implementation to practically ¯nd solutions, as we instead do in Sec. 7. Moreover, the method to compute the weights of coalitions is not quantitative (but it is only qualitative) and parametric, as we are alternatively able to represent with semirings. In [ 8 ] an extension of the Alternating-time Temporal Logic (ATL) for modeling coalitions through argumentation is presented: a merge between ATL and the coalitional framework is obtained in order to express that agents are able to form a coalition which can successfully achieve a given property; the notions of defence and con°ict-free are de¯ned in terms of defeat rather than attack and preferences of arguments are given in a qualitative way (instead of quantitative as in our paper); to compute the desired classes of coalitions a model checker can be used; however, with such techniques, exponential complexity can be hardly faced while constraint programming provides a lot of techniques to tackle combinatorial problems [ 18 ]. In [ 6 ], social viewpoints (a model for goal based reasoning) are used to argue about coalitions in argumentation theory. The attack relation is based on the goal that agents have to achieve, that is, a coalition attacks another coalition if they share the same goal; this work does not provide a computational framework and only qualitative preferences over arguments are considered. In [ 5 ] a common computational and quantitative framework is presented, where attacks (and consequently, also the computation of the classical Dung's semantics) have an associated weight to represent how much inconsistency we tolerate in the solution. Our work extends [ 5 ] by considering partitions of arguments and showing an implementation in JaCoP (no implementation is given in [ 5 ]) with related tests on small-world graphs. Partitions of arguments implies rede¯ning the whole (argumentation) theory concepts w.r.t [ 5 ], e.g. stability. 9

Summary and Future Work

We extended classical argumentation frameworks of [ 9 ] to the problem of forming coalitions of arguments, partitioning all the arguments of a given starting set. We rede¯ned the classical de¯nitions of Dung's extensions (con°ict-free, admissible, stable and complete ones) in order to consider a partition of all the arguments into multiple coalitions, and modeled the problem of ¯nding such coalitions with SCSPs [ 4, 3, 18 ]: this semiring-based formalism can be used to relax the concept of con°ict-free partitions in order to allow some inconsistency (i.e. attacks) within the same coalition. The proposed quantitative framework can be used also to solve classical (i.e. crisp) CSPs. We have also solved a problem example considering only 1-solutions with JaCoP [ 15 ] and then we performed tests on a small-world network randomly generated with [ 17 ]. Starting from a single set of arguments, the goal has been to partition it into multiple coalitions with the same features (e.g. stability or admissibility) without discarding any argument. In the future we want to implement ®-con°ict-free, ®-stable, ®-admissible and ®-complete partitions in JaCoP, for ® <S 1. Moreover, we want to improve the performance obtained in Sec. 7 by testing di®erent solvers and constraint techniques (e.g. by taking the inspiration from [ 16 ]).

References

1. L. Amgoud . An argumentation-based model for reasoning about coalition structures . In ArgMAS05 , volume 4049 of LNCS , pages 217 { 228 . Springer, 2005 .

2. K. R. Apt and A. Witzel . A generic approach to coalition formation . CoRR, abs/0709.0435 , 2007 .

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

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

5. S. Bistarelli and F. Santini . A common computational framework for semiringbased argumentation systems . In ECAI'10 , volume 215 , pages 131 { 136 . IOS Press, 2010 .

6. G. Boella , L. van der Torre, and S. Villata . Social viewpoints for arguing about coalitions . In PRIMA , volume 5357 of LNCS , pages 66 { 77 . Springer, 2008 .

7. K. P. Bogart . Introductory Combinatorics. Academic Press, Inc., Orlando, FL, USA, 2000 .

8. N. Bulling , J. Dix , and C. I. Chesn~evar. Modelling coalitions: Atl + argumentation . pages 681 { 688 . IFAAMAS , 2008 .

9. 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 .

10. P. E. Dunne , A. Hunter , P. McBurney , S. Parsons , and M. Wooldridge . Inconsistency tolerance in weighted argument systems . pages 851 { 858 . IFAAMS , 2009 .

11. W. D. Harvey and M. L. Ginsberg . Limited discrepancy search . In IJCAI (1) , pages 607 { 615 , 1995 .

12. B. Horling and V. Lesser . A survey of multi-agent organizational paradigms . Knowl. Eng. Rev. , 19 ( 4 ): 281 { 316 , 2004 .

13. G. Katsirelos and T. Walsh . Dynamic symmetry breaking constraints . In Workshop on Modeling and Solving Problems with Constraints (at ECAI08) , pages 39 { 44 . Informal Proc ., 2008 .

14. J. Kleinberg . Navigation in a small world . Nature , 406 : 845 , 2000 .

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

16. N. Ohta , V. Conitzer , R. Ichimura , Y. Sakurai , A. Iwasaki , and M. Yokoo . Coalition structure generation utilizing compact characteristic function representations . In CP , volume 5732 of LNCS , pages 623 { 638 . Springer, 2009 .

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

18. F. Rossi , P. van Beek, and T. Walsh . Handbook of Constraint Programming. Elsevier Science Inc ., NY , USA, 2006 .

19. O. Shehory and S. Kraus . Task allocation via coalition formation among autonomous agents . In IJCAI (1) , pages 655 { 661 , 1995 .