Effective tag mechanisms for evolving coordination

ABSTRACT

Tags or observable features shared by a group of similar agents are effectively used in real and artificial societies to signal intentions and can be used to infer unobservable properties and choose appropriate behaviors. Use of tags to select partners has been shown to produce stable cooperation in agent populations playing the Prisoner's Dilemma game. Existing tag mechanisms, however, can promote cooperation only if that requires identical actions from all group members. We propose a more general tag-based interaction scheme that facilitates and supports significantly richer coordination between agents. Our work is motivated by previous research that showed the ineffectiveness of current tag schemes for solving games requiring divergent actions. The mechanisms proposed here not only solves those problems but are effective for other general-sum games. We argue that these general-purpose tag mechanisms allow new application possibilities of multiagent learning algorithms as they allow an agent to reuse its learned knowledge about one agent when interacting with other agents sharing the same observable features.

REFERENCES

• 1: P. D. Allison. The cultural evolution of beneficent norms. Social Forces, 71:279--301, 1992.
• 2: R. Axelrod. The Evolution of Cooperation. Basic Books, 1984.
• 3: R. Axelrod. The complexity of cooperation: Agent-based models of conflict and cooperation. Princeton University Press, Princeton, NJ, 1997.
• 4: A. Ballim and Y. Wilks. Beliefs, stereotypes and dynamic agent modeling. User Modeling and User-Adapted Interaction, 1(1):33--65, 1991.
• 5: J. Bendor and P. Swistak. The evolutionary stability of cooperation. American Political Science Review, 91(2):290--307, June 1997.
• 6: D. Carmel and S. Markovitch. Learning models of intelligent agents. In Thirteenth National Conference on Artificial Intelligence, pages 62--67, Menlo Park, CA, 1996. AAAI Press/MIT Press.
• 7: A. J. Courtney. Control-display stereotypes for multicultural user systems. IEEE Transactions on Systems, Man, and Cybernetics, 22(4):681--687, July-Aug. 1992.
• 8: 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.
• 9: Sung Ho Ha, Digital Content Recommender on the Internet, IEEE Intelligent Systems, v.21 n.2, p.70-77, March 2006 [doi>10.1109/MIS.2006.24]
• 10: 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]
• 11: D. Hales and B. Edmonds. Applying a socially inspired technique (tags) to improve cooperation in p2p networks. IEEE Transactions in Systems, Man and Cybernetics -- Part A: Systems and Humans, 35(3):385--395, 2005.
• 12: John H. Holland , Keith J. Holyoak , Richard E. Nisbett , Paul R. Thagard, Induction: processes of inference, learning, and discovery, MIT Press, Cambridge, MA, 1986
• 13: C. M. Judd and B. Park. Definition and assessment of accuracy in social stereotypes. Psychological Review, 100(1):109--128, Jan. 1993.
• 14: B. Julstrom. The development of cooperation in genetic algorithms for the iterated prisoner's dilemma. In Proceedings of the 33rd Annual Midwest Instruction and Computing Symposium (MICS 2000), April 2000.
• 15: Karl Tuyls , Pieter Jan Hoen , Bram Vanschoenwinkel, An Evolutionary Dynamical Analysis of Multi-Agent Learning in Iterated Games, Autonomous Agents and Multi-Agent Systems, v.12 n.1, p.115-153, January 2006 [doi>10.1007/s10458-005-3783-9]
• 16: Joseph A. Konstan, Introduction to recommender systems: Algorithms and Evaluation, ACM Transactions on Information Systems (TOIS), v.22 n.1, p.1-4, January 2004 [doi>10.1145/963770.963771]
• 17: 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.
• 18: R. B. Myerson. Game Theory: Analysis of Conflict. Harvard University Press, 1991.
• 19: Eugene Nudelman , Jennifer Wortman , Yoav Shoham , Kevin Leyton-Brown, Run the GAMUT: A Comprehensive Approach to Evaluating Game-Theoretic Algorithms, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.880-887, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.238]
• 20: Georgios Paliouras , Vangelis Karkaletisis , Christos Papatheodorou , Constantine D. Spyropoulos, Exploiting learning techniques for the acquisition of user stereotypes and communities, Proceedings of the seventh international conference on User modeling, p.169-178, June 1999, Banff, Canada
• 21: 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]
• 22: B. Price and C. Boutilier. Accelerating reinforcement learning through implicit imitation. Applied Artificial Intelligence Journal, 19:569--629, 2003.
• 23: Paul Resnick , Hal R. Varian, Recommender systems, Communications of the ACM, v.40 n.3, p.56-58, March 1997 [doi>10.1145/245108.245121]
• 24: E. Rich. Stereotypes and user modeling. In A. Kobsa and W. Wahlster, editors, User Models in Dialog Systems, pages 35--51. Springer-Verlag, Berlin, 1989.
• 25: E. A. Rich. User modeling via stereotypes. Cognitive Science, 3:329--354, 1979.
• 26: 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.
• 27: R. Riolo, M. D. Cohen, and R. Axelrod. Cooperation without reciprocity. Nature, 414:441--443, 2001.
• 28: M. Root. How we divide the world. In D. A. Howard, editor, PSA' 1998: Proceedings of the 1998 Biennial Meetings of the Philosophy of Science Association, Part II: Symposium Papers, pages S628--S639. Philosophy of Science Association, Newark, Delaware, 1998.
• 29: J. Ben Schafer , Joseph Konstan , John Riedi, Recommender systems in e-commerce, Proceedings of the 1st ACM conference on Electronic commerce, p.158-166, November 03-05, 1999, Denver, Colorado, United States [doi>10.1145/336992.337035]
• 30: Bracha Shapira , Peretz Shoval , Uri Hanani, Stereotypes in information filtering systems, Information Processing and Management: an International Journal, v.33 n.3, p.273-287, May 1997 [doi>10.1016/S0306-4573(97)00003-4 ]
• 31: K. Sigmund and M. A. Nowak. The alternating prisoner's dilemma. Journal of Theoretical Biology, 38:262--275, 1994.
• 32: J. L. Stimpson, M. A. Goodrich, and L. C. Walters. Satisficing and learning cooperation in the prisoner's dilemma. In Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, pages 535--540, 2001.
• 33: 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 ]
• 34: Dajun Zeng , Katia Sycara, Bayesian learning in negotiation, International Journal of Human-Computer Studies, v.48 n.1, p.125-141, Jan., 1998 [doi>10.1006/ijhc.1997.0164 ]
• 35: Xiangmin Zhang , Hui Han, An empirical testing of user stereotypes of information retrieval systems, Information Processing and Management: an International Journal, v.41 n.3, p.651-664, May 2005 [doi>10.1016/j.ipm.2004.01.005]

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:
coordination, evolution, games, learning, prisoner's dilemma, tags