Computing Nash Equilibria of ActionGraph Games
Navin Bhat, Kevin LeytonBrown
Abstract:
Actiongraph games (AGGs) are a fully expressive game representation which can compactly express both strict and contextspecific independence between players' utility functions. Actions are represented as nodes in a graph G, and the payoff to an agent who chose the action s depends only on the numbers of other agents who chose actions connected to s. We present algorithms for computing both symmetric and arbitrary equilibria of AGGs using a continuation method. We analyze the worstcase cost of computing the Jacobian of the payoff function, the exponentialtime bottleneck step, and in all cases achieve exponential speedup. When the indegree of G is bounded by a constant and the game is symmetric, the Jacobian can be computed in polynomial time.
Keywords: null
Pages: 3542
PS Link:
PDF Link: /papers/04/p35bhat.pdf
BibTex:
@INPROCEEDINGS{Bhat04,
AUTHOR = "Navin Bhat
and Kevin LeytonBrown",
TITLE = "Computing Nash Equilibria of ActionGraph Games",
BOOKTITLE = "Proceedings of the Twentieth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI04)",
PUBLISHER = "AUAI Press",
ADDRESS = "Arlington, Virginia",
YEAR = "2004",
PAGES = "3542"
}

