Autori: Gabriel Istrate, Madhav V. Marathe and S. S. Ravi

Editorial: Mathematical Structures in Computer Science, 22(5), p.788-815, 2012.

Rezumat:

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 by Shoham and Tennenholtz [1994], Kittock [1993], Dyer et al [2002], Mossel and Roch [2007].

Under random scheduling (i.e. when at each step the two nodes that play are specified by an edge of G chosen uniformly at random), 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 summarized 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. On the other hand a nonadaptive scheduler that is only allowed to choose one of the participants is no more powerful than a random scheduler.
Even an adaptive scheduler is not significantly more powerful, 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]).

A conference version (short abstract) appeared under the name „Adversarial models in evolutionary game dynamics” in Proceedings of the Twelfth Annual Symposium on Discrete Algorithms (SODA’01), Washington, DC, USA

A preprint of the full version can be
downloaded from

http://arxiv.org/abs/0812.1194

Cuvinte cheie: adversarial scheduling analysis, evolutionary game theory

URL: http://journals.cambridge.org/action/displayJournal?jid=msc