12th Conference on Theoretical Aspects of Rationality and Knowledge

Nash equilibrium in generalised Muller games

Soumya Paul and Sunil Simon

Proceedings of the 29th Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2009), pages 335-346, 2009.


We suggest that extending Muller games with preference ordering for players is a natural way to reason about unbounded duration games. In this context, we look at the standard solution concept of Nash equilibrium for non-zero sum games. We show that Nash equilibria always exists for such generalised Muller games on finite graphs and present a procedure to compute an equilibrium strategy profile. We also give a procedure to compute a subgame perfect equilibrium when it exists in such games.

Download PDF (from drops.dagstuhl.de).