Markov $α$-Potential Games
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916668079341568 |
|---|---|
| author | Guo, Xin Li, Xinyu Maheshwari, Chinmay Sastry, Shankar Wu, Manxi |
| author_facet | Guo, Xin Li, Xinyu Maheshwari, Chinmay Sastry, Shankar Wu, Manxi |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2305_12553 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Markov $α$-Potential Games Guo, Xin Li, Xinyu Maheshwari, Chinmay Sastry, Shankar Wu, Manxi Computer Science and Game Theory Artificial Intelligence Multiagent Systems Systems and Control Dynamical Systems 91A68, 91A50, 91A15, 91A14, 91A10 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. |
| title | Markov $α$-Potential Games |
| topic | Computer Science and Game Theory Artificial Intelligence Multiagent Systems Systems and Control Dynamical Systems 91A68, 91A50, 91A15, 91A14, 91A10 |
| url | https://arxiv.org/abs/2305.12553 |