Games and nets literature review

Back to Games and networks

Literature

Gil and Zanette. Coevolution of agents and networks: Opinion spreading and community disconnection. Physics Letters B (2006) pdf

Eguilez, V. et al. Cooperation and emergence of role differentiation in the dynamics of social networks. arXiv: physics (2006) pdf

I found this paper describing a very similar model and I believe this is more or less what we intend to do. On this model agents play the PD in a network structure. More or less it goes like this; Links between Defector and defector break and are randomly assigned. Rules (when playing PD) between the agents are adapted by imitating the wealthiest neighbor (this would be adaptation within the agents lifetime (learning), there is no evolutionary adaptation as we discussed in the evening meeting, which we could also implement and compare both). Their result is some role differentiation between the agents (leaders, conformist, exloiters, etc). Their treating the problem "how the network is dynamically formed or how a given network structure is reached after social agents interact for a long time".

Ohtsuki, H., Hauert, C., Lieberman, E. & Nowak, M.A. A simple rule for the evolution of cooperation on graphs and social networks. Nature 441: 502-505 (2006). pdf

This is a simple exploration of how network structure -- in particular, connectedness -- affects the evolution of cooperation. They find that a good predictor for whether cooperation can invade and spread in a network is whether the benefit-cost ratio is greater than the (average) degree of the graph. They derive the result exactly for a cycle, approximately for a random graph where every node has the same degree, and use simulation to show that the fit is good for true random graphs and scale-free networks.

Santos, F.C., Pacheco, J.M. & Lenaerts T. Evolutionary dynamics of social dilemmas in structured heterogeneous populations. Proc Nat Acad Sci USA 103: 3490-3494 (2006). pdf

The authors show that heterogeneity in the degree of the graph (e.g. scale-free networks as opposed to single-scale networks) can encourage the evolution of cooperation. They simulate using what amounts to an imitation rule on a fixed network structure, and parameterize the game that is played so that it can represent three popular games: Stag Hunt, Hawk-Dove, and Prisoner's Dilemma.

Page, K. Nowak, M. Sigmund, K. The spatial ultimatum game. Proc. R. Soc. Lond. B 267, 2177-2182 (2000) pdf

In an ultimatum game played between members of a population with random mixing offer strategies evolve towards zero, provided the mutation rate per generation is small. On a 1D lattice they approximate a fair split, and on a 2D grid they are around 0.35.

Goyal, S. Learning in Networks: a Survey. Forthcoming in, Group formation in economics: networks, clubs, and coalitions (2003) pdf

A broad overview of learning on both static and adaptive networks. The paper examines a variety of games including those involving information aquisition, information sharing, cooperation, conflict and others.

Jin, E., Girvin, M. and Newman, M. Structure of Growing Social Networks Physical Review E (2001) pdf

Some interesting ideas in general, but specifically useful for thinking about how to model the growth and decay of social networks. Also, since this is co-authored by Mark Newman it would be convenient to ask him about the ideas put forth in the paper.

Not yet read:

Nowak, M. and Sigmund, K. Evolutionary dynamics of biological games. Science 303 (2004) pdf

Albert, R. and Barabási, A. Topology of Evolving Networks: Local Events and Universality Physical Review Letters (2000) pdf

Jackson, M. and Wolinski, A. A Strategic Model of Social and Economic Networks Journal of Economic Theory (1996) pdf

Bala, V. and Goyal, S. A Noncooperative Model of Network Formation Econometrica (2000) pdf

Social Foraging

Rogers A. Does biology constrain culture? American Anthropologist 90(4): 819–831 (1988). pdf

Rogers shows that in a population with both individual learning strategies and social learning strategies, for certain probabilites of environmental change in any given generation, the mixed evolutionarily stable strategy will be at a point at which the payoff from social learning exactly matches that of individual learning. Individual learning is assumed to have a constant, frequency independent payoff. He assumes individual learning to have a cost associated with it and social learning to be costless. The model has no space or other structure across which animals communicate. If the environment changes with too great a probability per generation social learners will be eliminated.

Wakano, J. Aoki, K. and Feldman, M. A mathematical analysis of social learning Theoretical Population Biology 66 249–258 (2004) pdf

The authors present a model in which social learning, individual learning and fixed (genetic) strategies are in competition. Social learning has cost d, individual learning has cost c and making a mistake about the state of the environment has cost s. Costs are ordered d < c < s. The fitnesses of the different strategies vary as a function of the number of generations between environmental changes l. Individual learners win when the environment changes every generation (l = 1), decreasing in frequency as the number of generations between changes increases. Social learners are at zero frequency when l = 1, rising in frequency while l < 684. When l > 684 innate strategies suddenly rise from zero frequency to take over the whole population. This critical value of l* = 683 is for a given set of parameters .

Dall, S. et al. Information and its use by animals in evolutionary ecology. TREE 20 4 (2005) pdf

This paper includes a section on 'inadvertant social information' - ie cues. The authors mention that use of social cues can lead to informational cascades - there's a literature in economics on this that I know exists but haven't read much of. This can be valuable, but can also lead to important errors. An examples among animals is the take-off behaviour of large flocks of birds. Many of the birds in a departing flock will take off on the basis of only social cues from the birds around them - this may be valuable if it usually signifies approaching danger, but a waste of energy if it does not. The sharing of information through social cues has useful emergent group level results such as 1. the synchronisation of patch departure 2. the rapid learning of local habitat depletion 3. the estimation of habitat or bredding colony quality (eg from observation of the number of offspring fledged in various colonies). There are likely to be costs involved in both types of information collection (social and individual) and as a result it may pay to specialise in one or the other. Information pooling among social insects is heavily studied, often in haplodiploid species such as ants or bees.

Liu, Y. Passino, K. Biomimicry of Social Foraging Bacteria for Distributed Optimization: Models, Principles, and Emergent Behaviors. JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS Vol. 115, No. 3, pp. 603–628 (2002) pdf

An evolutionary simulation of bacterial social foraging by means of 'attractants' they secrete in space and which others respond to. Extending this with explicit networks might be exciting.

Social_network_growth_with_assortative_mixing._Physica_A_338,_119_(2004)._Catanzaro,_Michele et al. pdf

Using a variant on the “BarabHasi–Albert preferential attachment” model the authors reproduce some of the assortative qualities of social networks. Their variation includes a greater level of mixing as the life of the node is > than that of the edge. It is demonstrated that strong assortativity can break the scale free nature of the networks. (this could be of interest for the consequences of clustering strategies in the proposed model)

Lieberman, E. Hauert, C. Nowak, M. Evolutionary dynamics on graphs. Nature 433 (2005) pdf

The authors investigate the consequences of sub structuring in a population using a graph theoretic approach. They observe that the structure can promote drift over selective processes relating to gene fixation. Where multiple roots or origins exist in the graphs mutants occurring in these nodes may never fixate or go extinct. Most interestingly they investigate whether graphs exist that could have the opposite effect. They find that graphs can be produced where there fixation probability of advantageous mutations approaches unity, all but eliminating drift in sufficiently large poulations. (the consequences of amplifiers and suppressors of natural selection occurring in networks are huge. Under what conditions and processes do populations increase their evolvability, making a transition between the dominance of evolutionary processes?? They also look at a game played on a cyclic network with a simple pay of matrix on pages 314-5.)

Back to games and nets group