My home page
Biography
Research
Publications
My group
Courses
Professional activities
FAQ
Personal
Papers

Daphne Koller Publications

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

by B. Blum, C.R. Shelton, and D. Koller
[newer version, 2006]

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

B. Blum, C.R. Shelton, and D. Koller (2003). "A Continuation Method for Nash Equilibria in Structured Games." Eighteenth International Joint Conference on Artificial Intelligence (IJCAI). pdf ps.gz

Bibtex citation

@inproceedings{Blum+al:IJCAI03,
  title = {A Continuation Method for Nash Equilibria in Structured Games},
  author = {B. Blum and C.R. Shelton and D. Koller},
  booktitle = {Eighteenth International Joint Conference on Artificial Intelligence (IJCAI)},
  month = {August},
  year = 2003, 
}

full list
Click to go to robotics Click to go to theory Click to go to CS Stanford Click to go to Stanford's Webpage
home | biography | research | papers | my group
courses | professional activities | FAQ | personal