Computing Pure Nash Equilibria in Symmetric Action Graph Games

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