Effective tag mechanisms for evolving cooperation

ABSTRACT

Certain observable features (tags), shared by a group of similar agents, can be used to signal intentions and can be effectively used to infer unobservable properties. Such inference will enable the formulation of appropriate behaviors for interaction with those agents. Tags have been previously shown to be successful in social dilemma situations such as the prisoner's dilemma, and more recently have been shown to be applicable to other games by augmenting the standard tag mechanisms. We examine these more general tag mechanisms, and explain previously reported results by more thoroughly examining their fundamental designs. We show that these new tag mechanisms, along with some adjustments and augmentations, can be effective in enabling stable, socially optimal, and fair cooperative outcomes to emerge in general sum games. We focus, in particular, on general-sum conflicted games, where socially optimal outcomes do not necessarily yield the best results for individual agents. We argue that the improvements and understanding of these mechanisms expands the usability of tag mechanisms for facilitating coordination in multiagent systems. We argue that they allow agents to effectively reuse knowledge learned form interactions with one agent when interacting with other agents sharing the same features.

REFERENCES

• 1: R. Axelrod. The complexity of cooperation: Agent-based models of conflict and cooperation. Princeton University Press, Princeton, NJ, 1997.
• 2: J. Bendor and P. Swistak. The evolutionary stability of cooperation. American Political Science Review, 91(2):290--307, June 1997.
• 3: S. J. Brams. Theory of Moves. Cambridge University Press, Cambridge: UK, 1994.
• 4: David Hales , Bruce Edmonds, Evolving social rationality for MAS using "tags", Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia [doi>10.1145/860575.860655]
• 5: John H. Holland , Keith J. Holyoak , Richard E. Nisbett , Paul R. Thagard, Induction: processes of inference, learning, and discovery, MIT Press, Cambridge, MA, 1986
• 6: C. M. Judd and B. Park. Definition and assessment of accuracy in social stereotypes. Psychological Review, 100(1):109--128, Jan 1993.
• 7: Matthew Matlock , Sandip Sen, Effective tag mechanisms for evolving coordination, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii [doi>10.1145/1329125.1329429]
• 8: A. McDonald and S. Sen. The success and failure of tag-mediated evolution of cooperation. In K. Tuyls, P. J. Hoen, K. Verbeeck, and S. Sen, editors, LAMAS, volume 3898 of Lecture Notes in Computer Science, pages 155--164. Springer, 2005.
• 9: R. B. Myerson. Game Theory: Analysis of Conflict. Harvard University Press, 1991.
• 10: 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]
• 11: R. Riolo. The effects and evolution of tag-mediated selection of partners in populations playing the Iterated Prisoner's Dilemma. In Proceedings of the Seventh International Conference on Genetic Algorithms, pages 378--385. Morgan Kaufmann Publishers, Inc., 1997.
• 12: R. Riolo, M. D. Cohen, and R. Axelrod. Cooperation without reciprocity. Nature, 414:441--443, 2001.
• 13: Peter Stone , Manuela Veloso, Multiagent Systems: A Survey from a Machine Learning Perspective, Autonomous Robots, v.8 n.3, p.345-383, June 2000 [doi>10.1023/A:1008942012299]

INDEX TERMS

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

General Terms:
Algorithms, Economics, Performance

Keywords:
cooperation, evolution, games, learning, tags