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

Daphne Koller Publications

Multi-Agent Influence Diagrams for Representing and Solving Games (2003)

by D. Koller and B. Milch
[older version, 2001]

Abstract: The traditional representations of games using the extensive form or the strategic form obscure much of the structure of real-world games. In this paper, we propose a graphical representation for noncooperative games - multi-agent influence diagrams (MAIDs). The basic elements in the MAID representation are variables, allowing an explicit representation of dependence, or relevance, relationships among variables. We define a decision variable D' as strategically relevant to D if, to optimize the decision rule at D, the decision maker needs to consider the decision rule at D'. We provide a sound and complete graphical criterion for determining strategic relevance. We then show how strategic relevance can be used to decompose large games into a set of interacting smaller games, which can be solved in sequence. We show that this decomposition can lead to substantial savings in the computational cost of finding Nash equilibria in these games.

Download Information

D. Koller and B. Milch (2003). "Multi-Agent Influence Diagrams for Representing and Solving Games." Games and Economic Behavior, 45(1), 181-221. Full version of paper in IJCAI '03. pdf ps.gz

Bibtex citation

@article{Koller+Milch:GEB03,
  author =       "D. Koller and B. Milch",
  journal =    "Games and Economic Behavior",
  title =        "Multi-Agent Influence Diagrams for Representing and
                 Solving Games",
  volume = 45,
  number = 1,
  pages =        "181--221",
  year =         "2003",
  note = {Full version of paper in IJCAI '03},
}

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