Computer Science – Computer Science and Game Theory
Scientific paper
2011-09-29
Journal Of Artificial Intelligence Research, Volume 25, pages 457-502, 2006
Computer Science
Computer Science and Game Theory
Scientific paper
10.1613/jair.1947
Structured game representations have recently attracted interest as models for multi-agent artificial intelligence scenarios, with rational behavior most commonly characterized by Nash equilibria. This paper presents efficient, exact algorithms for computing Nash equilibria in structured game representations, including both graphical games and multi-agent influence diagrams (MAIDs). The algorithms are derived from a continuation method for normal-form and extensive-form games due to Govindan and Wilson; they follow a trajectory through a space of perturbed games and their equilibria, exploiting game structure through fast computation of the Jacobian of the payoff function. They are theoretically guaranteed to find at least one equilibrium of the game, and may find more. Our approach provides the first efficient algorithm for computing exact equilibria in graphical games with arbitrary topology, and the first algorithm to exploit fine-grained structural properties of MAIDs. Experimental results are presented demonstrating the effectiveness of the algorithms and comparing them to predecessors. The running time of the graphical game algorithm is similar to, and often better than, the running time of previous approximate algorithms. The algorithm for MAIDs can effectively solve games that are much larger than those solvable by previous methods.
Blum Ben
Koller Daniel
Shelton Christian R.
No associations
LandOfFree
A Continuation Method for Nash Equilibria in Structured Games does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Continuation Method for Nash Equilibria in Structured Games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Continuation Method for Nash Equilibria in Structured Games will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-152954