2026-08-21T18:34:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27467 2026-08-21T14:42:41Z ddc:004 open_access

Simple Nash Equilibria for Qualitative Multiplayer Games Alluwaym, Mona Main, James C. A. Schewe, Sven games on graphs multiplayer games Nash equilibria subgame-perfect equilibria memoryless strategies 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mona Alluwaym and James C. A. Main and Sven Schewe 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.85 urn:nbn:de:0030-drops-274679 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.85 eng https://creativecommons.org/licenses/by/4.0/legalcode