research-article

Robust convention emergence in social networks through self-reinforcing structures dissolution

Authors:

Daniel Villatoro,

Jordi Sabater-Mir,

Sandip SenAuthors Info & Claims

ACM Transactions on Autonomous and Adaptive Systems (TAAS), Volume 8, Issue 1

Article No.: 2, Pages 1 - 21

https://doi.org/10.1145/2451248.2451250

Published: 19 April 2013 Publication History

Abstract

Convention emergence solves the problem of choosing, in a decentralized way and among all equally beneficial conventions, the same convention for the entire population in the system for their own benefit. Our previous work has shown that reaching 100% agreement is not as straighforward as assumed by previous researchers, that, in order to save computational resources fixed the convergence rate to 90% (measuring the time it takes for 90% of the population to coordinate on the same action). In this article we present the notion of social instruments as a set of mechanisms that facilitate and accelerate the emergence of norms from repeated interactions between members of a society, only accessing local and public information and thus ensuring agents' privacy and anonymity. Specifically, we focus on two social instruments: rewiring and observation. Our main goal is to provide agents with tools that allow them to leverage their social network of interactions while effectively addressing coordination and learning problems, paying special attention to dissolving metastable subconventions.

The first experimental results show that even with the usage of the proposed instruments, convergence is not accelerated or even obtained in irregular networks. This result leads us to perform an exhaustive analysis of irregular networks discovering what we have defined as Self-Reinforcing Structures (SRS). The SRS are topological configurations of nodes that promote the establishment and persistence of subconventions by producing a continuous reinforcing effect on the frontier agents. Finally, we propose a more sophisticated composed social instrument (observation + rewiring) for robust resolution of subconventions, which works by the dissolution of the stable frontiers caused by the Self-Reinforcing Substructures (SRS) within the social network.

References

[1]

Albert, R., Jeong, H., and Barabasi, A. L. 2000. Error and attack tolerance of complex networks. Nature 406, 6794, 378--382.

[2]

Babaoglu, O. and Jelasity, M. 2008. Self-&ast; properties through gossiping. Philos. Trans. Series A Math. Physical, Engin. Sci. 366, 1881, 3747--3757.

[3]

Barabasi, A.-L. and Albert, R. 1999. Emergence of scaling in random networks. Sci. 286, 509--512.

[4]

Chao, I., Ardaiz, O., and Sanguesa, R. 2008. Tag mechanisms evaluated for coordination in open multiagent systems. In Engineering Societies in the Agents World VIII, A. Artikis, G. OHare, K. Stathis, and G. Vouros, Eds., Lecture Notes in Computer Science, vol. 4995, Springer, 254--269.

Digital Library

[5]

Coleman, J. 1998. Foundations of Social Theory. Belknap Press of Harvard University Press.

[6]

Conte, R. and Paolucci, M. 2002. Reputation in Artificial Societies: Social Beliefs for Social Order. Vol. 7, Kluwer.

Digital Library

[7]

De Pinninck, A. P., Sierra, C., and Schorlemmer, M. 2007. Friends no more: Norm enforcement in multi-agent systems. In Proceedings of the 6^th International Joint Conference on Autonomous Agents and Multiagent Systems. 640--642.

Digital Library

[8]

Delgado, J. 2002. Emergence of social conventions in complex networks. Artif. Intell. 141, 1--2, 171--185.

Digital Library

[9]

Delgado, J., Pujol, J. M., and Sanguesa, R. 2003. Emergence of coordination in scale-free networks. Web Intell. Agent Syst. 1, 2, 131--138.

Digital Library

[10]

Epstein, J. M. 2000. Learning to be thoughtless: Social norms and individual computation. Working papers 00-03-022, Santa Fe Institute.

[11]

Freeman, L. C. 1979. Centrality in social networks: Conceptual clarification. Social Netw. 1, 3, 215--239.

[12]

Griffiths, N. and Luck, M. 2010. Changing neighbours: Improving tag-based cooperation. In Proceedings of the 9^th International Conference on Autonomous Agents and Multiagent Systems. 249--256.

Digital Library

[13]

Hales, D. 2002. Group reputation supports beneficent norms. J. Artif. Soc. Social Simul. 5, 4.

[14]

Hales, D. and Arteconi, S. 2006. Slacer: A self-organizing protocol for coordination in p2p networks. IEEE Intell. Syst. 21, 29, 35.

Digital Library

[15]

Holland, J. 1993. The effects of labels (tags) on social interactions. Working papers 93-10-064, Santa Fe Institute.

