11.30 a.m.
Solution Concepts and Algorithms for Infinite Multiplayer Games
Erich Graedel
RWTH Aachen University, Germany.
05-12-08

---

Abstract

We survey and discuss several solution concepts for infinite turn-based multiplayer games with qualitative (i.e. win-lose) objectives of the players. These games generalise in a natural way the common model of games in verification which are two-player, zero-sum games with omega-regular winning conditions. The generalisation is in two directions: games may have more than two players, and the objectives of the players need not be completely antagonistic.

The notion of a Nash equilibrium is the classical solution concept in game theory. However, for games that extend over time, in particular for games of infinite duration, Nash equilibria are not always satisfactory as a notion of rational behaviour. We discuss refined notions of equilibria and present criteria for their existence and algorithms to find them. We also discuss other solution concepts from game theory such as iterated elimination of dominated strategies.