Abstract | ||
---|---|---|
Consider a system in which players at nodes of an underlying graph G
repeatedly play Prisoner's Dilemma against their neighbors. The players adapt
their strategies based on the past behavior of their opponents by applying the
so-called win-stay lose-shift strategy. This dynamics has been studied in
(Kittock 94), (Dyer et al. 2002), (Mossel and Roch, 2006).
With random scheduling, starting from any initial configuration with high
probability the system reaches the unique fixed point in which all players
cooperate. This paper investigates the validity of this result under various
classes of adversarial schedulers. Our results can be sumarized as follows:
1. An adversarial scheduler that can select both participants to the game can
preclude the system from reaching the unique fixed point on most graph
topologies. 2. A nonadaptive scheduler that is only allowed to choose one of
the participants is no more powerful than a random scheduler. With this
restriction even an adaptive scheduler is not significantly more powerful than
the random scheduler, provided it is "reasonably fair".
The results exemplify the adversarial scheduling approach we propose as a
foundational basis for the generative approach to social science (Epstein
2007). |
Year | Venue | Keywords |
---|---|---|
2008 | Clinical Orthopaedics and Related Research | discrete dynamical sys- tems,adversarial analysis,self stabilization,evolutionary games,social science,prisoner s dilemma,fixed point |
Field | DocType | Volume |
Discrete mathematics,Graph,Combinatorics,Scheduling (computing),Game dynamics,Network topology,Artificial intelligence,Generative grammar,Dilemma,Fixed point,Mathematics,Adversarial system | Journal | abs/0812.1 |
Citations | PageRank | References |
3 | 0.47 | 10 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Gabriel Istrate | 1 | 99 | 24.96 |
Madhav Marathe | 2 | 2775 | 262.17 |
S. S. Ravi | 3 | 2259 | 227.21 |