Markov Decision Processes in Artificial Intelligence

Chapter 8

Stochastic Games 1

8.1. Introduction

Game theory [AUM 02] is a formal model for studying the interactions among agents, assuming that such interactions can span from cooperation to conflict. Originally conceived as a mathematical tool for economic sciences, Game theory demonstrated its utility through the years in logic and in set theory [GRÄ 02, MAR 75], in biology and in evolution theory [SMI 02], in computer science [PAP 95, PAR 02, GIE 06], in conflict analysis [MYE 97], etc.

Interaction is the corner stone of the studies underlying game theory. Modeling interactions first requires extending the notion of game theory to dynamic games, generally used to represent the competition among processes that evolve over time. Stochastic transitions are then used to formalize uncertainty. Stochastic (or Markov) games are dynamic games with stochastic transitions. Nowadays they form a rich and mature mathematical theory, used in many applications like economy, biology and other domains with similar properties, such as evolution and populations, queues, telecommunications, model checking, etc. Recently, stochastic games have taken increasing importance in computer science, in particular through multi-agent systems for decision-making, automated planning and learning in environments where several autonomous agents operate [STO 00].

In this chapter, we consider stochastic games as the most generic multi-agent model. We present in detail several algorithms whose purpose is to solve ...