We describe a new algorithm for computing a Nash equilibrium in graphical games, a compact representation for multi-agent systems that we introduced in previous work. The algorithm is the first to compute equilibria both efficiently and exactly for a nontrivial class of graphical games. 1 Introduction Seeking to replicate the representational and computational benefits that graphical models have provided to probabilistic inference, several recent works have introduced graph-theoretic frameworks for the study of multi-agent systems (La Mura 2000; Koller and Milch 2001; Kearns et al. 2001). In the simplest of these formalisms, each vertex represents a single agent, and the edges represent pairwise interaction between agents. As with many familiar network models, the macroscopic behavior of a large system is thus implicitly described by its local interactions, and the computational challenge is to extract the global states of interest. Classical game theory is typically used to model multi-agent interactions, and the global states of interest are thus the so-called Nash equilibria, in which no agent has a unilateral incentive to deviate.

We present a principled and efficient planning algorithm for cooperative multiagent dynamic systems. A striking feature of our method is that the coordination and communication between the agents is not imposed, but derived directly from the system dynamics and function approximation architecture. We view the entire multiagent system as a single, large Markov decision process (MDP), which we assume can be represented in a factored way using a dynamic Bayesian network (DBN). The action space of the resulting MDP is the joint action space of the entire set of agents. Our approach is based on the use of factored linear value functions as an approximation to the joint value function.

We propose a new classification for multi-agent learning algorithms, with each league of players characterized by both their possible strategies and possible beliefs. Using this classification, we review the optimality of existing algorithms, including the case of interleague play. We propose an incremental improvement to the existing algorithms that seems to achieve average payoffs that are at least the Nash equilibrium payoffs in the longrun against fair opponents.

We present a principled and efficient planning algorithm for cooperative multiagent dynamicsystems. A striking feature of our method is that the coordination and communication between the agents is not imposed, but derived directly from the system dynamics and function approximation architecture. We view the entire multiagentsystem as a single, large Markov decision process (MDP), which we assume can be represented in a factored way using a dynamic Bayesian network (DBN).The action space of the resulting MDP is the joint action space of the entire set of agents. Our approach is based on the use of factored linear value functions as an approximation to the joint value function. This factorization of the value function allows the agents to coordinate their actions at runtime using a natural message passing scheme. We provide a simple and efficient method for computing such an approximate value function by solving a single linear program, whosesize is determined by the interaction between the value function structure and the DBN. We thereby avoid the exponential blowup in the state and action space. We show that our approach compares favorably with approaches based on reward sharing. We also show that our algorithm is an efficient alternative tomore complicated algorithms even in the single agent case.

What do we expect a successful learner to do?

The algorithm is the first to compute equilibria both efficiently and exactly for a nontrivial class of graphical games. 1 Introduction Seeking to replicate the representational and computational benefits that graphical modelshave provided to probabilistic inference, several recent works have introduced graph-theoretic frameworks for the study of multi-agent systems (LaMura 2000; Koller and Milch 2001; Kearns et al. 2001). In the simplest of these formalisms, each vertex represents a single agent, and the edges represent pairwise interaction between agents. As with many familiar network models, the macroscopic behavior of a large system is thus implicitly described by its local interactions, andthe computational challenge is to extract the global states of interest. Classical game theory is typically used to model multi-agent interactions, and the global states of interest are thus the so-called Nash equilibria, in which no agent has a unilateral incentive to deviate. In a recent paper (Kearns et al. 2001), we introduced such a graphical formalism for multi-agent game theory, and provided two algorithms for computing Nash equilibria whenthe underlying graph is a tree (or is sufficiently sparse).

The Association for the Advancement of Artificial Intelligence (AAAI) presented the AAAI-02 Workshop Program on Sunday and Monday, 28-29 July 2002 at the Shaw Convention Center in Edmonton, Alberta, Canada. The AAAI-02 workshop program included 18 workshops covering a wide range of topics in AI. The workshops were Agent-Based Technologies for B2B Electronic-Commerce; Automation as a Caregiver: The Role of Intelligent Technology in Elder Care; Autonomy, Delegation, and Control: From Interagent to Groups; Coalition Formation in Dynamic Multiagent Environments; Cognitive Robotics; Game-Theoretic and Decision-Theoretic Agents; Intelligent Service Integration; Intelligent Situation-Aware Media and Presentations; Meaning Negotiation; Multiagent Modeling and Simulation of Economic Systems; Ontologies and the Semantic Web; Planning with and for Multiagent Systems; Preferences in AI and CP: Symbolic Approaches; Probabilistic Approaches in Search; Real-Time Decision Support and Diagnosis Systems; Semantic Web Meets Language Resources; and Spatial and Temporal Reasoning.

The Association for the Advancement of Artificial Intelligence (AAAI) presented the AAAI-02 Workshop Program on Sunday and Monday, 28-29 July 2002 at the Shaw Convention Center in Edmonton, Alberta, Canada. The AAAI-02 workshop program included 18 workshops covering a wide range of topics in AI. The workshops were Agent-Based Technologies for B2B Electronic-Commerce; Automation as a Caregiver: The Role of Intelligent Technology in Elder Care; Autonomy, Delegation, and Control: From Interagent to Groups; Coalition Formation in Dynamic Multiagent Environments; Cognitive Robotics; Game-Theoretic and Decision-Theoretic Agents; Intelligent Service Integration; Intelligent Situation-Aware Media and Presentations; Meaning Negotiation; Multiagent Modeling and Simulation of Economic Systems; Ontologies and the Semantic Web; Planning with and for Multiagent Systems; Preferences in AI and CP: Symbolic Approaches; Probabilistic Approaches in Search; Real-Time Decision Support and Diagnosis Systems; Semantic Web Meets Language Resources; and Spatial and Temporal Reasoning.

Send applications and inquiries to May Cheh; National Library of Medicine, 8600 Rockville Pike, Mail Stop 54, Bethesda, MD 20894-6075; Email: cheh@nlm.nih.gov

The Association for the Advancement of Artificial Intelligence, in cooperation with Stanford University's Department of Computer Science, presented the 2002 Spring Symposium Series, held Monday through Wednesday, 25 to 27 March 2002, at Stanford University. The nine symposia were entitled (1) Acquiring (and Using) Linguistic (and World) Knowledge for Information Access; (2) Artificial Intelligence and Interactive Entertainment; (3) Collaborative Learning Agents; (4) Information Refinement and Revision for Decision Making: Modeling for Diagnostics, Prognostics, and Prediction; (5) Intelligent Distributed and Embedded Systems; (6) Logic-Based Program Synthesis: State of the Art and Future Trends; (7) Mining Answers from Texts and Knowledge Bases; (8) Safe Learning Agents; and (9) Sketch Understanding.