Emergence of Multiagent Coalition by Leveraging Complex Network Dynamics

PI: Anita Raja

RA: Mohammad Rashedul Hasan

Collaborator:  Professor Sherief Abdallah, British University, Dubai

Sponsor: NSF



There has been a great deal of interest in the multiagent systems (MAS) community about the emergence and maintenance of coalitions among agents. A coalition is defined as a group of agents who have decided to cooperate in order to perform a common task. However, in the interaction of selfish agents, where defection actions bring more short-term benefit, emergence of sustained coalitions becomes challenging. For example, in solving distributed combinatorial problems such as in resource and task allocation and MAS planning and scheduling every agent tries to maximize its own good without concern for the global good. Traditionally this problem has been modeled as a Prisoner's Dilemma (PD) game within
 a game-theoretic framework. The PD game, where selfish and rational agents try to maximize their utility by interacting with each other, offers a powerful metaphor for understanding how cooperation may emerge in the face of short-term selfish behavior. When it is played iteratively among two agents, the ‘tit-for-tat’ strategy has been shown to maximize cooperation. Although defection is the only evolutionary stable strategy in iterated PD, the likelihood of cooperation is remarkably increased if the agent interaction is constrained by the underlying network topology. 

The emergence of cooperation has initially been shown over a simple grid topology and later for complex networks such as scale-free (SF) and small-world networks. However, in these approaches agents do not use the network dynamics to enhance the emergence phenomenon. These works start by assuming a pre-established static complex network platform and then employ agents on the nodes of the network for mutual interactions. In other words, agents do not have the capability to form the network. These approaches use a given structure of the complex network with fixed properties and do not explore the other possible network configurations by varying the topological features. Therefore, the results that they generate are specific to the respective network topologies. In addition to this, they do not explore how the topological insights could reinforce agent dynamics to control the collective phenomena of cooperation. Therefore, while these help us to understand which network configurations favor cooperative behavior, agents do not seem to leverage the structural properties of the network. Moreover these works do not intend to achieve full cooperation.


In this project, we intend to design a decentralized approach where self-interested agents in a MAS operating on large SF networks exploit the complex network dynamics to facilitate the convergence into a single coalition. We use an iterated PD game to capture the agent interactions and provide a coalition emergence algorithm based on the intuitive idea that it would be beneficial for an agent to form a coalition with a wealthy (higher payoff) and influential (higher accumulated coupling strength) neighbor. We enable the agents to acquire the social status of its coalition by adding its neighbors coupling strength with its own (accumulation of the coupling strength) as it joins the neighbors’ coalition. We develop a computational model to study how our algorithm performs on various types of SF networks by varying the degree-heterogeneity and the clustering coefficient. We investigate how a dynamical process of the network, i.e., the coalition formation, is influenced by the structural properties of the network. Our goal is to determine the topological insights that, when embedded into agent partner selection strategy, results in a network always leading towards the emergence of a sustained single coalition where agents all over the network cooperate with each other. In other words, we emphasize on the significance of employing “network thinking” by the agents to control their dynamics and the dynamical processes of the network.
 

Our Approach:


Unlike many previous works that assume pre-established static networks, we determine the topological insights for the agents to choose their interaction partners to form a dynamically growing SF network and show that this network formation process significantly enhances the emergence phenomenon.

   

Figure 1: Dynamic network formation by the agents

 

 
 


 

Experimental Results:


Table 1: BA & Extended BA Model: Instances of sustainable multiple coalitions (#MC), the average Global Clustering Coefficient (GCC) and the average Degree-Heterogeneity (DH) over 500 realizations of the network for various values of p and A.


 

Figure 2: BA & Extended BA Model: Average no. of coalitions for various values of the initial attractiveness parameter (A) and the clustering probability p.


 
Figure 3: Degree-Distribution for various values of p and A (x-axis: node-degree & y-axis: node id from 0 to 999.

 

Observations:


•    Dynamic process (coalition formation) in networked MAS can be controlled by the dynamic topology.

•    The coalition emergence process is significantly enhanced when the topological insights, such as acquiring increased degree-heterogeneity and high clustering, are embedded into the agent partner selection strategy.
 

Current & Future Work:


•    Fast convention convergence in complex networks
•    Optimal convention in large convention space

 

 

References:


•    Mohammad Rashedul Hasan and Anita Raja, “Emergence of Cooperation using Commitments and Complex Network Dynamics”, To appear in the Proceedings of the 2013  IEEE/ WIC/ ACM International Conference on Intelligent Agent Technology (IAT-2013) (Acceptance Rate 30.7%)

•    Mohammad Rashedul Hasan and Anita Raja, “The Role of Complex Network Dynamics in the Emergence of Multiagent Coalition”, Two page abstract in the AAAI-13 Student Abstract and Poster Program (SA-13), Procceeding of AAAI2013, pp 1615-1616, July 17, 2013, Bellevue, Washington.

•    Mohammad Rashedul Hasan and Anita Raja, “Emergence of Multiagent Coalition by Leveraging Complex Network Dynamics”, Proceedings of AAMAS 2013 Fifth International Workshop on Emergent Intelligence on Networked Agents (WEIN'13), pp 9-23, May 6-10, 2013, St. Paul, Minnesota.

•    Mohammad Rashedul Hasan and Anita Raja, “Emergence of Privacy Conventions in Online Social Networks”,  Doctoral Consortium Abstract in the Proceedings of the Twelfth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2013), pp 1433-1434, May 6-10, 2013, St. Paul, Minnesota.

Acknowledgement: This material is based upon work supported by the National Science Foundation under Grant No. IIS: 1018067. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation (NSF).