2026-07-24T05:15:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19407 2024-03-06T11:03:58Z ddc:004 open_access

Solving Odd-Fair Parity Games Sağlam, Irmak Schmuck, Anne-Kathrin parity games strong transition fairness algorithmic game theory This paper discusses the problem of efficiently solving parity games where player Odd has to obey an additional strong transition fairness constraint on its vertices - given that a player Odd vertex v is visited infinitely often, a particular subset of the outgoing edges (called live edges) of v has to be taken infinitely often. Such games, which we call Odd-fair parity games, naturally arise from abstractions of cyber-physical systems for planning and control. In this paper, we present a new Zielonka-type algorithm for solving Odd-fair parity games. This algorithm not only shares the same worst-case time complexity as Zielonka’s algorithm for (normal) parity games but also preserves the algorithmic advantage Zielonka’s algorithm possesses over other parity solvers with exponential time complexity. We additionally introduce a formalization of Odd player winning strategies in such games, which were unexplored previous to this work. This formalization serves dual purposes: firstly, it enables us to prove our Zielonka-type algorithm; secondly, it stands as a noteworthy contribution in its own right, augmenting our understanding of additional fairness assumptions in two-player games. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Irmak Sağlam and Anne-Kathrin Schmuck 2023 Is Part Of LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2023.34 urn:nbn:de:0030-drops-194077 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.34 eng https://creativecommons.org/licenses/by/4.0/legalcode