Beyond Value Iteration for Parity Games: Strategy Iteration with Universal Trees

Zhuan Khye Koh, Georg Loho

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)
19 Downloads (Pure)

Abstract

Parity games have witnessed several new quasi-polynomial algorithms since the breakthrough result of Calude et al. (STOC 2017). The combinatorial object underlying these approaches is a universal tree, as identified by Czerwinski et al. (SODA 2019). By proving a quasi-polynomial lower bound on the size of a universal tree, they have highlighted a barrier that must be overcome by all existing approaches to attain polynomial running time. This is due to the existence of worst case instances which force these algorithms to explore a large portion of the tree. As an attempt to overcome this barrier, we propose a strategy iteration framework which can be applied on any universal tree. It is at least as fast as its value iteration counterparts, while allowing one to take bigger leaps in the universal tree. Our main technical contribution is an efficient method for computing the least fixed point of 1-player games. This is achieved via a careful adaptation of shortest path algorithms to the setting of ordered trees. By plugging in the universal tree of Jurdzinski and Lazic (LICS 2017), or the Strahler universal tree of Daviaud et al. (ICALP 2020), we obtain instantiations of the general framework that take time O(mn2 log n log d) and O(mn2 log3 n log d) respectively per iteration.

Original languageEnglish
Title of host publication47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022
EditorsStefan Szeider, Robert Ganian, Alexandra Silva
PublisherDagstuhl
ISBN (Electronic)9783959772563
DOIs
Publication statusPublished - 1 Aug 2022
Event47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022 - Vienna, Austria
Duration: 22 Aug 202226 Aug 2022
Conference number: 47

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume241
ISSN (Print)1868-8969

Conference

Conference47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022
Abbreviated titleMFCS 2022
Country/TerritoryAustria
CityVienna
Period22/08/2226/08/22

Keywords

  • parity games
  • progress measure
  • strategy iteration
  • universal trees
  • value iteration

Fingerprint

Dive into the research topics of 'Beyond Value Iteration for Parity Games: Strategy Iteration with Universal Trees'. Together they form a unique fingerprint.

Cite this