Dynamics in Near-Potential Games

Tuesday, October 29, 2013 - 9:00am - 9:50am
Keller 3-180
Pablo Parrilo (Massachusetts Institute of Technology)
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).
MSC Code: