Department of Computer Science and
RWTH Aachen
2pm Wednesday 19th October 2005
Room 2511, JCMB, King's Buildings
We study infinite games played by arbitrarily many players on a directed graph. Equilibrium states capture rational behaviour in these games. Besides the well-known notion of a Nash equilibrium, we deal with the less well-known notion of a subgame perfect equilibrium. We argue that the latter is more appropriate for the kind of games we discuss. We show the existence of a subgame perfect equilibrium in any game where each player has a winning condition of Borel type. For games played on a finite graph where each player has a parity winning condition we show the existence of a subgame perfect equilibrium in finite-state strategies. By a suitable notion of game reduction, this result can be extended to games with arbitrary omega-regular winning conditions. In the last part of the talk, we develop an algorithm for computing a maximal finite-state subgame perfect equilibrium of a game with omega-regular winning conditions and analyse the complexity of the corresponding decision problem.