Simple Nash Equilibria for Qualitative Multiplayer Games
This work advances the theoretical understanding of equilibrium existence in multiplayer games with ω-regular objectives, providing necessary and sufficient conditions for memoryless equilibria.
The paper proves that memoryless randomised subgame-perfect equilibria exist in turn-based deterministic games with reachability, safety, and 0-2 Muller objectives, and provides an algorithm to construct them. It also shows that randomisation may be required for memoryless equilibria in games with reachability/Büchi or safety/CoBüchi objectives, and that memoryless equilibria do not exist for other Muller objectives.
We investigate memory requirements for Nash and subgame-perfect equilibria in turn-based deterministic games with $ω$-regular objectives. We prove that memoryless randomised (i.e., stationary) subgame-perfect equilibria always exist in games with reachability, safety, and 0-2 Muller objectives (i.e., Muller objectives for which accepting sets are either up- or downward closed), and any combination of these objectives. We provide an algorithm to construct such an equilibrium. We also show that randomisation may be required to construct memoryless equilibria in games with reachability or Büchi as well as safety or CoBüchi objectives, and that memoryless equilibria need not exist for any other class of Muller objectives (with respect to the Mostowski hierarchy).