InterJournal Complex Systems, 1044
Status: Accepted
Manuscript Number: [1044]
Submission Date: 2004
Tags for All - Understanding and Engineering Tag Systems
Author(s): David Hales

Subject(s): CX.3

Category:

Abstract:

Since Holland (1993) introduced the concept of tags as a possible mechanism for the formation of cooperative individuals within an evolving system (among other things) a number of tag models with intriguing, and potentially very useful, properties have been advanced. Tags are markings or social cues that are attached to individuals (agents) and are observable by others. They evolve like any other trait for a given evolutionary model. The key point is that the tags have no direct behavioural implication for the individuals that carry them. Through indirect effects, however, they can evolve from initially random values into complex ever changing patterns that serve to structure interactions between individuals. Riolo (1997) showed how tags could boost cooperation in a scenario involving agents playing the iterated prisoners dilemma (IPD). Agents bias their game playing towards individuals with similar tags (the indirect effect). In these studies tags were represented by a single real number attached to each agent. Subsequently Hales (2000) advanced a model, using binary tag strings, that demonstrated the evolution of cooperative interactions in the single round Prisoners Dilemma (PD). Further work (Riolo et al, 2001) showed the emergence of altruistic giving behaviour and the evolution of cooperation and specialisation (Hales 2002) [footnote1]. These latter models are important because they advance a novel mechanism for evolving coordinated and cooperative interactions between unrelated agents that have no knowledge of each other and have never met previously. This obviates the need for repeated interactions (Tivers 1971), "genetic" relatedness (Hamilton 1964), "image scoring" (Nowak and Sigmund 1998) or strict spatial relationships (Nowak and Sigmund 1992) in the production of cooperation. Tag mechanisms therefor have potential engineering applications where these other methods are not applicable (see below). Although the general mechanism by which tags produce these results appears to be the result of a dynamic group formation and dissolution process (Hales 2000, Riolo et al 2001, Sigmund and Nowak 2001) with selection appearing to occur at the group-level, there has been little analytical or empirical exploration of this hypothesis. Indeed it is not even currently understood what the necessary and / or sufficient conditions might be to produce tag systems what give rise to these properties of interest (other than the specific existence proofs of the simulation results presented). In this paper we identify what appears to be a necessary condition that all previous models implicitly contained. In each case the authors had not identified this property as significant, yet without it the phenomena of interest disappears. We report the results of computational simulations which demonstrate the necessity of the condition and begin to sketch out a way towards analytically capturing the condition. The necessary condition is that the mutation rate of the tag must be much higher than the mutation rate applied to any behavioural traits. In this way cooperative "groups" (agents sharing the same or similar tags and interacting cooperatively with each other) can be "cloned" before being invaded by exploitative mutants that "kill" or "dissolve" the group. We demonstrate this by varying a parameter (the tag / action trait mutation ratio) over many of runs of a simulation model and measure cooperation. The result is a (non-linear) sigmoidial relationship, indicating a transition threshold for the relative mutation rate in a given system. Since recent work (Hales and Edmonds 2003 and in press) has indicated how tag mechanisms might be applied to the solution of complex engineering problems it would seem that a deeper understanding of the necessary and sufficient conditions of application would be timely. It would appear that such mechanisms may have application in self-organising adaptive Peer-2-Peer networks (Hales and Edmonds in press) and distributed and spontaneously self-organising mobile agent based applications (where issues of trust and cooperation are paramount but can not easily be dealt with using traditional techniques). More generally we argue for an exploratory simulation approach to the engineering of complex systems, where techniques and mechanisms are discovered in simulation then refined and developed in order to eventually produce deployable solutions. However, we identify many open problems in attempting to developer such a method based on our experiences. Footnotes: [footnote1] It should be noted that the results of these further studies have been questioned (Roberts and Sherrat 2002, Edmonds and Hales 2003). References: Edmonds, B. and Hales, D. (2003) Replication, Replication and Replication - Some Hard Lessons from Model Alignment. Journal of Artificial Societies and Social Simulation 6(4). Hales, D. (2000), Cooperation without Space or Memory: Tags, Groups and the Prisoner's Dilemma. In Moss, S., Davidsson, P. (Eds.) Multi-Agent-Based Simulation. Lecture Notes in Artificial Intelligence, 1979:157-166. Berlin: Springer-Verlag. Hales, D. (2001) Tag Based Cooperation in Artificial Societies. PhD Thesis (Dept. Of Computer Science, University of Essex, U.K. 2001). Hales, D. (2002) Evolving Specialisation, Altruism and Group-Level Optimisation Using Tags. In Sichman, J. S., Bousquet, F. Davidsson, P. (Eds.) Multi-Agent- Based Simulation II. Lecture Notes in Artificial Intelligence 2581:26-35 Berlin: Springer Verlag. Hales, D. and Edmonds, B. (2003) Evolving Social Rationality for MAS using "Tags", In Rosenschein, J. S., et al. (eds.) Proceedings of the 2nd International Conference on Autonomous Agents and Multiagent Systems, Melbourne, July 2003 (AAMAS03), ACM Press, 497-503 Hales, D. and Edmonds, B. (in press) Can Tags Build Working Systems? - From MABS to ESOA. Presented at the ESOA workshop at the AAMAS 2003 Conference (15th July 2003). To be published in Lecture Notes in Artificial Intelligence, Springer. Hamilton, W. D. (1964) The genetical evolution of social behaviours, I and II. J. Theor. Biol. 7, 1-52. Holland, J. (1993) The Effect of Lables (Tags) on Social Interactions. Santa Fe Institute Working Paper 93-10-064. Santa Fe, NM. Nowak, M. & May, R. (1992) Evolutionary Games and Spatial Chaos. Nature, 359, 532-554. Nowak, M. & Sigmund, K..(1998) Evolution of indirect reciprocity by image scoring. Nature, 393, 573-557. reciprocity. Nature 414, 441-443 Riolo, R. (1997) The Effects of Tag-Mediated Selection of Partners in Evolving Populations Playing the Iterated Prisoner's Dilemma. Santa Fe Institute Working Paper 97-02-016. Santa Fe, NM. Riolo, R. L., Cohen, M. D. & Axelrod, R. (2001) Evolution of cooperation without Roberts, G. & Sherratt, T. N. (2002) Nature 418, 449-500 Sigmund, K. and Nowak, A, M. (2001) Tides of Tolerance. Nature 414, 403-405. Trivers, R. (1971) The evolution of reciprocal altruism. Q. Rev. Biol. 46, 35- 57

Retrieve Manuscript
Submit referee report/comment


Public Comments: