Markov $α$-Potential Games
This work addresses the analysis of equilibrium and optimization in Markov games, which is a foundational problem in multi-agent reinforcement learning and game theory, offering a novel theoretical framework with practical applications.
The authors introduced Markov α-potential games as a new framework for analyzing Markov games, proving that any finite-state, finite-action Markov game fits this framework and establishing the existence of an α-potential function, with optimizers corresponding to α-stationary Nash equilibria. They applied this framework to Markov congestion games and perturbed Markov team games, deriving explicit bounds for α and providing algorithms with Nash regret analysis supported by numerical experiments.
We propose a new framework of Markov $α$-potential games to study Markov games. We show that any Markov game with finite-state and finite-action is a Markov $α$-potential game, and establish the existence of an associated $α$-potential function. Any optimizer of an $α$-potential function is shown to be an $α$-stationary Nash equilibrium. We study two important classes of practically significant Markov games, Markov congestion games and the perturbed Markov team games, via the framework of Markov $α$-potential games, with explicit characterization of an upper bound for $α$ and its relation to game parameters. Additionally, we provide a semi-infinite linear programming based formulation to obtain an upper bound for $α$ for any Markov game. Furthermore, we study two equilibrium approximation algorithms, namely the projected gradient-ascent algorithm and the sequential maximum improvement algorithm, along with their Nash regret analysis, and corroborate the results with numerical experiments.