Slow emergence of cooperation for win-stay lose-shift on trees |
| |
Authors: | Elchanan Mossel Sébastien Roch |
| |
Affiliation: | (1) Department of Statistics, University of California, Berkeley, Berkeley, CA, 94720-3860 |
| |
Abstract: | 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.
Editors: Amy Greenwald and Michael Littman. |
| |
Keywords: | Games on graphs Learning Prisoner’ s dilemma game Win-Stay Lose-Shift Oriented percolation Emergence of cooperation |
本文献已被 SpringerLink 等数据库收录! |
|