Computing Pure Nash Equilibria in Symmetric Action Graph Games
Abstract
We analyze the problem of computing pure Nash equilibria in action graph games (AGGs), which are a compact game-theoretic representation. While the problem is NP-complete in general, for certain classes of AGGs there exist polynomial time algorithms. We propose a dynamic-programming approach that constructs equilibria of the game from equilibria of restricted games played on subgraphs of the action graph. In particular, if the game is symmetric and the action graph has bounded treewidth, our algorithm determines the existence of pure Nash equilibrium in polynomial time.
Cite
Text
Jiang and Leyton-Brown. "Computing Pure Nash Equilibria in Symmetric Action Graph Games." AAAI Conference on Artificial Intelligence, 2007.Markdown
[Jiang and Leyton-Brown. "Computing Pure Nash Equilibria in Symmetric Action Graph Games." AAAI Conference on Artificial Intelligence, 2007.](https://mlanthology.org/aaai/2007/jiang2007aaai-computing/)BibTeX
@inproceedings{jiang2007aaai-computing,
title = {{Computing Pure Nash Equilibria in Symmetric Action Graph Games}},
author = {Jiang, Albert Xin and Leyton-Brown, Kevin},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2007},
pages = {79-85},
url = {https://mlanthology.org/aaai/2007/jiang2007aaai-computing/}
}