[16]

Kittock, J. E. 1993. Emergent conventions and the structure of multi-agent systems. In Proceedings of the Complex Systems Summer School. Santa Fe Institute Studies in the Sciences of Complexity Lecture Vol. VI. Lectures in Complex Systems, Santa Fe Institute. Addison-Wesley, 507--521.

[17]

Mukherjee, P., Sen, S., and Airiau, S. 2007. Norm emergence in spatially contrained interactions. In Proceedings of the Working Notes of the Adaptive and Learning Agents Workshop at the 6^th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS'07).

[18]

Mukherjee, P., Sen, S., and Airiau, S. 2008. Norm emergence under constrained interactions in diverse societies. In Proceedings of the 7^th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS'08). 779--786.

Digital Library

[19]

Radwanick, S. 2010. Facebook captures top spot among social networking sites in india. http://www.comscore.com/Insights/Press_Releases/2010/8/Facebook_Captures_Top_Spot_among_Social_Networking_Sites_in_India

[20]

Salazar-Ramirez, N., Rodriguez-Aguilar, J. A., and Arcos, J. L. 2008. An infection-based mechanism for self-adaptation in multi-agent complex networks. In Proceedings of the 2^nd IEEE International Conference on Self-Adaptive and Self-Organizing Systems (SASO'08). P. R. S. Brueckner and U. Bellur, Eds., 161--170.

Digital Library

[21]

Savarimuthu, B. T. R., Cranefield, S., Purvis, M., and Purvis, M. 2007. Role model based mechanism for norm emergence in artificial agent societies. In Proceedings of the International Conference on Coordination, Organizations, Institutions, and Norms in Agent Systems III (COIN'07). 203--217.

Digital Library

[22]

Scott, J. 2000. Social Network Analysis: A Handbook 2^nd Ed. Sage Publications.

[23]

Sen, S. and Airiau, S. 2007. Emergence of norms through social learning. In Proceedings of the 20^th International Joint Conference on Artificial Intelligence (IJCAI'07). 1507--1512.

Digital Library

[24]

Shoham, Y. and Tennenholtz, M. 1997. On the emergence of social conventions: Modeling, analysis, and simulations. Artif. Intell. 94, 139--166.

Digital Library

[25]

Toivonen, R., Castello, X., Eguiluz, V. M., Saramaki, J., Kaski, K., and San Miguel, M. 2009. Broad lifetime distributions for ordering dynamics in complex networks. Phys. Rev. E Statist. Nonlin. Soft Matter Phys. 79, 1--8.

[26]

Urbano, P., Balsa, J., Antunes, L., and Moniz, L. 2009. Force versus majority: A comparison in convention emergence efficiency. In Proceedings of the International Workshop on Coordination, Organizations, Institutions, and Norms in Agent Systems IV (COIN@AAMAS'09). Lecture Notes in Computer Science, vol. 5428, Springer, 48--63.

Digital Library

[27]

Villatoro, D., Sen, S., and Sabater-Mir, J. 2009. Topology and memory effect on convention emergence. In Proceedings of the International Conference of Intelligent Agent Technology (IAT). IEEE Press.

Digital Library

[28]

Walker, A. and Wooldridge, M. 1995. Understanding the emergence of conventions in multi-agent systems. In Proceedings of the 1^st International Conference on Multi--Agent Systems. V. Lesser, Ed., MIT Press, 384--389.

[29]

Watkins, C. and Dayan, P. 1992. Q-Learning. Mach. Learn. 8, 3-4, 279--292.

Digital Library

[30]

Watts, D. J. and Strogatz, S. H. 1998. Collective dynamics of “small-world” networks. Nature 393, 6684, 440--442.

Cited By

Wang YMiao YFu GLu PYang YGu WFang ZNiu L(2024)Norm Emergence through Conflict-Blocking Interactions in Industrial Internet of Things EnvironmentsSensors10.3390/s2418604724:18(6047)Online publication date: 19-Sep-2024
https://doi.org/10.3390/s24186047
Wang ZLi RJin XDing H(2023)Emergence of Social Norms in Metanorms Game With High-Order Interaction TopologyIEEE Transactions on Computational Social Systems10.1109/TCSS.2022.314497810:3(1057-1072)Online publication date: Jun-2023
https://doi.org/10.1109/TCSS.2022.3144978
Locodi AO’Riordan C(2021)Introducing a graph topology for robust cooperationRoyal Society Open Science10.1098/rsos.2019588:5Online publication date: 5-May-2021
https://doi.org/10.1098/rsos.201958
Show More Cited By

Index Terms

Robust convention emergence in social networks through self-reinforcing structures dissolution
1. Computing methodologies
  1. Artificial intelligence
    1. Distributed artificial intelligence

Recommendations

Emergence of conventions through social learning

Societal norms or conventions help identify one of many appropriate behaviors during an interaction between agents. The offline study of norms is an active research area where one can reason about normative systems and include research on designing and ...
Manipulating convention emergence using influencer agents

Coordination in open multi-agent systems (MAS) can reduce costs to agents associated with conflicting goals and actions, allowing artificial societies to attain higher levels of aggregate utility. Techniques for increasing coordination typically involve ...
The impact of social placement of non-learning agents on convention emergence
AAMAS '12: Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems - Volume 3

Social conventions are important for establishing and maintaining coordination in groups of agents, especially where there is no centralised control. As individuals interact, learn, and update their strategies, effective coordination can be achieved ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Autonomous and Adaptive Systems

ACM Transactions on Autonomous and Adaptive Systems Volume 8, Issue 1

April 2013

126 pages

ISSN:1556-4665

EISSN:1556-4703

DOI:10.1145/2451248

Issue’s Table of Contents

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 April 2013

Accepted: 01 July 2012

Revised: 01 March 2012

Received: 01 March 2011

Published in TAAS Volume 8, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Generalitat de Catalunya
Sixth Framework Programme
Ministerio de Educación, Cultura y Deporte
Proyecto Intramural de Frontera MacNorms (PIFCOO-08-00017)

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
326
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wang YMiao YFu GLu PYang YGu WFang ZNiu L(2024)Norm Emergence through Conflict-Blocking Interactions in Industrial Internet of Things EnvironmentsSensors10.3390/s2418604724:18(6047)Online publication date: 19-Sep-2024
https://doi.org/10.3390/s24186047
Wang ZLi RJin XDing H(2023)Emergence of Social Norms in Metanorms Game With High-Order Interaction TopologyIEEE Transactions on Computational Social Systems10.1109/TCSS.2022.314497810:3(1057-1072)Online publication date: Jun-2023
https://doi.org/10.1109/TCSS.2022.3144978
Locodi AO’Riordan C(2021)Introducing a graph topology for robust cooperationRoyal Society Open Science10.1098/rsos.2019588:5Online publication date: 5-May-2021
https://doi.org/10.1098/rsos.201958
Diaz CNikolaev APerla AVeremyev APasiliao E(2019)Robust communication network formation: a decentralized approachComputational Social Networks10.1186/s40649-019-0072-36:1Online publication date: 27-Nov-2019
https://doi.org/10.1186/s40649-019-0072-3
Morris-Martin ADe Vos MPadget J(2019)Norm emergence in multiagent systems: a viewpoint paperAutonomous Agents and Multi-Agent Systems10.1007/s10458-019-09422-033:6(706-749)Online publication date: 1-Nov-2019
https://dl.acm.org/doi/10.1007/s10458-019-09422-0
Ajmeri NGuo HMurukannaiah PSingh M(2018)Robust norm emergence by revealing and reasoning about contextProceedings of the 27th International Joint Conference on Artificial Intelligence10.5555/3304415.3304421(28-34)Online publication date: 13-Jul-2018
https://dl.acm.org/doi/10.5555/3304415.3304421
Wang YLu WHao JWei JLeung HAndre EKoenig SDastani MSukthankar G(2018)Efficient Convention Emergence through Decoupled Reinforcement Social Learning with Teacher-Student MechanismProceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3237383.3237501(795-803)Online publication date: 9-Jul-2018
https://dl.acm.org/doi/10.5555/3237383.3237501
Saghiri AMeybodi M(2018)An adaptive super-peer selection algorithm considering peers capacity utilizing asynchronous dynamic cellular learning automataApplied Intelligence10.1007/s10489-017-0946-848:2(271-299)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.1007/s10489-017-0946-8
Diaz CNikolaev APasiliao E(2018)A Decentralized Deterministic Information Propagation Model for Robust CommunicationComputational Data and Social Networks10.1007/978-3-030-04648-4_20(235-246)Online publication date: 18-Nov-2018
https://doi.org/10.1007/978-3-030-04648-4_20
Ajmeri NMurukannaiah PGuo HSingh MLarson KWinikoff MDas SDurfee E(2017)ArnorProceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems10.5555/3091125.3091163(230-238)Online publication date: 8-May-2017
https://dl.acm.org/doi/10.5555/3091125.3091163
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents