Inscriere cercetatori

Premii Ad Astra

premii Ad Astra

Asociația Ad Astra a anunțat câștigătorii Premiilor Ad Astra 2022: Proiectul și-a propus identificarea și popularizarea modelelor de succes, a rezultatelor excepționale ale cercetătorilor români din țară și din afara ei.

Asociatia Ad Astra a cercetatorilor romani lanseaza BAZA DE DATE A CERCETATORILOR ROMANI DIN DIASPORA. Scopul acestei baze de date este aceea de a stimula colaborarea dintre cercetatorii romani de peste hotare dar si cu cercetatorii din Romania. Cercetatorii care doresc sa fie nominalizati in aceasta baza de date sunt rugati sa trimita un email la

Adversarial scheduling in discrete models of social dynamics

Domenii publicaţii > Ştiinţe informatice + Tipuri publicaţii > Articol în revistã ştiinţificã

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

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


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

Cuvinte cheie: adversarial scheduling analysis, evolutionary game theory