Norm emergence under constrained interactions in diverse societies

ABSTRACT

Effective norms, emerging from sustained individual interactions over time, can complement societal rules and significantly enhance performance of individual agents and agent societies. Researchers have used a model that supports the emergence of social norms via learning from interaction experiences where each interaction is viewed as a stage game. In this social learning model, which is distinct from an agent learning from repeated interactions against the same player, an agent learns a policy to play the game from repeated interactions with multiple learning agents. The key research question is to characterize when and how the entire population of homogeneous learners converge to a consistent norm when multiple action combinations yield the same optimal payoff. In this paper we study two extensions to the social learning model that significantly enhances its applicability. We first explore the effects of heterogeneous populations where different agents may be using different learning algorithms. We also investigate norm emergence when agent interactions are physically constrained. We consider agents located on a grid where an agent is more likely to interact with other agents situated closer to it than those that are situated afar. The key new results include the surprising acceleration in learning with limited interaction ranges. We also study the effects of pure-strategy players, i.e., nonlearners in the environment.

REFERENCES

• 1: R. Axelrod. The complexity of cooperation: Agent-based models of confict and cooperation. Princeton University Press, Princeton, NJ, 1997.
• 2: G. Boella and L. Lesmo. A game theoretic approach to norms. Cognitive Science Quarterly, 2(3--4):492--512, 2002.
• 3: Guido Boella , Leendert van der Torre, Norm Governed Multiagent Systems: The Delegation of Control to Autonomous Agents, Proceedings of the IEEE/WIC International Conference on Intelligent Agent Technology, p.329, October 13-17, 2003
• 4: Multiagent learning using a variable learning rate, Artificial Intelligence, v.136 n.2, p.215-250, April 2002 [doi>10.1016/S0004-3702(02)00121-2]
• 5: Jordi Delgado , Josep M. Pujol , Ramón Sangüesa, Emergence of coordination in scale-free networks, Web Intelligence and Agent Systems, v.1 n.2, p.131-138, April 2003
• 6: F. Dignum, D. Kinny, and L. Sonenberg. From desires, obligations and norms to goals. Cognitive Science Quarterly, 2(3--4):407--430, 2002.
• 7: Joshua M. Epstein, Learning to Be Thoughtless: Social Norms and Individual Computation, Computational Economics, v.18 n.1, p.9-24, August 2001 [doi>10.1023/A:1013810410243]
• 8: D. Fudenberg and K. Levine. The Theory of Learning in Games. MIT Press, Cambridge, MA, 1998.
• 9: A. García-Camino , J. A. Rodríguez-Aguilar , C. Sierra , W. Vasconcelos, A rule-based approach to norm-oriented programming of electronic institutions, ACM SIGecom Exchanges, v.5 n.5, p.33-40, January 2006 [doi>10.1145/1124566.1124571]
• 10: M. Genesereth, M. Ginsberg, and J. Rosenschein. Cooperation without communications. In Proceedings of the National Conference on Artificial Intelligence, pages 51--57, Philadelphia, Pennsylvania, 1986.
• 11: D. Lewis. Convention: A Philosophical Study. Harvard University Press, 1969.
• 12: N. M. and M. R. M. Evolutionary games and spatial chaos. Nature(London), 359:826--829, 1992.
• 13: R. B. Myerson. Game Theory: Analysis of Confict. Harvard University Press, 1991.
• 14: Liviu Panait , Sean Luke, Cooperative Multi-Agent Learning: The State of the Art, Autonomous Agents and Multi-Agent Systems, v.11 n.3, p.387-434, November 2005 [doi>10.1007/s10458-005-2631-2]
• 15: M. Posch. Evolution of equilibria in the long run: A general theory and applications. Journal of Economic Theory, 65:383--415, 1995.
• 16: R. Powers and Y. Shoham. New criteria and a new algorithm for learning in multi-agent systems. In Proceedings of NIPS, 2005.
• 17: T. C. Schelling. The Strategy of Confict. Havard University Press, 1960.
• 18: F. Schweitzer, J. Zimmermann, and H. MÂĺuhlenbein. Coordination of decisions in a spatial agent modela. Physica A, 303(1--2):189--216, 2001.
• 19: S. Sen and S. Airiau. Emergence of norms through social learning. In Proceedings of the Twentieth International Joint Conference on Artificial Intelligence(IJCAI'07), pages 1507--1512, January 2007.
• 20: Yoav Shoham , Moshe Tennenholtz, On the emergence of social conventions: modeling, analysis, and simulations, Artificial Intelligence, v.94 n.1-2, p.139-166, July 1997 [doi>10.1016/S0004-3702(97)00028-3]
• 21: Kagan Tumer , David Wolpert, Collective Intelligence and Braess' Paradox, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.104-109, July 30-August 03, 2000
• 22: Christopher J. C. H. Watkins , Peter Dayan, Technical Note: $\backslash cal\; Q$-Learning, Machine Learning, v.8 n.3-4, p.279-292, May 1992 [doi>10.1007/BF00992698]
• 23: P. H. Young. The economics of convention. The Jounal of Economic Perspectives, 10(2):105--122, Spring 1996.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence

General Terms:
Experimentation

Keywords:
coordination game, norm, social dilemma