The complexity of Nash equilibria in infinite multiplayer games

We study the complexity of Nash equilibria in infinite (turn-based, qualitative) multiplayer games. Chatterjee & al. showed the existence of a Nash equilibrium in any such game with omega-regular winning conditions, and they devised an algorithm for computing one. We argue that in applications it is often insufficient to compute just some Nash equilibrium. Instead, we enrich the problem by allowing to put (qualitative) constraints on the payoff of the desired equilibrium. Our main result is that the resulting decision problem is NP-complete for games with co-Buchi, parity or Streett winning conditions but fixed-parameter tractable for many natural restricted classes of games with parity winning conditions. For games with Buchi winning conditions we show that the problem is, in fact, decidable in polynomial time. We also analyse the complexity of strategies realising a Nash equilibrium. In particular, we show that pure finite-state strategies as opposed to arbitrary mixed strategies suffice to realise any Nash equilibrium of a game with w-regular winning conditions with a, qualitative constraint on the payoff.