Rules for Computing Resistance of Transitions of Learning Algorithms in Games

Abstract

In a finite game the Stochastically Stable States (SSSs) of adaptive play are contained in the set of minimizers of resistance trees. Also, in potential games, the SSSs of the log-linear learning algorithm are the minimizers of the potential function. The SSSs can be characterized using the resistance trees of a Perturbed Markov Chain (PMC), they are the roots of minimum resistance tree. Therefore, computing the resistance of trees in PMC is important to analyze the SSSs of learning algorithms. A learning algorithm defines the Transition Probability Function (TPF) of the induced PMC on the action space of the game. Depending on the characteristics of the algorithm the TPF may become composite and intricate. Resistance computation of intricate functions is difficult and may even be infeasible. Moreover, there are no rules or tools available to simplify the resistance computations. In this paper, we propose novel rules that simplify the computation of resistance. We first, give a generalized definition of resistance that allows us to overcome the limitations of the existing definition. Then, using this new definition we develop the rules that reduce the resistance computation of composite TPF into resistance computation of simple functions. We illustrate their strength by efficiently computing the resistance in log-linear and payoff-based learning algorithms. They provide an efficient tool for characterizing SSSs of learning algorithms in finite games.