On the Imitation Strategy for Games on Graphs

Details On the Imitation Strategy for Games on Graphs On the Imitation Strategy for Games on Graphs

2011-02-18

arxiv.org/abs/1102.3879v1

Computer Science

Computer Science and Game Theory

32 pages

Scientific paper

In evolutionary game theory, repeated two-player games are used to study strategy evolution in a population under natural selection. As the evolution greatly depends on the interaction structure, there has been growing interests in studying the games on graphs. In this setting, players occupy the vertices of a graph and play the game only with their immediate neighbours. Various evolutionary dynamics have been studied in this setting for different games. Due to the complexity of the analysis, however, most of the work in this area is experimental. This paper aims to contribute to a more complete understanding, by providing rigorous analysis. We study the imitation dynamics on two classes of graph: cycles and complete graphs. We focus on three well known social dilemmas, namely the Prisoner's Dilemma, the Stag Hunt and the Snowdrift Game. We also consider, for completeness, the so-called Harmony Game. Our analysis shows that, on the cycle, all four games converge fast, either to total cooperation or total defection. On the complete graph, all but the Snowdrift game converge fast, either to cooperation or defection. The Snowdrift game reaches a metastable state fast, where cooperators and defectors coexist. It will converge to cooperation or defection only after spending time in this state which is exponential in the size, n, of the graph. In exceptional cases, it will remain in this state indefinitely. Our theoretical results are supported by experimental investigations.

Affiliated with

Also associated with

No associations

Rating

On the Imitation Strategy for Games on Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Imitation Strategy for Games on Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Imitation Strategy for Games on Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-213361