2024/05/23 by Yuma Fujimoto, Fujimoto, Yuma, Kaito Ariu +3
Engineering · #Chaotic Dynamics (nlin.CD) #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Guidance and Control Systems #Multiagent Systems (cs.MA) #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.2405.14546
openalex publication_date 2024/05/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This study examines the global behavior of dynamics in learning in games between two players, X and Y. We consider the simplest situation for memory asymmetry between two players: X memorizes the other Y's previous action and uses reactive strategies, while Y has no memory. Although this memory complicates the learning dynamics, we discover two novel quantities that characterize the global behavior of such complex dynamics. One is an extended Kullback-Leibler divergence from the Nash equilibrium, a well-known conserved quantity from previous studies. The other is a family of Lyapunov functions of X's reactive strategy. These two quantities capture the global behavior in which X's strategy becomes more exploitative, and the exploited Y's strategy converges to the Nash equilibrium. Indeed, we theoretically prove that Y's strategy globally converges to the Nash equilibrium in the simplest game equipped with an equilibrium in the interior of strategy spaces. Furthermore, our experiments also suggest that this global convergence is universal for more advanced zero-sum games than the simplest game. This study provides a novel characterization of the global behavior of learning in games through a couple of indicators.