Dynamics in Near-Potential Games
Presenter
October 29, 2013
Keywords:
- Dynamics in Game
MSC:
- 91-XX
Abstract
Potential games are a special class of games that allow for tractable dynamic analysis. Intuitively, games that are "close" to a potential game should share similar properties. In this talk, we formalize and develop this idea by quantifying how the dynamical features of potential games extend to near-potential games. Towards this goal, we discuss a novel flow representation of arbitrary finite games as a canonical direct sum decomposition into three components, which we refer to as the potential, harmonic and nonstrategic components.
Our results show that the limiting behavior of better-response and best-response dynamics can be characterized in terms of the approximate equilibrium set of a close potential game. Moreover, the size of this set is proportional to a closeness measure between the original game and the potential game. Analogous results are also shown to hold for other dynamical processes, such as logit response. Our approach presents a systematic framework for studying convergence behavior of adaptive learning dynamics in finite strategic form games.
Joint work with Ozan Candogan (Duke) and Asu Ozdaglar (MIT).