TY - JOUR
T1 - Path to Stochastic Stability: Comparative Analysis of Stochastic Learning Dynamics in Games
AU - Jaleel, Hassan
AU - Shamma, Jeff S.
N1 - KAUST Repository Item: Exported on 2020-11-24
PY - 2020
Y1 - 2020
N2 - Stochastic stability is an important solution concept for stochastic learning dynamics in games. However, a limitation of this solution concept is its inability to distinguish between different learning rules that lead to the same steady-state behavior. We identify this limitation and develop a framework for the comparative analysis of the transient behavior of stochastic learning dynamics. We present the framework in the context of two learning dynamics: Log-Linear Learning (LLL) and Metropolis Learning (ML). Although both of these dynamics lead to the same steady-state behavior, they correspond to different behavioral models for decision making. In this work, we propose multiple criteria to analyze and quantify the differences in the short and medium-run behaviors of stochastic learning dynamics. We derive upper bounds on the expected hitting time of the set of Nash equilibria for both LLL and ML. For the medium to long-run behavior, we identify a set of tools from the theory of perturbed Markov chains that result in a hierarchical decomposition of the state space into collections of states called cycles.
AB - Stochastic stability is an important solution concept for stochastic learning dynamics in games. However, a limitation of this solution concept is its inability to distinguish between different learning rules that lead to the same steady-state behavior. We identify this limitation and develop a framework for the comparative analysis of the transient behavior of stochastic learning dynamics. We present the framework in the context of two learning dynamics: Log-Linear Learning (LLL) and Metropolis Learning (ML). Although both of these dynamics lead to the same steady-state behavior, they correspond to different behavioral models for decision making. In this work, we propose multiple criteria to analyze and quantify the differences in the short and medium-run behaviors of stochastic learning dynamics. We derive upper bounds on the expected hitting time of the set of Nash equilibria for both LLL and ML. For the medium to long-run behavior, we identify a set of tools from the theory of perturbed Markov chains that result in a hierarchical decomposition of the state space into collections of states called cycles.
UR - http://hdl.handle.net/10754/627530
UR - https://ieeexplore.ieee.org/document/9265240/
U2 - 10.1109/TAC.2020.3039485
DO - 10.1109/TAC.2020.3039485
M3 - Article
SN - 2334-3303
SP - 1
EP - 1
JO - IEEE Transactions on Automatic Control
JF - IEEE Transactions on Automatic Control
ER -