Beyond Theorems: A Counterexample to Potential Markov Game Criteria
<|reference_start|>Beyond Theorems: A Counterexample to Potential Markov Game Criteria: There are only limited classes of multi-player stochastic games in which independent learning is guaranteed to converge to a Nash equilibrium. Markov potential games are a key example of such classes. Prior work has outlined sets of sufficient conditions for a stochastic game to qualify as a Markov potential game. However, these conditions often impose strict limitations on the game's structure and tend to be challenging to verify. To address these limitations, Mguni et al. [12] introduce a relaxed notion of Markov potential games and offer an alternative set of necessary conditions for categorizing stochastic games as potential games. Under these conditions, the authors claim that a deterministic Nash equilibrium can be computed efficiently by solving a dual Markov decision process. In this paper, we offer evidence refuting this claim by presenting a counterexample.<|reference_end|>
@article{fardno2024beyond,
    title={Beyond Theorems: A Counterexample to Potential Markov Game Criteria},
    author={Fatemeh Fardno and Seyed Majid Zahedi},
    journal={arXiv preprint arXiv:2405.08206},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.08206},
    primaryClass={cs.GT cs.MA}
}