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