Dynamics in near-potential games

• 成果类型: Article
• 署名作者: Candogan, Ozan; Ozdaglar, Asuman; Parrilo, Pablo A.
• 署名单位: Massachusetts Institute of Technology (MIT)
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2013.07.001
• 发表日期: 2013
• 页码: 66-90
• 关键词: Dynamics in games; Near-potential games; best response dynamics; Logit response dynamics; Fictitious play

摘要

We consider discrete-time learning dynamics in finite strategic form games, and show that games that are close to a potential game inherit many of the dynamical properties of potential games. We first study the evolution of the sequence of pure strategy profiles under better/best response dynamics. We show that this sequence converges to a (pure) approximate equilibrium set whose size is a function of the distance to a given nearby potential game. We then focus on logit response dynamics, and provide a characterization of the limiting outcome in terms of the distance of the game to a given potential game and the corresponding potential function. Finally, we turn attention to fictitious play, and establish that in near-potential games the sequence of empirical frequencies of player actions converges to a neighborhood of (mixed) equilibria, where the size of the neighborhood increases according to the distance to the set of potential games. (C) 2013 Elsevier Inc. All rights reserved.