2023/05/21 by Xin Guo, Guo, Xin, Xinyu Li +7 · 1 citation
Decision Sciences · #91A10 #91A14 #91A15 #91A50 #91A68 #Artificial Intelligence (cs.AI) #Computer Science and Game Theory (cs.GT) #Dynamical Systems (math.DS) #FOS: Computer and information sciences #FOS: Electrical engineering #FOS: Mathematics #Game Theory and Applications #Multiagent Systems (cs.MA) #Systems and Control (eess.SY) #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.2305.12553
openalex publication_date 2023/05/21 · openalex created_date 2023/05/24 · openalex updated_date 2026/07/29
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.