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.
This talk is part of the Erlangen AI Hub.