Personal tools
You are here: Home Events Abstract Archives 2005 Rational Behaviour and Strategy Construction in Infinite Multiplayer Games

Rational Behaviour and Strategy Construction in Infinite Multiplayer Games

Michael Ummels 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.

Document Actions