Name
Abstract | ||
|---|---|---|
In this paper we advocate the study of discrete models of social dynamics under adversarial scheduling. The approach we propose forms part of a foundational basis for a generative approach to social science (Epstein 2007). We highlight the feasibility of the adversarial scheduling approach by using it to study the Prisoners's Dilemma Game with Pavlov update, a dynamics that has already been investigated under random update in Kittock (1994), Dyer et al. (2002), Mossel and Roch (2006) and Dyer and Velumailum (2011). The model is specified by letting players at the nodes of an underlying graph G repeatedly play the Prisoner's Dilemma against their neighbours. The players adapt their strategies based on the past behaviour of their opponents by applying the so-called win-stay lose-shift strategy. With random scheduling, starting from any initial configuration, the system reaches the fixed point in which all players cooperate with high probability. On the other hand, under adversarial scheduling the following results hold: A scheduler that can select both game participants can preclude the system from reaching the unique fixed point on most graph topologies. A non-adaptive 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'. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1017/S0960129511000533 | Mathematical Structures in Computer Science |
Keywords | Field | DocType |
non-adaptive scheduler,social dynamic,adaptive scheduler,random update,adversarial scheduling,pavlov update,dilemma game,discrete model,adversarial scheduling approach,random scheduling,generative approach,random scheduler | Graph,Scheduling (computing),Computer science,Network topology,Artificial intelligence,Social dynamics,Fixed point,Dilemma,Generative grammar,Adversarial system | Journal |
Volume | Issue | ISSN |
22 | 5 | 0960-1295 |
Citations | PageRank | References |
1 | 0.37 | 14 |
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 |