Flows and Decompositions of Games: Harmonic and Potential Games

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.

References in corpus (1)

• Statistical ranking and combinatorial Hodge theory

Cited by in corpus (37)

• What are higher-order networks?
• Game-Theoretic Multiagent Reinforcement Learning
• The Mechanics of n-Player Differentiable Games
• Mean curvature, threshold dynamics, and phase field theory on finite graphs
• Dynamics in Near-Potential Games
• Evolutionary potential games on lattices
• Open-ended Learning in Symmetric Zero-sum Games
• Simplicial Convolutional Filters
• Hodge Laplacians on graphs
• Hodge decomposition and the Shapley value of a cooperative game
• Existence of equilibria in countable games: an algebraic approach
• Potential Game-Based Non-Myopic Sensor Network Planning for Multi-Target Tracking
• Learning in Nonzero-Sum Stochastic Games with Potentials
• Diverse Auto-Curriculum is Critical for Successful Real-World Multiagent Learning Systems
• Analysis of Crowdsourced Sampling Strategies for HodgeRank with Sparse Random Graphs
• The Geometry of Synchronization Problems and Learning Group Actions
• The graph structure of two-player games
• A Cheeger Inequality for the Graph Connection Laplacian
• Pure Nash Equilibria and Best-Response Dynamics in Random Games
• Strategic Decompositions of Normal Form Games: Zero-sum Games and Potential Games
• Chaos of Learning Beyond Zero-sum and Coordination via Game Decompositions
• Equilibrium Characterization for Data Acquisition Games
• Matrix Expression of Bayesian Game
• Consensus Multiplicative Weights Update: Learning to Learn using Projector-based Game Signatures
• Graphical Games and Decomposition
• On Best-Response Dynamics in Potential Games
• A Comprehensive Survey on STP Approach to Finite Games
• A Note On Orthogonal Decomposition of Finite Games
• Decentralized Fictitious Play in Near-Potential Games with Time-Varying Communication Networks
• Axiomatic and Probabilistic Foundations for the Hodge-Theoretic Shapley Value
• Fast Adaptive Algorithm for Robust Evaluation of Quality of Experience
• On Coset Weighted Potential Game
• Linear Representation of Symmetric Games
• On Potential Equations of Finite Games
• Parsimonious Mixed-Effects HodgeRank for Crowdsourced Preference Aggregation
• Efficient sensor network planning method using approximate potential game
• Polynomial representation for orthogonal projections onto subspaces of finite games