Tags and image scoring for robust cooperation

ABSTRACT

Establishing and maintaining cooperation is an enduring problem in multi-agent systems and, although several solutions exist, the increased use of online trading systems, peer-to-peer networks, and ubiquitous computing environments mean that it remains an important question. Environments are emerging in which large numbers of agents are required to cooperate, but where repeat interactions between agents may be rare or non-existent. Most existing approaches to cooperation rely on reciprocity to establish notions of trust and reputation. However, where repeat interactions are rare such approaches are not always effective. In this paper we use ideas from biology and the social sciences to provide a mechanism that supports cooperation in such environments. Our mechanism combines a tag-based method to enable co-operation given a lack of reciprocity, with an adaptation of a simple image scoring reputation model to cope with cheating agents. Using a simple peer-to-peer scenario we show how cooperative behaviour is favoured, and how the influence of cheating agents can be reduced using only minimal information about an agent's neighbours.

REFERENCES

• 1: R. D. Alexander. The Biology of Moral Systems. Aldine de Gruyter, 1987.
• 2: P. D. Allison. The cultural evolution of beneficent norms. Social Forces, 71(2):279--301, 1992.
• 3: R. Boyd and P. J. Richerson. The evolution of indirect reciprocity. Social Networks, 11:213--236, 1989.
• 4: R. Dawkins. The Selfish Gene. Oxford University Press, 1976.
• 5: B. Edmonds and D. Hales. Replication, replication and replication --- some hard lessons from model alignment. Journal of Artificial Societies and Social Simulation, 6(4), 2003.
• 6: D. Hales. Understanding tag systems by comparing tag models. In B. Edmonds, C. H. Iglesias, and K. G. Troitzsch, editors, Social Simulation: Technologies, Advances and New Discoveries. Idea Group, 2007.
• 7: 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]
• 8: D. Hales and B. Edmonds. Applying a socially inspired technique (tags) to improve cooperation in P2P networks. IEEE Transactions on Systems, Man, and Cybernetics, Part A, 35(3):385--395, 2005.
• 9: John H. Holland, Hidden order: how adaptation builds complexity, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1996
• 10: Audun Jøsang , Roslan Ismail , Colin Boyd, A survey of trust and reputation systems for online service provision, Decision Support Systems, v.43 n.2, p.618-644, March, 2007 [doi>10.1016/j.dss.2005.05.019]
• 11: R. M. Kramer. Trust and distrust in organizations: Emerging perspectives, enduring questions. Annual Review of Psychology, 50:659--598, 1999.
• 12: 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]
• 13: M. Nowak and K. Sigmund. Evolution of indirect reciprocity by image scoring. Nature, 393:573--577, 1998.
• 14: M. Nowak and K. Sigmund. Evolution of indirect reciprocity. Nature, 437:1291--1298, 2005.
• 15: Sarvapali D. Ramchurn , Dong Huynh , Nicholas R. Jennings, Trust in multi-agent systems, The Knowledge Engineering Review, v.19 n.1, p.1-25, March 2004 [doi>10.1017/S0269888904000116]
• 16: Paul Resnick , Ko Kuwabara , Richard Zeckhauser , Eric Friedman, Reputation systems, Communications of the ACM, v.43 n.12, p.45-48, Dec. 2000 [doi>10.1145/355112.355122]
• 17: R. Riolo, M. Cohen, and R. Axelrod. Evolution of cooperation without reciprocity. Nature, 414:441--443, 2001.
• 18: G. Roberts and T. N. Sherratt. Does similarity breed cooperation? Nature, 418:499--500, 2002.

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Reliability

Keywords:
P2P, cooperation, evolution, image scoring, reputation, tags