
Rational Behaviour and Strategy Construction in Infinite Multiplayer GamesMichael 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 wellknown notion of a Nash equilibrium, we deal with the less wellknown 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 finitestate strategies. By a suitable notion of game reduction, this result can be extended to games with arbitrary omegaregular winning conditions. In the last part of the talk, we develop an algorithm for computing a maximal finitestate subgame perfect equilibrium of a game with omegaregular winning conditions and analyse the complexity of the corresponding decision problem. Document Actions 
