Markov $\hat{I}\pm$-Potential Games

Abstract

We propose a new framework of Markov $\hat{I}\pm$-potential games to study Markov games. We show that any Markov game with finite-state and finite-action is a Markov $\hat{I}\pm$-potential game, and establish the existence of an associated $\hat{I}\pm$-potential function. Any optimizer of an $\hat{I}\pm$-potential function is shown to be an $\hat{I}\pm$-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 $\hat{I}\pm$-potential games, with explicit characterization of an upper bound for $\hat{I}\pm$ and its relation to game parameters. Additionally, we provide a semi-infinite linear programming based formulation to obtain an upper bound for $\hat{I}\pm$ 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.

33 pages, 5 figures