Multi-Agent Influence Diagrams for Representing and Solving Games

Game Theoretic and Decision Theoretic Agents

Volume

Papers from the 2001 AAAI Spring Symposium

Contents

Game theory provides a theoretical basis for defining rational behavior in multi-agent scenarios. However, the computational complexity of finding equilibria in large games has limited game theory’s practical applications. In this paper, we explore the application of structured probabilistic models to multi-agent scenarios. We define multi-agent influence diagrams (MAIDs), which represent games in a way that allows us to take advantage of independence relationships among variables. This representation allows us to define a notion of strategic relevance: D' is strategically relevant to D if, optimize the decision rule at D, the decision maker needs know the decision rule at D'. We provide a sound and complete graphical criterion for determining strategic relevance. We then show how strategic relevance, which is made explicit by the MAID structure, can be exploited in algorithms for computing equilibria to obtain exponential savings in certain classes of games.