Slow Emergence of Cooperation for Win-Stay Lose-Shift on Trees

Details Slow Emergence of Cooperation for Win-Stay Lose-Shift on Trees Slow Emergence of Cooperation for Win-Stay Lose-Shift on Trees

2005-09-23

arxiv.org/abs/math/0509576v1

Mathematics

Probability

Scientific paper

We consider a group of agents on a graph who repeatedly play the prisoner's dilemma game against their neighbors. The players adapt their actions to the past behavior of their opponents by applying the win-stay lose-shift strategy. On a finite connected graph, it is easy to see that the system learns to cooperate by converging to the all-cooperate state in a finite time. We analyze the rate of convergence in terms of the size and structure of the graph. [Dyer et al., 2002] showed that the system converges rapidly on the cycle, but that it takes a time exponential in the size of the graph to converge to cooperation on the complete graph. We show that the emergence of cooperation is exponentially slow in some expander graphs. More surprisingly, we show that it is also exponentially slow in bounded-degree trees, where many other dynamics are known to converge rapidly.

Affiliated with

Also associated with

No associations

Rating

Slow Emergence of Cooperation for Win-Stay Lose-Shift on Trees 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 Slow Emergence of Cooperation for Win-Stay Lose-Shift on Trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Slow Emergence of Cooperation for Win-Stay Lose-Shift on Trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-552939