UCR

Computer Science and Engineering



Christian R. Shelton, Professor

A Continuation Method for Nash Equilibria in Structured Games (2003)

by Ben Blum, Christian R. Shelton, and Daphne Koller


Abstract: We describe 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 the space of perturbed games and their equilibria. Our algorithms exploit game structure through fast computation of the Jacobian of the game's payoff function. They are guaranteed to find at least one equilibrium of the game and may find more. Our approach provides the first exact algorithm for computing an exact equilibrium in graphical games with arbitrary topology, and the first algorithm to exploit fine-grain structural properties of MAIDs. We present experimental results for our algorithms. The running time for our graphical game algorithm is similar to, and often better than, the running time of previous approximate algorithms. Our algorithm for MAIDs can effectively solve games that are much larger than those that could be solved using previous methods.

Download Information

Ben Blum, Christian R. Shelton, and Daphne Koller (2003). "A Continuation Method for Nash Equilibria in Structured Games." Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence (pp. 757-764). pdf   ps ps.gz    

Bibtex citation

@inproceedings{BluSheKol03,
   author = "Ben Blum and Christian R. Shelton and Daphne Koller",
   title = "A Continuation Method for {N}ash Equilibria in Structured Games",
   booktitle = "Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence",
   booktitleabbr = "{IJCAI}",
   year = 2003,
   pages = "757-764",
}

More Information

Address

University of California, Riverside
Chung Hall, room 327
Riverside, CA 92521
Tel: (951) 827-2554
E-mail: cshelton@cs.ucr.edu

 


Other Links