2026-07-21T20:03:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24138 2025-11-12T13:33:31Z ddc:004 open_access

Games with ω-Automatic Preference Relations Bruyère, Véronique Grandmont, Christophe Raskin, Jean-François Games played on graphs Nash equilibrium ω-automatic relations ω-recognizable relations constrained Nash equilibria existence problem This paper investigates Nash equilibria (NEs) in multi-player turn-based games on graphs, where player preferences are modeled as ω-automatic relations via deterministic parity automata. Unlike much of the existing literature, which focuses on specific reward functions, our results apply to any preference relation definable by an ω-automatic relation. We analyze the computational complexity of determining the existence of an NE (possibly under some constraints), verifying whether a given strategy profile forms an NE, and checking whether a specific outcome can be realized by an NE. When a (constrained) NE exists, we show that there always exists one with finite-memory strategies. Finally, we explore fundamental properties of ω-automatic relations and their implications in the existence of equilibria. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Véronique Bruyère and Christophe Grandmont and Jean-François Raskin 2025 Is Part Of LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2025.31 urn:nbn:de:0030-drops-241381 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.31 eng https://creativecommons.org/licenses/by/4.0/legalcode