Flows and decompositions of games: harmonic and potential games
From MaRDI portal
Publication:2884285
DOI10.1287/MOOR.1110.0500zbMATH Open1239.91006arXiv1005.2405OpenAlexW1675187506MaRDI QIDQ2884285FDOQ2884285
Authors: Ozan Candogan, Ishai Menache, Asuman Ozdaglar, Pablo A. Parrilo 
Publication date: 24 May 2012
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Abstract: 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 study the structural and equilibrium properties of this new class of games. Intuitively, the potential component of a game captures interactions that can equivalently be represented as a common interest game, while the harmonic part represents the conflicts between the interests of the players. We make this intuition precise, by studying the properties of these two classes, and show that indeed they have quite distinct and remarkable characteristics. For instance, while finite potential games always have pure Nash equilibria, harmonic games generically never do. Moreover, we show that the nonstrategic component does not affect the equilibria of a game, but plays a fundamental role in their efficiency properties, thus decoupling the location of equilibria and their payoff-related properties. Exploiting the properties of 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 properties of potential and harmonic games to "nearby" games. We exemplify this point by showing that the set of approximate equilibria of an arbitrary game can be characterized through the equilibria of its projection onto the set of potential games.
Full work available at URL: https://arxiv.org/abs/1005.2405
Recommendations
Noncooperative games (91A10) Games involving graphs (91A43) Fundamental topics (basic mathematics, methodology; applicable to economics in general) (91B02) Hodge theory in global analysis (58A14) Spaces of games (91A70)
Cited In (57)
- Best-response dynamics in two-person random games with correlated payoffs
- Exploring multi-potential games in strategic form: a graph theoretic approach
- Towards multi‐agent reinforcement learning‐driven over‐the‐counter market simulations
- To catch a stag: identifying payoff- and risk-dominance effects in coordination games
- Game-theoretic multi-agent motion planning in a mixed environment
- On potential equations of finite symmetric games
- Verification of coset weighted potential game and its application to optimisation of multi-agent systems
- Mean curvature, threshold dynamics, and phase field theory on finite graphs
- Decentralized bandwidth control subject to two-layer constraints
- Ordinal potentials in smooth games
- On three-player potential games
- Agency, potential and contagion
- With potential games, which outcome is better?
- On potential equations of finite games
- Orthogonal decomposition of incomplete-profile finite game space
- Hodge decomposition and the Shapley value of a cooperative game
- Graphical potential games
- The geometry of synchronization problems and learning group actions
- A survey on cross-discipline of control and game
- The network HHD: quantifying cyclic competition in trait-performance models of tournaments
- Flow sharing and bankruptcy games
- The buck-passing game
- Algebraic verification of finite group-based potential games with vector payoffs
- An application of optimization theory to the study of equilibria for games: a survey
- Weighted and near weighted potential games with application to game theoretic control
- Analysis of crowdsourced sampling strategies for HodgeRank with sparse random graphs
- On best-response dynamics in potential games
- What Are Higher-Order Networks?
- Existence of equilibria in countable games: an algebraic approach
- Robustness of dynamics in games: a contraction mapping decomposition approach
- Pure Nash equilibria and best-response dynamics in random games
- Similarity Suppresses Cyclicity: Why Similar Competitors Form Hierarchies
- Title not available (Why is that?)
- Games, graphs and Kirchhoff laws
- Fashion and homophily
- Decompositions of finite games: from weighted inner product to standard inner product
- On skew-symmetric games
- Dynamic potential games: the discrete-time stochastic case
- On basis and pure Nash equilibrium of finite pure harmonic games
- On coset weighted potential game
- A comprehensive survey on STP approach to finite games
- A survey on decomposition of finite strategic-form games
- Recent advances in optimization and game theoretic control for networked systems
- Strategic decompositions of normal form games: zero-sum games and potential games
- Classification by decomposition: a novel approach to classification of symmetric \(2\times 2\) games
- Directed graphical structure, Nash equilibrium, and potential games
- From Boolean game to potential game
- Regular potential games
- Zeroth-order feedback optimization for cooperative multi-agent systems
- Hodge Laplacians on graphs
- Incomplete-profile potential games
- Evolutionary potential games on lattices
- Decomposition of games: some strategic considerations
- Modeling, analysis, and dynamics of Bayesian games via matrix-based method
- Evolution of social networks
- Stackelberg-Nash equilibrium and quasi harmonic games
- Dynamics in near-potential games
This page was built for publication: Flows and decompositions of games: harmonic and potential games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2884285)
