Flows and Decompositions of Games: Harmonic and Potential Games

• 成果类型: Article
• 署名作者: Candogan, Ozan; Menache, Ishai; Ozdaglar, Asuman; Parrilo, Pablo A.
• 署名单位: Massachusetts Institute of Technology (MIT); Microsoft
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1110.0500
• 发表日期: 2011
• 页码: 474-503
• 关键词: Fictitious play; CONVERGENCE; REPRESENTATION

摘要

In this paper we introduce a novel flow representation for finite games in strategic form. This representation allows us to develop a canonical direct sum decomposition of an arbitrary game into three components, which we refer to as the potential, harmonic, and nonstrategic components. We analyze natural classes of games that are induced by this decomposition, and in particular, focus on games with no harmonic component and games with no potential component. We show that the first class corresponds to the well-known potential games. We refer to the second class of games as harmonic games, and demonstrate that this new class has interesting properties which contrast with properties of potential games. Exploiting the decomposition framework, we obtain explicit expressions for the projections of games onto the subspaces of potential and harmonic games. This enables an extension of the equilibrium properties of potential and harmonic games to nearby games.