Recent work at the interface between artificial intelligence and game      
theory has provided natural, compact representations for describing
multi-agent interaction under uncertainty. These representations use
graphical networks, and  make explicit the dependency relationships
that hold between agents' decisions, utilities and the chance
variables in the environment, which may be then exploited for
efficient inference.  Graphical networks facilitate the decomposition
of complex multi-agent decision-making problems into smaller,
interacting constituents which can be analyzed independently in a way
that preserves the global structure of the problem. Applications using
graphical networks for decision-making abound, and include vehicle
tracking, military combat simulations and human-computer negotiation.

This half-day tutorial will survey these new formalisms, focusing on
their expressiveness as knowledge representation languages, and the
challenges they pose to inference algorithms. It will show how to
construct networks that adequately capture the relationship between
agents' beliefs about each other's strategies and the environment.  It
will present a variety of techniques that exploit the network
structure in order to efficiently extract equilibrium strategies for
agents that satisfy various conditions.  Throughout the tutorial, both
theory and algorithms will be exemplified using to systems: the IBAL programming
language, a probabilistic language that is generally applicable to
graphical formalisms; and Colored Trails, a test-bed for investigating
decision-making in groups comprising people, computers and a mix of these two.

The tutorial presupposes a basic understanding of probability theory,
but is self contained in all other aspects.  It does not assume
knowledge of  game theoretic concepts, nor  previous exposure
to multi-agent systems research, or probabilistic reasoning.   

Single-agent decision-making
    Decision Theory
        Strategies, preferences and utilities
        Uncertainty and the maximum expected utility principle
        Making sequential decisions
        Decision trees
    Bayesian networks
        Syntax and semantics
        Independence and d-separation
    Influence Diagrams (ID)
        Syntax and semantics
        Relationship with Bayesian networks
        Converting IDs to decision trees
        Computing expected utilities in IDs
        Solving IDs
Multi-agent decision-making
    Game Theory
        Extensive and normal form representations
        Mixed strategies
        Nash equilibrium
    Multi-Agent Influence Diagrams (MAID)
        Strategic relevance and s-separation
        Computing expected utilities in MAIDs
        Solving MAIDs
    Reasoning patterns
        Well distinguishing (WD) strategies
        Relationship with Nash equilibrium strategies
        Completeness result
    Graphical games
        Syntax and semantics
        Representation as Constraint Satisfaction Problem
    Local effect games
    Network of Influence Diagrams (NID)
        Syntax and semantics
        Learning in NIDs

        
Much attention has been given to game theoretic formalisms in the
AAMAS community. However, the inherent assumptions of these formalisms
have made it difficult to use them in complex domains, such as the
trading agent competition, or human-computer negotiation.  To date,
AI researchers have not fully exploited the work in the probabilistic
reasoning community that has enabled to represent large multi-agent
problems compactly and efficiently.  This tutorial will make these
ideas more accessible to the AAMAS community, making their relevance
clear by including examples and applications.

 
Avi Pfeffer is Associate Professor at Computer Science at Harvard
University.  His research is directed towards achieving rational
behavior in intelligent systems, based on the principles of
probability theory, decision theory, Bayesian learning and game
theory.  He received his PhD in 2000 from Stanford University, where
his dissertation on probabilistic reasoning received the Arthur Samuel
Thesis Award.  Prof. Pfeffer has published technical papers on
probabilistic reasoning, strategic reasoning, agent modeling, temporal
reasoning, and database systems.  He was awarded the NSF Career Award
in 2001 for work on strategic reasoning, and the Alfred P. Sloan
Foundation Research Fellowship in 2002.



Ya'akov (Kobi) Gal is a post-doctoral researcher at the MIT
Artificial Intelligence lab and at Harvard University's School of
Engineering and Applied Sciences. His research focuses on
representations and algorithms for reasoning about agents' beliefs and
decision-making processes.  He is a two-time recipient of Harvard
University's Derek Bok award for excellence in teaching, as well as
the School of Engineering and Applied Science's outstanding teacher
award.  Gal has served as a teaching fellow in five courses at Harvard
University, including advanced undergraduate and graduate level AI
courses.  He has published five conference and two journal papers on graphical
formalisms for representing agents' decision-making processes.