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

Daphne Koller Publications

Multi-Agent Algorithms for Solving Graphical Games (2002)

by D. Vickrey and D. Koller


Abstract: Consider the problem of a group of agents trying to find a stable strategy profile for a joint interaction. A standard approach is to describe the situation as a single multi-player game and find an equilibrium strategy profile of that game. However, most algorithms for finding equilibria are computationally expensive; they are also centralized, requiring that all relevant payoff information be available to a single agent (or computer) who must determine the entire equilibrium profile. In this paper, we exploit two ideas to address these problems. We consider structured game representations, where the interaction between the agents is sparse, an assumption that holds in many real-world situations. We also consider the slightly relaxed task of finding an approximate equilibrium. We present two algorithms for finding approximate equilibria in these games, one based on a hill-climbing approach and one on constraint satisfaction. We show that these algorithms exploit the game structure to achieve faster computation. They are also inherently local, requiring only limited communication between directly interacting agents. They can thus be scaled to games involving large numbers of agents, provided the interaction between the agents is not too dense.

Download Information

D. Vickrey and D. Koller (2002). "Multi-Agent Algorithms for Solving Graphical Games." Proceedings of the Eighteenth National Conference on Artificial Intelligence (AAAI-02) (pp. 345-351). pdf ps.gz

Bibtex citation

@inproceedings{Vickrey+Koller:AAAI02,
  author =       "D. Vickrey and D. Koller",
  booktitle =    "Proceedings of the Eighteenth National Conference on
                 Artificial Intelligence (AAAI-02)",
  title =        "Multi-Agent Algorithms for Solving Graphical Games",
  pages =        "345--351",
  year =         "2002",
}

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