Game Theory for Networks. 7th International EAI Conference, GameNets 2017 Knoxville, TN, USA, May 9, 2017, Proceedings

Research Article

Rules for Computing Resistance of Transitions of Learning Algorithms in Games

Download
203 downloads
  • @INPROCEEDINGS{10.1007/978-3-319-67540-4_9,
        author={Mohammed Ali and Pierre Coucheney and Marceau Coupechoux},
        title={Rules for Computing Resistance of Transitions of Learning Algorithms in Games},
        proceedings={Game Theory for Networks. 7th International EAI Conference, GameNets 2017 Knoxville, TN, USA, May 9, 2017, Proceedings},
        proceedings_a={GAMENETS},
        year={2017},
        month={9},
        keywords={Potential games Learning algorithms Log-linear learning Perturbed Markov Chains Resistance of transitions},
        doi={10.1007/978-3-319-67540-4_9}
    }
    
  • Mohammed Ali
    Pierre Coucheney
    Marceau Coupechoux
    Year: 2017
    Rules for Computing Resistance of Transitions of Learning Algorithms in Games
    GAMENETS
    Springer
    DOI: 10.1007/978-3-319-67540-4_9
Mohammed Ali1,*, Pierre Coucheney2,*, Marceau Coupechoux1,*
  • 1: LTCI, Telecom ParisTech, Université Paris-Saclay
  • 2: DAVID-Lab, UVSQ
*Contact email: mdshabbirali88@gmail.com, pierre.coucheney@uvsq.fr, marceau.coupechoux@telecom-paristech.fr

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.