5th Conference on Computability in Europe

Stability under Strategy Switching

Soumya Paul, R. Ramanujam and Sunil Simon

Proc. 5th Conference on Computability in Europe (CiE 2009), LNCS 5635, pages 389-398, Springer, 2009.

© Springer-Verlag.


We suggest that a process-like notion of strategy is relevant in the context of interactions in systems of self-interested agents. In this view, strategies are not plans formulated by rational agents considering all possible futures and (mutually recursively) taking into account strategies employed by other players. Instead, they are partial; players start with a set of potential strategies and dynamically switch between them. This necessitates some means in the model for players to access each others' strategies, and we suggest a syntax by which players' rationale for such switching may be specified and structurally composed. In such a model one can ask a stability question: given a game arena and a strategy specification, whether players eventually settle down to strategies without further switching. We show that this problem can be algorithmically solved using automata theoretic methods.

Technical report close to the article PDF.