Learning agent influence in MAS with complex social networks

摘要

In complex open multi-agent systems (MAS), where there is no centralised control and individuals have equal authority, ensuring cooperative and coordinated behaviour is challenging. Norms and conventions are useful means of supporting cooperation in an emergent decentralised manner, however it takes time for effective norms and conventions to emerge. Identifying influential individuals enables the targeted seeding of desirable norms and conventions, which can reduce the establishment time and increase efficacy. Existing research is limited with respect to considering (i) how to identify influential agents, (ii) the extent to which network location imbues influence on an agent, and (iii) the extent to which different network structures affect influence. In this paper, we propose a methodology for learning a model for predicting the network value of an agent, in terms of the extent to which it can influence the rest of the population. Applying our methodology, we show that exploiting knowledge of the network structure can significantly increase the ability of individuals to influence which convention emerges. We evaluate our methodology in the context of two agent-interaction models, namely, the language coordination domain used by Salazar et al. (AI Communications 23(4): 357–372, 2010) and a coordination game of the form used by Sen and Airiau (in: Proceedings of the 20th International Joint Conference on Artificial Intelligence, 2007) with heterogeneous agent learning mechanisms, and on a variety of synthetic and real-world networks. We further show that (i) the models resulting from our methodology are effective in predicting influential network locations, (ii) there are very few locations that can be classified as influential in typical networks, (iii) four single metrics are robustly indicative of influence across a range of network structures, and (iv) our methodology learns which single metric or combined measure is the best predictor of influence in a given network.