We introduce a new formal approach to social networks in order to distinguish four ways in which coalitions change. First, the agents in the network change. Second, dependencies among the agents change, for example due to addition or removal of powers and goals of the agents. Third, norms can introduce normative dependencies for obligations and prohibitions. Fourth, coalitions can change due to internal processes. We propose a number of stability measures to identify each one of the four proposed sources of coalitions' dynamics and the consequences they induce on the stability of coalitions.
Coalitions play a central role in social reasoning, and
thus various theories have been used and developed in
multiagent systems. For example, coalitional game theory has
been adopted from economics and extended for multiagent
systems [
Possible reasons behind these changes are due to
operations of addition and removal of the components of our
model such as agents, dependencies among agents,
normative dependencies concerning normative goals and powers.
More precisely, how do we measure the evolution and the
changes of a coalition over time in terms of:
Changes of the agents and dependencies. We distinguish
two kinds of uses for dependence networks: global use in
software engineering where the designer models all
stakeholders [
Changes of the dependencies related to norms.Norms
are used for the dynamics of dependence networks, which
explained why they have not been considered thus far in
the static dependence networks [
Internal dynamics. Changes of the coalition itself in terms of goal-based and norm-based dependencies composing the coalition, e.g., an agent is excluded from a coalition because of a malicious behaviour.
We call the last kind of change internal dynamics to distinguish it from the other dynamics related to the addition or deletion of agents or goal-based and norm-based dependencies. They represent the case in which the network remains the same, involving the same agents and dependencies, but the composition of the coalition changes, including new dependencies or excluding the old ones. A simple and intuitive common sense example of the above presented changes can be the next one. Consider a soccer team as a coalition. It can change because new players come in, or players retire. It can change, because agents acquire new 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 multiagent paradigm while from social network theory we take the idea of defining graph theoretic measures. Concerning measures, we define measures associated to the number of agents and the number of goal-based dependencies present in each time instant, counting the number of norm-based dependencies in each time instant and counting the changes in the dependencies composing coalitions. Our measures are unified in an average measure returning coalitions’ stability depending on the differences between values associated to consecutive time instants.
In this paper, we do not give a formal ontology but
we define indications of the possible changes of coalitions.
Moreover, we do not perform any simulation as in Carley’s
dynamic networks analysis [
We use the following example of a coalition in a grid environment. Inside a virtual organization (VO), local coalitions may be formed in order to cooperate to achieve shared goals 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 goalbased 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 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 follows directly from the grid metaphor. Computers can be connected to the grid like electrical machines can be connected to the power net. So the computers connected to the grid changes frequently, e.g., node e. If they do so, then also the coalition changes. How frequently they change is our first measure.
The second kind of change concerns goal-based dependencies. Node b fulfilled the goal of node c to save the file satellite.mpeg. This dependency does not hold anymore and it is deleted, as shown in Figure 1.b. This deletion of dependencies changes the structure of the local coalition because of now the reciprocity involves also node d inside the system. The deletion, as the addition, of a goal-based dependency may cause a change in the coalitions composed by these dependencies.
The third kind of change is related with security. A node has a number of private information, e.g., a unique access to its pc. If another node has the necessity to access to it, it has to ask the first node the permission, e.g., a login and a password, as in the norm-based dependency among nodes a and c. Obligations, instead, are due to particular services provided by the nodes. The obligation is represented as a dependency, as in the case of the norm-based dependency among nodes d and b, and it is removed if the obligation is no more active in the system. Figure 2.a shows the introduction of a norm-based dependency representing the obligation for node b to give the access to file finalres.txt to node a.
The fourth kind of change, internal changes of coalitions, represents changes in the composition of the coalition because of internal reasons. In Grid networks, malicious behaviors can be recognized, e.g., in case of attacks or for not properly following the protocol, and malicious nodes can be excluded from further interactions with the other nodes, as shown in Figure 2.b.
Our modeling approach aims to provide a design
methodology both for multiagent systems and social systems, based
on the normative multiagent paradigm. We present our
model as a tuple composed by the concepts of agents,
goals, norms and time. This notions are represented in our
dependency modeling as nodes or dependency relations
between these entities. For more details about the dependency
modeling, see Villata [
Definition 1: hA, G, N, T , D, D ⊆ A × A × G, T → 2A, T → 2D, N → 2D, C ⊆ 2D, N ⊆ Ci consists in a set of agents A, a set of goals G, a set of norms N , a set of time instants T and a set of dependencies D. Every time instant is related to the set of agents and to the set of dependencies D present in the system in that instant. Norms are represented as a subset of dependencies. A coalition is represented as a set of dependencies and a subset of the dependencies composing a coalition can be represented by norms.
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, 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 a. Otherwise, the set of agents B may be removed from the coalition or be sanctioned.
In a multiagent system, since an agent is put into a system that involves also other agents, he can be supported by the others to achieve his own goals if he is not able to do them alone. This leads to the concept of power representing the capability of a group of agents (possibly composed only by one agent) to achieve some goals (theirs or of other agents) performing some actions without the possibility to be obstructed. The power of a group of agents is defined as follows:
GDefinition 2 (Agents’ power): hA, G, power : 2A → 22 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 sets of goals G1S , . . . , GSm they can achieve.
Definitions 1 and 2 have the aim to explain how social
dependence networks can be seen as multiagent systems.
The notion of power is relevant for our methodology since
it represents the social basis for the development of our
model based on the methodology of dependence networks
as developed by Conte and Sichman [
Definition 3 (Dependence Networks (DN)): A dependence network is a tuple hA, G, dep, ≥i where: • A is a set of agents and G is a set of goals; • dep : 2A × 2A → 22G is a function that relates with each pair of sets of agents all the sets of goals on which the first depends on the second. • ≥: A → 2G × 2G is for each agent a total pre-order on goals which occur in his dependencies: G1 ≥ (a)G2 implies that ∃B, C ⊆ A such that a ∈ B and G1, G2 ∈ depend(B, C).
The dependency modeling represents our modeling activity consisting in the identification of the dependencies among the agents. Our dependency modeling is represented as a directed labeled graph whose nodes are instances of the concepts of the metamodel, e.g., agents, goals, and whose arcs are instances of the notions representing relationships between them such as goal-based dependency and normbased dependency. A graphical representation of the model obtained following this modeling activity is depicted in the legend of Figure 3. Open and closed arrows are used to provide an immediate graphical representation of coalitions.
In this section, we present a definition of coalition based on the structure of dependence network and how to use these different kinds of dependencies to model and measure coalitions’ dynamics. In our model, a coalition is defined as follows:
Definition 4 (Coalition): Let A be a set of agents and G be a set of goals. A coalition function is a partial function C : A × 2A × 2G such that {a | C(a, B, G)} = {b | b ∈ B, C(a, B, G)}, the set of agents profiting from the coalition is the set of agents contributing to it. Let hA, G, dep, ≥i be a social dependence network, a coalition function C is a coalition if ∃a ∈ A, B ⊆ A, G′ ⊆ G such that C(a, B, G′) implies G′ ∈ dep(a, B).
As introduced before, we can model and measure coalitions’ dynamics over time in terms of: changes of the agents and goal-based dependencies, changes of the dependencies related to norms and changes inside the coalition itself.
The first kind of change is due to agents entering or leaving the multiagent system we model or to the dependencies added or deleted depending on the fulfillment of the related goal or the presence of the power to fulfill this goal. In our model, we distinguish two different kinds of goals, achievement goals and maintenance goals. In contracts goals are typically achievement ones while, in game theoretical approaches, coalitions are typically concerned 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 perspective to define the evolution of coalitions and thus their stability. Moreover, our model aims to distinguish and represent not only short term situations such as, for example, a virtual meeting on Second Life but also long term situations as, for example, the work of a particular department or office or, in the Grid scenario, the work of a virtual organization for e-Research.
We can define two measures associated to the number of agents and the number of goal-based dependencies present in each time instant. The first measure calculates the ratio between the number of agents added and removed in a particular time instant depending and the number of agents present at the previous time instant. The second measure calculates the ratio between the number of goal-based dependencies added and deleted in a particular time instant depending and the number of goal-based dependencies present at the previous time instant. The measures are defined as follows:
Definition 5 (Agents and Dependencies Measures): Let i be a time frame, N Agent is given by the number of agents entering the system iAi+ and leaving the system Ai , depend− ing on the total number of agents Ai−1 present at time frame i − 1:
N Agent = X i
A+
i Ai−1 + X
Ai− Ai−1 Let i be a time frame, N Dep is given by the number i of goal-based dependencies added to the network Di+ and deleted form the network Di−, depending on the total number of goal-based dependencies Di−1 present at time frame i − 1:
N Dep = X i
D+
i Di−1 + X
Di− Di−1
Example 1: In Figure 3, we present the case of six time frames visualizing the evolution of a coalition. In the first time frame, we have five agents and a coalition involving agents a, b, c, as shown by the dependencies composing it. There are also two norm-based dependencies and three goalbased dependencies. The passage from the first instant t1 to 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 back to the situation of instant t4.
The second kind of change is due to norms and, in particular, to obligations. An obligation is a requirement which must be fulfilled to take some course of action, whether legal or moral. Normative reasoning is strictly related to norms’ changes and the definition of a representation and a measure for them allows to do it. The norm sets a particular kind of dependency among two agents. This dependency can be deleted if the obligation is fulfilled or a new obligation can be inserted into the system to regulate its behaviour. In our model, we distinguish, represent and measure both short term contracts, e.g., a transaction on e-Bay such as an agreement carried out between separate entities involving the exchange of items of value as goods and money, and long term contracts, e.g., the marriage contract which hopefully lasts forever.
We can define a measure associated to the number of norm-based dependencies present in each time instant. This measure calculates the ratio between the number of normbased dependencies added and deleted to each time instant depending and the total number of norm-based dependencies present in that time instant. The measure is defined as follows:
Definition 6 (Norms Measure): Let i be a time frame, N Norm is given by the number of norm-based dependencies i − added to the network Oi+ and deleted form the network Oi , depending on the total number of norm-based dependencies Oi−1 present at time frame i − 1:
N Norm = X i
O+
i Oi−1 + X
Oi− Oi−1
Example 2: In Figure 4, we model three time instants. In the first time instant t1, we have a coalition formed by all the four agents, three goal-based dependencies and two normbased dependencies. From time instant t1 to time instant t2, the norm-based dependency involving agents d and b is removed due to the removal of the normative goal or the removal of the associated power. From time instant t2 to time instant t3, a new norm-based dependency is set due to the insertion of a new normative goal or the associated normative power.
The third kind of change is related to changes inside the coalition itself, e.g., an agent is excluded from a coalition because of a malicious behaviour. This third kind of change is the only one related to the coalition itself and it has to represent and measure the changes in the composition of each coalition of the system. We define a measure which calculates the ratio between the number of the goalbased and norm-based dependencies composing the coalition in each time instant and the dependencies composing the coalition in the previous time instant, as follows:
Definition 7 (Coalitions Measure): Let i be a time frame, N Coal is given by the number of norm-based and goal-based i dependencies of a coalition added to the network (Di+ + Oi+) ∈ Ci and deleted from the network (Di− + Oi−) ∈ Ci depending on the total number of norm-based and goal-based dependencies composing the coalition (Di−1 + Oi−1) ∈ Ci−1 at time frame i − 1: NiCoal = X
(Di+ + Oi+)Ci (Di−1 + Oi−1)Ci−1 +X
(Di− + Oi−)Ci (Di−1 + Oi−1)Ci−1
Example 3: Consider the coalition depicted in time instant t1 of Figure 5. The coalition is composed by agents a, b and c. The passage from time instant t1 to time instant t2 sees the addition inside the coalition of agent d due to the reciprocity-based principle of coalition formation. From time instant t2 to time instant t3, agent d is excluded from the coalition, without any change in the number or type of the dependencies composing the coalition itself. This can depend, as said, on a malicious behaviour of the excluded agent.
The above measures are defined for one time moment only. We can unify these measures for a sequence of dependence networks associating to each time instant the average number of changes. We can define this measure as follows:
Definition 8 (Changes Measures): Let i be a time frame of a sequence of social dependence networks, the measure of the changes’ average is given by the fraction of the sum of the single measures and the number of available measures: N Agent + N Dep + N Norm + N Coal i i i i
measures Measures of example 1 vary as shown in Table 1.
NAgent i NDep NNi orm i NCoal
i Changes
Thanks to the changes measure, we underline that the two time frames with the main changes in comparison with their previous time frame are t3 and t5, as can be supposed observing the relative figure. It can be noted that in our measures the deletion of a component increases the difference of the changes measure associated to two time frames in a row while the addition of these components causes a minor change. This behaviour is due to the relation of our measure with the game theoretical approaches for defining stability: the stability is maintained in order to avoid the breaking off of the agents from the grand coalition and form their own group.
We choose the simplest possible measures that capture the 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 maintained. Moreover, the measures now only give a global indication of the stability of agents, dependencies, norms and coalitions. We could also measure whether changes in agents and dependencies coincides with changes in the coalition thanks to our four measures.
In a multiagent perspective, a coalition can be viewed
under two different representational frameworks. The first
one regards cooperative game theory. Cooperative game
theory studies those games in which players are able to make
binding agreements with the aim to achieve a collective
benefit. This approach is strictly related to the field of economics
and various approaches of this kind have been presented in
literature as, for example, the work of Shehory and Kraus
[
We present a model to represent, at each time instant, the state of the system in terms of agents, goals, norms and the dependencies relating all these concepts. This model allows the distinction and measure of the possible coalitions’ dynamics. In particular, we distinguish among three different kinds of coalitions’ changes: changes based on addition or deletion of agents or goal-based dependencies, changes based on the addition or deletion of norm-based dependencies and changes on the internal structure of the coalition itself. It can be observed that with a more detailed model we could make more detailed and precise distinctions between the four kinds of changes. However, often we only have the given information, for example in systems’ design, and we already would like to do this kind of analysis on these models. This is precisely where graphtheoretical social network techniques are useful. We combine these techniques with the normative multiagent paradigm introducing in the networks norm-based dependencies. The strength of this combination consists in building a modeling technique able to represent in an intuitive way not only the inter-relationships among the actors of the system but also external constraints such as norms and, particularly, obligations, e.g., in our Grid scenario. The main difficulty of this approach consists in the creation of a common model without simplifying too much the two original frameworks.
Moreover, we introduce four measures aiming to measure
these changes inside the networks to each time instant and
an average measure to compute the stability of a sequence
of dependence networks. Our model allows to measure
coalitions’ dynamics in terms of changing dependencies,
agents and coalitions, distinguishing also among goal-based
dependencies and norm-based ones. Using dependence
networks as methodology to model a system advantages us from
different points of view. First, they are abstract, thus they
can be used for conceptual modeling, simulation, design and
formal analysis. Second, they are used in high level design
languages, like TROPOS [
Concerning future work, we are working on a definition of coalitions’ stability in our model, based on the presented measures, because of a lack of a definition of this notion in the field of social network theory. The notion of stability in our model can be identified intuitively in the absence of coalitions’ changes we described but it is necessary to provide a formal definition of this notion and to associate it a measure able to represent it. Moreover, we start to simulate the use of our model and its associated measures in order to provide quantitative results based on our approach, similarly to social network theory approaches.