Higher-Order Uncoupled Learning Dynamics and Nash Equilibrium
For game theorists and multi-agent learning researchers, this work provides foundational insights into the learnability of mixed-strategy Nash equilibria using higher-order dynamics, though results are largely theoretical and incremental.
The paper proves that for any finite game with an isolated completely mixed-strategy Nash equilibrium, there exist higher-order uncoupled learning dynamics that locally converge to it, but also shows that no single dynamics can learn all such equilibria. It introduces the Asymptotic Best Response property and studies its compatibility with Nash equilibria.
We study learnability of mixed-strategy Nash Equilibrium (NE) in general finite games using higher-order replicator dynamics as well as classes of higher-order uncoupled heterogeneous dynamics. In higher-order uncoupled learning dynamics, players have no access to utilities of opponents (uncoupled) but are allowed to use auxiliary states to further process information (higher-order). We establish a link between uncoupled learning and feedback stabilization with decentralized control. Using this association, we show that for any finite game with an isolated completely mixed-strategy NE, there exist higher-order uncoupled learning dynamics that lead (locally) to that NE. We further establish the lack of universality of learning dynamics by linking learning to the control theoretic concept of simultaneous stabilization. We construct two games such that any higher-order dynamics that learn the completely mixed-strategy NE of one of these games can never learn the completely mixed-strategy NE of the other. Next, motivated by imposing natural restrictions on allowable learning dynamics, we introduce the Asymptotic Best Response (ABR) property. Dynamics with the ABR property asymptotically learn a best response in environments that are asymptotically stationary. We show that the ABR property relates to an internal stability condition on higher-order learning dynamics. We provide conditions under which NE are compatible with the ABR property. Finally, we address learnability of mixed-strategy NE in the bandit setting using a bandit version of higher-order replicator dynamics.