DROPS

Document

DOI: 10.4230/LIPIcs.FSTTCS.2023.34

Solving Odd-Fair Parity Games

Authors: Irmak Sağlam and Anne-Kathrin Schmuck

Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)

Abstract

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.

Cite as

Irmak Sağlam and Anne-Kathrin Schmuck. Solving Odd-Fair Parity Games. In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, pp. 34:1-34:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{saglam_et_al:LIPIcs.FSTTCS.2023.34,
  author =	{Sa\u{g}lam, Irmak and Schmuck, Anne-Kathrin},
  title =	{{Solving Odd-Fair Parity Games}},
  booktitle =	{43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)},
  pages =	{34:1--34:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-304-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{284},
  editor =	{Bouyer, Patricia and Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.34},
  URN =		{urn:nbn:de:0030-drops-194077},
  doi =		{10.4230/LIPIcs.FSTTCS.2023.34},
  annote =	{Keywords: parity games, strong transition fairness, algorithmic game theory}
}

Search Results

Documents authored by Schmuck, Anne-Kathrin

Solving Odd-Fair Parity Games

Abstract

Cite as

Thanks for your feedback!

Could not send message