  This paper proposes a new framework of Markov $\alpha$-potential games to
study Markov games. In this new framework, Markov games are shown to be Markov
$\alpha$-potential games, and the existence of an associated $\alpha$-potential
function is established. Any optimizer of an $\alpha$-potential function is
shown to be an $\alpha$-stationary NE. Two important classes of practically
significant Markov games, Markov congestion games and the perturbed Markov team
games, are studied via this framework of Markov $\alpha$-potential games, with
explicit characterization of an upper bound for $\alpha$ and its relation to
game parameters. Additionally, a semi-infinite linear programming based
formulation is presented to obtain an upper bound for $\alpha$ for any Markov
game. Furthermore, two equilibrium approximation algorithms, namely the
projected gradient-ascent algorithm and the sequential maximum improvement
algorithm, are presented along with their Nash regret analysis, and
corroborated by numerical experiments.
