Computing Pure Nash Equilibria in Symmetric Action Graph Games

Albert Xin Jiang, Kevin Leyton-Brown

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.

Subjects: 7.1 Multi-Agent Systems; 9.2 Computational Complexity

Submitted: Apr 25, 2007

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.