TUTORIAL: Computational Game Theory
Recently
there has been renewed interest in game theory in several research disciplines,
with its uses ranging from the modeling of evolution to the design of distributed
protocols. In the AI community, game theory is emerging as the dominant
formalism for studying strategic and cooperative interaction in multi-agent
systems.
Classical
work provides rich mathematical foundations and equilibrium concepts, but
relatively little in the way of computational and representational insights
that would allow game theory to scale up to large, complex systems. The rapidly
emerging field of computational game theory is addressing such algorithmic issues,
and this tutorial will provide a survey of developments. Special emphasis will
be placed on the interdisciplinary flavor of the field, drawing on methods and
insights from artificial intelligence, machine learning, theoretical computer
science, economics, biology, and many other fields.
Among
the topics to be covered are:
§
Examples of
Strategic Conflict as Matrix Games
§
Basics
Definitions of (Matrix) Game Theory
§
Notions of
Equilibrium: Overview
§
Definition and
Existence of Nash Equilibria
§
Computing Nash Equilibria for Matrix Games
§
Graphical Models
for Multiplayer Game Theory
§
Computing Nash Equilibria in Graphical Games
§
Probabilistic
Inference and Game Theory
§
Bayesian
Networks and Graphical Games
§
Sampling Methods
in Game Theory
§
Congestion Games
and Summarization Games
§
Social Network
Theory and Computational Game Theory
§
Interdependent Security
and Game Theory
§
Other
Equilibrium Concepts:
o
Correlated Equilibria,
o
Correlated Equilibria and Graphical Games,
o
Evolutionary
Stable Strategies,
o
Nash's
Bargaining Problem, Cooperative Equilibria
§
Learning in
Repeated Games:
o
Classical
Approaches,
o
Regret
Minimizing Algorithms,
o
Connections to
Machine Learning
§
Games with
State:
o
Connections to
Reinforcement Learning
§
Other Directions
and Conclusions
The
tutorial will be self-contained, assuming no prior knowledge of game theory.
Biosketch of the
presenter:
Michael
Kearns is Professor of Computer and Information Science the