=Paper=
{{Paper
|id=Vol-494/paper-12
|storemode=property
|title=Four Ways to Change Coalitions: Agents, Dependencies, Norms and Internal Dynamics
|pdfUrl=https://ceur-ws.org/Vol-494/coinpaper3.pdf
|volume=Vol-494
|dblpUrl=https://dblp.org/rec/conf/mallow/BoellaTV09
}}
==Four Ways to Change Coalitions: Agents, Dependencies, Norms and Internal Dynamics==
https://ceur-ws.org/Vol-494/coinpaper3.pdf
Four Ways to Change Coalitions:
Agents, Dependencies, Norms and Internal Dynamics
Guido Boella Leendert van der Torre Serena Villata
University of Turin University of Luxembourg University of Turin
Italy Luxembourg Italy
Email: guido@di.unito.it Email: leon.vandertorre@uni.lu Email: villata@di.unito.it
Abstract software engineering where the designer models all stake-
holders [2], and social simulation where no such assumption
We introduce a new formal approach to social networks is made [8]. In the former, game theory can be used for
in order to distinguish four ways in which coalitions change. reasoning about social interaction, in the latter simulation
First, the agents in the network change. Second, dependen- methods are used. We follow the tradition of TROPOS [2]
cies among the agents change, for example due to addition for requirements analysis, as formalized by Sauro [5] and
or removal of powers and goals of the agents. Third, norms close to qualitative game theories developed by Wooldridge
can introduce normative dependencies for obligations and et al. [1], not the latter [8].
prohibitions. Fourth, coalitions can change due to internal Changes of the dependencies related to norms.Norms
processes. We propose a number of stability measures to are used for the dynamics of dependence networks, which
identify each one of the four proposed sources of coalitions’ explained why they have not been considered thus far in
dynamics and the consequences they induce on the stability the static dependence networks [9]. A norm analytically
of coalitions. implies that agents (intend to) execute them, and therefore
leads to dependencies among agents just like the original
1. Introduction goal-based dependencies studied by Sichman and Conte [9].
Norms should be clearly distinguished from obligations.
Coalitions play a central role in social reasoning, and More precisely, norms are used to generate new dependence
thus various theories have been used and developed in mul- networks in which a number of dependencies are normative
tiagent systems. For example, coalitional game theory has ones. Within a dependence network, the effect of the norm
been adopted from economics and extended for multiagent consists in a normative goal such as an obligation. These
systems [6], [7], and social networks have been adopted normative goals, i.e., obligations, are treated just like goals
from social sciences and modified to represent dependence derived from the agent’s desires. The coalitions which may
networks among agents [8], [4], [5]. These theories differ in emerge depend on the dependencies among the agents, so
various ways. For example, in the former, potential coalitions since norms change the dependencies among agents, they
may be seen as sets of agents while in the latter, dependence also change the coalitions which will emerge.
networks can be seen as criteria for proposing/accepting Internal dynamics. Changes of the coalition itself in terms
to form coalitions [8], or potential coalitions are viewed of goal-based and norm-based dependencies composing the
as sets of dependencies (the dependencies represent the coalition, e.g., an agent is excluded from a coalition because
contract of the potential coalition) [5]. Moreover, in the of a malicious behaviour.
former various notions of stability are defined, whereas in We call the last kind of change internal dynamics to
the latter they are not. In this paper, we address the question distinguish it from the other dynamics related to the ad-
how to distinguish and model the different reasons behind dition or deletion of agents or goal-based and norm-based
the change of coalitions in requirements analysis. dependencies. They represent the case in which the network
Possible reasons behind these changes are due to oper- remains the same, involving the same agents and dependen-
ations of addition and removal of the components of our cies, but the composition of the coalition changes, including
model such as agents, dependencies among agents, norma- new dependencies or excluding the old ones. A simple and
tive dependencies concerning normative goals and powers. intuitive common sense example of the above presented
More precisely, how do we measure the evolution and the changes can be the next one. Consider a soccer team as
changes of a coalition over time in terms of: a coalition. It can change because new players come in, or
Changes of the agents and dependencies. We distinguish players retire. It can change, because agents acquire new
two kinds of uses for dependence networks: global use in abilities or loose abilities, e.g., they loose their form, they
break a leg, and so on, or get new goals, e.g., they want
to play in the national team. Concerning norms, there can
be the obligation set by the trainer for a player to play in
the left wing position. Concerning internal dynamics, there
may be a malicious behavior of a player, e.g., he gets too
many red cards since he is too aggressive and he is no longer
allowed to play. In the paper, we explain the changes using
a grid-based running example.
From the multiagent systems field, we use the normative Figure 1. Grid network:C={a, b, c};C={a, b, c, d}.
multiagent paradigm while from social network theory we
take the idea of defining graph theoretic measures. Concern-
ing measures, we define measures associated to the number
of agents and the number of goal-based dependencies present The second kind of change concerns goal-based depen-
in each time instant, counting the number of norm-based dencies. Node b fulfilled the goal of node c to save the
dependencies in each time instant and counting the changes file satellite.mpeg. This dependency does not hold anymore
in the dependencies composing coalitions. Our measures are and it is deleted, as shown in Figure 1.b. This deletion of
unified in an average measure returning coalitions’ stability dependencies changes the structure of the local coalition
depending on the differences between values associated to because of now the reciprocity involves also node d inside
consecutive time instants. the system. The deletion, as the addition, of a goal-based
In this paper, we do not give a formal ontology but dependency may cause a change in the coalitions composed
we define indications of the possible changes of coalitions. by these dependencies.
Moreover, we do not perform any simulation as in Carley’s The third kind of change is related with security. A node
dynamic networks analysis [3]. This paper is organized as has a number of private information, e.g., a unique access
follows. Section 2 presents a grid-based scenario. Section to its pc. If another node has the necessity to access to it,
3 and 4 present the key concepts of our metamodel and it has to ask the first node the permission, e.g., a login and
the three coalitions’ changes in detail. Related work and a password, as in the norm-based dependency among nodes
conclusions end the paper. a and c. Obligations, instead, are due to particular services
provided by the nodes. The obligation is represented as a
2. Changing coalitions in a GRID scenario dependency, as in the case of the norm-based dependency
among nodes d and b, and it is removed if the obligation is no
We use the following example of a coalition in a grid envi- more active in the system. Figure 2.a shows the introduction
ronment. Inside a virtual organization (VO), local coalitions of a norm-based dependency representing the obligation for
may be formed in order to cooperate to achieve shared goals node b to give the access to file finalres.txt to node a.
such as, i.e., computations and storage of satellites’ data.
We depict a section of the VO composed by five nodes,
as in Figure 1.a, following the legend of Figure 3. The
VO is composed by four nodes connected to each other
by dependencies based both on goals and on norms and
nodes a, b and c form a local coalition. Considering goal-
based dependencies, node b depends on node a to save the
file satellite.jpg, node c depends on node b to save the file
satellite.mpeg and node c depends on node d to run the file
results.mat, since they are not able to perform their goals
alone. Considering norm-based dependencies, instead, node
a depends on node c to have the permission to open the file Figure 2. Grid network: C={a, b, c, d};C={a, b, c}.
dataJune.mat while node c is obliged to give to node b the
results of the running of file mining.mat.
The first kind of change of coalitions in the grid scenario The fourth kind of change, internal changes of coali-
follows directly from the grid metaphor. Computers can tions, represents changes in the composition of the coalition
be connected to the grid like electrical machines can be because of internal reasons. In Grid networks, malicious
connected to the power net. So the computers connected behaviors can be recognized, e.g., in case of attacks or for
to the grid changes frequently, e.g., node e. If they do so, not properly following the protocol, and malicious nodes can
then also the coalition changes. How frequently they change be excluded from further interactions with the other nodes,
is our first measure. as shown in Figure 2.b.
3. The model to their goals {g1 , g2 } or {g3 }. A dependence network is
defined as follows:
3.1. The model definition Definition 3 (Dependence Networks (DN)): A
dependence network is a tuple hA, G, dep, ≥i where:
Our modeling approach aims to provide a design method- • A is a set of agents and G is a set of goals;
G
ology both for multiagent systems and social systems, based A
• dep : 2 × 2
A
→ 22 is a function that relates with
on the normative multiagent paradigm. We present our each pair of sets of agents all the sets of goals on which
model as a tuple composed by the concepts of agents, the first depends on the second.
goals, norms and time. This notions are represented in our G G
• ≥: A → 2 × 2 is for each agent a total pre-order on
dependency modeling as nodes or dependency relations be- goals which occur in his dependencies: G1 ≥ (a)G2
tween these entities. For more details about the dependency implies that ∃B, C ⊆ A such that a ∈ B and G1 , G2 ∈
modeling, see Villata [10]. Our model can be represented as depend(B, C).
follows:
The dependency modeling represents our modeling ac-
Definition 1: hA, G, N, T, D, D ⊆ A × A × G, T →
tivity consisting in the identification of the dependencies
2A , T → 2D , N → 2D , C ⊆ 2D , N ⊆ Ci consists in a
among the agents. Our dependency modeling is represented
set of agents A, a set of goals G, a set of norms N , a
as a directed labeled graph whose nodes are instances of the
set of time instants T and a set of dependencies D. Every
concepts of the metamodel, e.g., agents, goals, and whose
time instant is related to the set of agents and to the set of
arcs are instances of the notions representing relationships
dependencies D present in the system in that instant. Norms
between them such as goal-based dependency and norm-
are represented as a subset of dependencies. A coalition is
based dependency. A graphical representation of the model
represented as a set of dependencies and a subset of the
obtained following this modeling activity is depicted in the
dependencies composing a coalition can be represented by
legend of Figure 3. Open and closed arrows are used to
norms.
provide an immediate graphical representation of coalitions.
In this model, a coalition can be represented by a set
of dependencies, represented by C(a, B, G) where a is an
agent, B is a set of agents and G is a set of goals. Intuitively, 4. Coalitions’ Dynamics
the coalition agrees that for each C(a, B, G) part of the
coalition, the set of agents B will see to the goal G of agent In this section, we present a definition of coalition based
a. Otherwise, the set of agents B may be removed from the on the structure of dependence network and how to use
coalition or be sanctioned. these different kinds of dependencies to model and measure
In a multiagent system, since an agent is put into a system coalitions’ dynamics. In our model, a coalition is defined as
that involves also other agents, he can be supported by the follows:
others to achieve his own goals if he is not able to do them Definition 4 (Coalition): Let A be a set of agents and G
alone. This leads to the concept of power representing the be a set of goals. A coalition function is a partial function
capability of a group of agents (possibly composed only C : A × 2A × 2G such that {a | C(a, B, G)} = {b | b ∈
by one agent) to achieve some goals (theirs or of other B, C(a, B, G)}, the set of agents profiting from the coalition
agents) performing some actions without the possibility to is the set of agents contributing to it. Let hA, G, dep, ≥i be
be obstructed. The power of a group of agents is defined as a social dependence network, a coalition function C is a
follows: coalition if ∃a ∈ A, B ⊆ A, G′ ⊆ G such that C(a, B, G′ )
Definition 2 (Agents’ power): hA, G, power : 2A → implies G′ ∈ dep(a, B).
2G As introduced before, we can model and measure coali-
2 i where A is a set of agents, G is a set of goals. The
function power relates with each set S ⊆ A of agents the tions’ dynamics over time in terms of: changes of the agents
sets of goals G1S , . . . , Gm and goal-based dependencies, changes of the dependencies
S they can achieve.
Definitions 1 and 2 have the aim to explain how social related to norms and changes inside the coalition itself.
dependence networks can be seen as multiagent systems.
The notion of power is relevant for our methodology since 4.1. Agent and dependencies’ changes
it represents the social basis for the development of our
model based on the methodology of dependence networks The first kind of change is due to agents entering or
as developed by Conte and Sichman [9]. In this model, an leaving the multiagent system we model or to the depen-
agent is described by a set of prioritized goals, and there is dencies added or deleted depending on the fulfillment of
a global dependence relation that explicates how an agent the related goal or the presence of the power to fulfill this
depends on other agents for fulfilling its goals. For example, goal. In our model, we distinguish two different kinds of
dep({a, b}, {c, d}) = {{g1, g2 }, {g3 }} expresses that the set goals, achievement goals and maintenance goals. In con-
of agents {a, b} depends on the set of agents {c, d} to see tracts goals are typically achievement ones while, in game
theoretical approaches, coalitions are typically concerned 4.2. Norms’ changes
with maintenance goals. In this paper, we assume that goals
are maintenance goals rather than achievement ones, which
give us automatically a longer term and a more dynamic The second kind of change is due to norms and, in par-
perspective to define the evolution of coalitions and thus ticular, to obligations. An obligation is a requirement which
their stability. Moreover, our model aims to distinguish must be fulfilled to take some course of action, whether
and represent not only short term situations such as, for legal or moral. Normative reasoning is strictly related to
example, a virtual meeting on Second Life but also long norms’ changes and the definition of a representation and a
term situations as, for example, the work of a particular measure for them allows to do it. The norm sets a particular
department or office or, in the Grid scenario, the work of a kind of dependency among two agents. This dependency can
virtual organization for e-Research. be deleted if the obligation is fulfilled or a new obligation
can be inserted into the system to regulate its behaviour.
We can define two measures associated to the number of
In our model, we distinguish, represent and measure both
agents and the number of goal-based dependencies present in
short term contracts, e.g., a transaction on e-Bay such as an
each time instant. The first measure calculates the ratio be-
agreement carried out between separate entities involving the
tween the number of agents added and removed in a particu-
exchange of items of value as goods and money, and long
lar time instant depending and the number of agents present
term contracts, e.g., the marriage contract which hopefully
at the previous time instant. The second measure calculates
lasts forever.
the ratio between the number of goal-based dependencies
added and deleted in a particular time instant depending We can define a measure associated to the number of
and the number of goal-based dependencies present at the norm-based dependencies present in each time instant. This
previous time instant. The measures are defined as follows: measure calculates the ratio between the number of norm-
Definition 5 (Agents and Dependencies Measures): Let i based dependencies added and deleted to each time instant
be a time frame, NiAgent is given by the number of agents depending and the total number of norm-based dependencies
entering the system A+ − present in that time instant. The measure is defined as
i and leaving the system Ai , depend-
ing on the total number of agents Ai−1 present at time frame follows:
i − 1: Definition 6 (Norms Measure): Let i be a time frame,
NiN orm is given by the number of norm-based dependencies
X A+ X A−
NiAgent
= i
+ i added to the network Oi+ and deleted form the network Oi− ,
Ai−1 Ai−1 depending on the total number of norm-based dependencies
Oi−1 present at time frame i − 1:
Let i be a time frame, NiDep is given by the number
of goal-based dependencies added to the network Di+ and X O+ X O−
deleted form the network Di− , depending on the total NiN orm = i
+ i
Oi−1 Oi−1
number of goal-based dependencies Di−1 present at time
frame i − 1:
Example 2: In Figure 4, we model three time instants. In
X D+ X D− the first time instant t1 , we have a coalition formed by all the
NiDep = i
+ i
Di−1 Di−1 four agents, three goal-based dependencies and two norm-
based dependencies. From time instant t1 to time instant
Example 1: In Figure 3, we present the case of six time t2 , the norm-based dependency involving agents d and b is
frames visualizing the evolution of a coalition. In the first removed due to the removal of the normative goal or the
time frame, we have five agents and a coalition involving removal of the associated power. From time instant t2 to
agents a, b, c, as shown by the dependencies composing it. time instant t3 , a new norm-based dependency is set due
There are also two norm-based dependencies and three goal- to the insertion of a new normative goal or the associated
based dependencies. The passage from the first instant t1 to normative power.
the second one shows the deletion of agent e. From instant
t2 to instant t3 , we observe the deletion of the goal-based
dependency connecting agents c and b. Also the coalition
changes and it is formed by all the four agents. From instant
t3 to instant t4 , the situation changes back to the original
configuration but the coalition is fixed. From instant t4 to
instant t5 , agent d disappears, a norm-based dependency is
deleted and the coalition changes its actors, involving now
a, b and c. From instant t5 to instant t6 , the situation cames Figure 4. Norms’ change.
back to the situation of instant t4 .
Figure 3. Agents and dependencies’ change.
4.3. Coalitions’ changes average number of changes. We can define this measure as
follows:
The third kind of change is related to changes inside the Definition 8 (Changes Measures): Let i be a time frame
coalition itself, e.g., an agent is excluded from a coalition of a sequence of social dependence networks, the measure of
because of a malicious behaviour. This third kind of change the changes’ average is given by the fraction of the sum of
is the only one related to the coalition itself and it has the single measures and the number of available measures:
to represent and measure the changes in the composition
of each coalition of the system. We define a measure NiAgent + NiDep + NiN orm + NiCoal
which calculates the ratio between the number of the goal- measures
based and norm-based dependencies composing the coalition Measures of example 1 vary as shown in Table 1.
in each time instant and the dependencies composing the t1 t2 t3 t4 t5 t6
coalition in the previous time instant, as follows: NiAgent 0/5 1/5 0/4 0/4 1/4 1/3
Definition 7 (Coalitions Measure): Let i be a time frame, NiDep 0/3 0/3 1/3 1/2 1/3 1/2
NiCoal is given by the number of norm-based and goal-based NiNorm 0/2 0/2 0/2 0/2 1/2 1/1
dependencies of a coalition added to the network (Di+ + NiCoal 0/3 0/3 3/3 0/4 3/4 3/3
Changes 0 0, 05 0, 33 0, 12 0, 55 0, 85
Oi+ ) ∈ Ci and deleted from the network (Di− + Oi− ) ∈ Ci
depending on the total number of norm-based and goal-based Table 1. Measures of Figure 3
dependencies composing the coalition (Di−1 + Oi−1 ) ∈
Ci−1 at time frame i − 1:
Thanks to the changes measure, we underline that the
X (Di+ + Oi+ )Ci
X
(Di− + Oi− )Ci
two time frames with the main changes in comparison
NiCoal = +
(Di−1 + Oi−1 )Ci−1 (Di−1 + Oi−1 )Ci−1 with their previous time frame are t3 and t5 , as can be
supposed observing the relative figure. It can be noted that
Example 3: Consider the coalition depicted in time in- in our measures the deletion of a component increases the
stant t1 of Figure 5. The coalition is composed by agents difference of the changes measure associated to two time
a, b and c. The passage from time instant t1 to time instant frames in a row while the addition of these components
t2 sees the addition inside the coalition of agent d due to causes a minor change. This behaviour is due to the relation
the reciprocity-based principle of coalition formation. From of our measure with the game theoretical approaches for
time instant t2 to time instant t3 , agent d is excluded from defining stability: the stability is maintained in order to avoid
the coalition, without any change in the number or type of the breaking off of the agents from the grand coalition and
the dependencies composing the coalition itself. This can form their own group.
depend, as said, on a malicious behaviour of the excluded We choose the simplest possible measures that capture the
agent. stability of the networks, because they represent all possible
changes can be performed in the composition of coalitions
and of the networks. When the average of the measures for a
sequence of dependence networks presents a great difference
in the values of two connected time instants, it underlines a
lack of stability while when the average presents a small or
inexistent difference between two connected time instants,
the stability of the coalition and of the network in general is
Figure 5. Coalitions’ change. maintained. Moreover, the measures now only give a global
indication of the stability of agents, dependencies, norms and
The above measures are defined for one time moment coalitions. We could also measure whether changes in agents
only. We can unify these measures for a sequence of and dependencies coincides with changes in the coalition
dependence networks associating to each time instant the thanks to our four measures.
5. Related Work coalitions’ dynamics in terms of changing dependencies,
agents and coalitions, distinguishing also among goal-based
In a multiagent perspective, a coalition can be viewed dependencies and norm-based ones. Using dependence net-
under two different representational frameworks. The first works as methodology to model a system advantages us from
one regards cooperative game theory. Cooperative game different points of view. First, they are abstract, thus they
theory studies those games in which players are able to make can be used for conceptual modeling, simulation, design and
binding agreements with the aim to achieve a collective ben- formal analysis. Second, they are used in high level design
efit. This approach is strictly related to the field of economics languages, like TROPOS [2], thus they can be used also in
and various approaches of this kind have been presented in software implementation.
literature as, for example, the work of Shehory and Kraus Concerning future work, we are working on a definition
[6]. The second perspective is based on the theory of the so- of coalitions’ stability in our model, based on the presented
cial power and dependence pioneered by Castelfranchi [4] as measures, because of a lack of a definition of this notion
starting point and then developed in the context of coalition in the field of social network theory. The notion of stability
formation by Sichman [8] and Sauro [5]. This involves the in our model can be identified intuitively in the absence
development of a social reasoning mechanism that analyzes of coalitions’ changes we described but it is necessary to
the possibility to profit from mutual-dependencies, e.g., two provide a formal definition of this notion and to associate it
agents depend on each other for the satisfaction of a shared a measure able to represent it. Moreover, we start to simulate
goal, or reciprocal-dependencies, e.g., two agents depend on the use of our model and its associated measures in order to
each other for the satisfaction of two different goals. Both provide quantitative results based on our approach, similarly
these two approaches present the following problems: they to social network theory approaches.
do not provide a modeling technique to represent coalitions’
dynamics and to distinguish them. References
6. Conclusions [1] T. Ågotnes, W. van der Hoek, and M. Wooldridge. Temporal
qualitative coalitional games. In AAMAS, pages 177–184,
We present a model to represent, at each time instant, the 2006.
state of the system in terms of agents, goals, norms and [2] P. Bresciani, A. Perini, P. Giorgini, F. Giunchiglia, and J. My-
the dependencies relating all these concepts. This model lopoulos. Tropos: An agent-oriented software development
allows the distinction and measure of the possible coali- methodology. Autonomous Agents and Multi-Agent Systems
tions’ dynamics. In particular, we distinguish among three Journal, 8:203–236, 2004.
different kinds of coalitions’ changes: changes based on
[3] K. M. Carley. Dynamic network analysis. In Dynamic Social
addition or deletion of agents or goal-based dependencies, Network Modeling and Analysis: Workshop Summary and
changes based on the addition or deletion of norm-based Papers, pages 133–145, 2003.
dependencies and changes on the internal structure of the
coalition itself. It can be observed that with a more detailed [4] C. Castelfranchi. The micro-macro constitution of power.
model we could make more detailed and precise distinctions Protosociology, 18:208–269, 2003.
between the four kinds of changes. However, often we [5] L. Sauro. Formalizing admissibility criteria in coalition
only have the given information, for example in systems’ formation among goal directed agents. PhD thesis, University
design, and we already would like to do this kind of of Turin, 2005.
analysis on these models. This is precisely where graph-
[6] O. Shehory and S. Kraus. Methods for task allocation via
theoretical social network techniques are useful. We combine agent coalition formation. Artificial Intelligence, 101:165–
these techniques with the normative multiagent paradigm 200, 1998.
introducing in the networks norm-based dependencies. The
strength of this combination consists in building a modeling [7] Y. Shoham and K. Leyton-Brown. Multiagent Systems: Al-
technique able to represent in an intuitive way not only gorithmic, Game-Theoretic, and Logical Foundations. Cam-
bridge University Press, 2008.
the inter-relationships among the actors of the system but
also external constraints such as norms and, particularly, [8] J. S. Sichman. Depint: Dependence-based coalition formation
obligations, e.g., in our Grid scenario. The main difficulty in an open multi-agent scenario. Artificial Societies and Social
of this approach consists in the creation of a common model Simulation, 1(2), 1998.
without simplifying too much the two original frameworks. [9] J. S. Sichman and R. Conte. Multi-agent dependence by
Moreover, we introduce four measures aiming to measure dependence graphs. In AAMAS’02, pages 483–490, 2002.
these changes inside the networks to each time instant and
an average measure to compute the stability of a sequence [10] S. Villata. A normative multiagent approach to requirements
of dependence networks. Our model allows to measure engineering. The logic journal of the IGPL, 2009.