DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2026.85

Simple Nash Equilibria for Qualitative Multiplayer Games

Authors: Mona Alluwaym, James C. A. Main, and Sven Schewe

Published in: LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)

Abstract

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).

Cite as

Mona Alluwaym, James C. A. Main, and Sven Schewe. Simple Nash Equilibria for Qualitative Multiplayer Games. In 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 386, pp. 85:1-85:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{alluwaym_et_al:LIPIcs.MFCS.2026.85,
  author =	{Alluwaym, Mona and Main, James C. A. and Schewe, Sven},
  title =	{{Simple Nash Equilibria for Qualitative Multiplayer Games}},
  booktitle =	{51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)},
  pages =	{85:1--85:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-442-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{386},
  editor =	{Kouck\'{y}, Michal and Petrișan, Daniela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.85},
  URN =		{urn:nbn:de:0030-drops-274679},
  doi =		{10.4230/LIPIcs.MFCS.2026.85},
  annote =	{Keywords: games on graphs, multiplayer games, Nash equilibria, subgame-perfect equilibria, memoryless strategies}
}

Search Results

Documents authored by Alluwaym, Mona

Simple Nash Equilibria for Qualitative Multiplayer Games

Abstract

Cite as

Thanks for your feedback!

Could not send message