Multi-agent influence diagrams for representing and solving games
成果类型：
Article; Proceedings Paper
署名作者：
Koller, D; Milch, B
署名单位：
Stanford University; University of California System; University of California Berkeley
刊物名称：
GAMES AND ECONOMIC BEHAVIOR
ISSN/ISSBN：
0899-8256
DOI：
10.1016/S0899-8256(02)00544-4
发表日期：
2003
页码：
181-221
关键词：
摘要：
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. (C) 2003 Elsevier Inc. All rights reserved.