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.