Vidal's library
Title: Multi-Agent Influence Diagrams for Representing and Solving Games
Author: Daphne Koller and Brian Milch
Journal: Games and Economic Behavior
Volume: 45
Number: 1
Pages: 181--221
Year: 2003
DOI: 10.1016/S0899-8256(02)00544-4
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.

Cited by 66  -  Google Scholar

@Article{koller03a,
  author =	 {Daphne Koller and Brian Milch},
  title =	 {Multi-Agent Influence Diagrams for Representing and
                  Solving Games},
  journal =	 {Games and Economic Behavior},
  year =	 2003,
  volume =	 45,
  number =	 1,
  pages =	 {181--221},
  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.},
  keywords =     {multiagent bayesian},
  url = 	 {http://jmvidal.cse.sc.edu/library/koller03a.pdf},
  doi = 	 {10.1016/S0899-8256(02)00544-4},
  cluster = 	 {5926612126393763743},
}
Last modified: Wed Mar 9 10:16:02 EST 2011