Tractable Algorithms for Approximate Nash Equilibria in Generalized Graphical Games with Tree Structure
Abstract
We provide the first fully polynomial time approximation scheme (FPTAS) for computing an approximate mixed-strategy Nash equilibrium in graphical multi-hypermatrix games (GMhGs), which are generalizations of normal-form games, graphical games, graphical polymatrix games, and hypergraphical games. Computing an exact mixed-strategy Nash equilibria in graphical polymatrix games is PPAD complete and thus generally believed to be intractable. In contrast, to the best of our knowledge, we are the first to establish an FPTAS for tree polymatrix games as well as tree graphical games when the number of actions is bounded by a constant. As a corollary, we give a quasi-polynomial time approximation scheme (quasi-PTAS) when the number of actions is bounded by a logarithm of the number of players.
Cite
Text
Ortiz and Irfan. "Tractable Algorithms for Approximate Nash Equilibria in Generalized Graphical Games with Tree Structure." AAAI Conference on Artificial Intelligence, 2017. doi:10.1609/AAAI.V31I1.10602Markdown
[Ortiz and Irfan. "Tractable Algorithms for Approximate Nash Equilibria in Generalized Graphical Games with Tree Structure." AAAI Conference on Artificial Intelligence, 2017.](https://mlanthology.org/aaai/2017/ortiz2017aaai-tractable/) doi:10.1609/AAAI.V31I1.10602BibTeX
@inproceedings{ortiz2017aaai-tractable,
title = {{Tractable Algorithms for Approximate Nash Equilibria in Generalized Graphical Games with Tree Structure}},
author = {Ortiz, Luis E. and Irfan, Mohammad Tanvir},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2017},
pages = {635-641},
doi = {10.1609/AAAI.V31I1.10602},
url = {https://mlanthology.org/aaai/2017/ortiz2017aaai-tractable/}
}