2022/08/22 by Volker Diekert, Diekert, Volker, Manfred Kufleitner +1
Computer Science · Economics, Econometrics and Finance · #Artificial Intelligence in Games #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Game Theory and Voting Systems #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge
paper · pdf · doi:10.48550/arxiv.2208.10121
openalex publication_date 2022/08/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Parity games are positionally determined. This is a fundamental and classical result. In 2010, Calude et al. showed a breakthrough result for finite parity games: the winning regions and their positional winning strategies can be computed in quasi-polynomial time. In the present paper we give a self-contained and detailed proofs for both results. The results in this paper are not meant to be original. The positional determinacy result is shown for possibly infinite parity games using the ideas of Zielonka which he published in 1998. In order to show quasi-polynomial time, we follow Lehtinen's register games, which she introduced in 2018. Although the time complexity of Lehtinen's algorithm is not optimal, register games are conceptually simple and interesting in their own right. Various of our proofs are either new or simplifications of the original proofs. The topics in this paper include the definition and the computation of optimal attractors for reachability games, too.