Abstract
In multi-agent systems it is often desirable for agents to adhere to standards of behaviour that minimise clashes and wasting of (limited) resources. In situations where it is not possible or desirable to dictate these standards globally or via centralised control, convention emergence offers a lightweight and rapid alternative. Placing fixed strategy agents within a population, whose interactions are constrained by an underlying network, has been shown to facilitate faster convention emergence with some degree of control. Placing these fixed strategy agents at topologically influential locations (such as high-degree nodes) increases their effectiveness. However, finding such influential locations often assumes that the whole network is visible or that it is feasible to inspect the whole network in a computationally practical time, a fact not guaranteed in many real-world scenarios. We present an algorithm, PO-Place, that finds influential nodes given a finite number of network observations. We show that PO-Place finds sets of nodes with similar reach and influence to the set of high-degree nodes and we then compare the performance of PO-Place to degree placement for convention emergence in several real-world topologies.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Borgs, C., Brautbar, M., Chayes, J., Khanna, S., Lucier, B.: The power of local information in social networks. In: Goldberg, P.W. (ed.) WINE 2012. LNCS, vol. 7695, pp. 406–419. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-35311-6_30
Brautbar, M., Kearns, M.J.: Local algorithms for finding interesting individuals in large networks. In: Proceedings of Innovation in Computer Science, pp. 188–199 (2010)
Chen, D.-B., Xiao, R., Zeng, A.: Predicting the evolution of spreading on complex networks. Sci. Rep. 4, 6108 (2014)
Chen, W., Wang, Y., Yang, S.: Efficient influence maximization in social networks. In: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 199–208 (2009)
Delgado, J.: Emergence of social conventions in complex networks. Artif. Intell. 141(1–2), 171–185 (2002)
Delgado, J., Pujol, J.M., Sangüesa, R.: Emergence of coordination in scale-free networks. Web Intell. Agent Syst. 1(2), 131–138 (2003)
Franks, H., Griffiths, N., Anand, S.S.: Learning agent influence in MAS with complex social networks. Auton. Agents Multi-Agent Syst. 28(5), 836–866 (2014)
Franks, H., Griffiths, N., Jhumka, A.: Manipulating convention emergence using influencer agents. Auton. Agents Multi-Agent Syst. 26(3), 315–353 (2013)
Griffiths, N., Anand, S.S.: The impact of social placement of non-learning agents on convention emergence. In: Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems, pp. 1367–1368 (2012)
Kandori, M.: Social norms and community enforcement. Rev. Econ. Stud. 59(1), 63–80 (1992)
Kittock, J.: Emergent conventions and the structure of multi-agent systems. In: Lectures in Complex Systems: Proceedings of the 1993 Complex Systems Summer School, pp. 507–521 (1995)
Leskovec, J., Krevl, A.: SNAP Datasets: Stanford large network dataset collection, June 2014. http://snap.stanford.edu/data
Marchant, J., Griffiths, N., Leeke, M.: Convention emergence and influence in dynamic topologies. In: Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, pp. 1785–1786 (2015)
Marchant, J., Griffiths, N., Leeke, M., Franks, H.: Destabilising conventions using temporary interventions. In: Ghose, A., Oren, N., Telang, P., Thangarajah, J. (eds.) COIN 2014. LNCS (LNAI), vol. 9372, pp. 148–163. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-25420-3_10
Mihara, S., Tsugawa, S., Ohsaki, H.: Influence maximization problem for unknown social networks. In: Proceedings of the IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, pp. 1539–1546 (2015)
Pei, S., Tang, S., Zheng, Z.: Detecting the influence of spreading in social networks with excitable sensor networks. PloS One 10(5), e0124848 (2015)
Salazar, N., Rodriguez-Aguilar, J.A., Arcos, J.L.: Robust coordination in large convention spaces. AI Commun. 23(4), 357–372 (2010)
Savarimuthu, B.T.R., Arulanandam, R., Purvis, M.: Aspects of active norm learning and the effect of lying on norm emergence in agent societies. In: Kinny, D., Hsu, J.Y., Governatori, G., Ghose, A.K. (eds.) PRIMA 2011. LNCS (LNAI), vol. 7047, pp. 36–50. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25044-6_6
Sen, S., Airiau, S.: Emergence of norms through social learning. In: Proceedings of the 20th International Joint Conference on Artifical Intelligence, pp. 1507–1512 (2007)
Villatoro, D., Sabater-Mir, J., Sen, S.: Social instruments for robust convention emergence. In: Proceedings of the 22nd International Joint Conference on Artificial Intelligence, pp. 420–425 (2011)
Villatoro, D., Sen, S., Sabater-Mir, J.: Topology and memory effect on convention emergence. In: Proceedings of the 2009 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology, pp. 233–240 (2009)
Walker, A., Wooldridge, M.: Understanding the emergence of conventions in multi-agent systems. In: International Conference on Multi-Agent Systems, pp. 384–389 (1995)
Wang, X., Su, Y., Zhao, C., Yi, D.: Effective identification of multiple influential spreaders by DegreePunishment. Phys. A: Stat. Mech. Appl. 461, 238–247 (2016)
Young, H.P.: The economics of convention. J. Econ. Perspect. 10(2), 105–122 (1996)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Marchant, J., Griffiths, N. (2017). Convention Emergence in Partially Observable Topologies. In: Sukthankar, G., Rodriguez-Aguilar, J. (eds) Autonomous Agents and Multiagent Systems. AAMAS 2017. Lecture Notes in Computer Science(), vol 10642. Springer, Cham. https://doi.org/10.1007/978-3-319-71682-4_12
Download citation
DOI: https://doi.org/10.1007/978-3-319-71682-4_12
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-71681-7
Online ISBN: 978-3-319-71682-4
eBook Packages: Computer ScienceComputer Science (R0)