一句话：为奇偶博弈提出通用树上的策略迭代框架，绕过值迭代需探索大量树节点的障碍，并实现每轮高效更新。
自 2017 年 Calude 等人的突破以来，奇偶博弈已有多种准多项式算法，其组合基础是通用树。Czerwiński 等人证明通用树大小有准多项式下界，表明现有算法可能被迫探索大量树节点，构成通向多项式时间的障碍。本文提出可应用于任意通用树的策略迭代框架：它至少不慢于对应值迭代，并允许在树中更大跳跃。核心技术创新是高效计算 1-player 游戏的最小不动点，方法是将最短路算法适配到有序树。代入 Jurdziński–Lazič 通用树或 Daviaud 等人的 Strahler 通用树，每轮迭代时间复杂度分别为 O(mn^2 log n log d) 和 O(mn^2 log^3 n log d)。
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 Czerwi\'nski 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 Jurdzi\'nski and Lazi\'c (LICS 2017), or the Strahler universal tree of Daviaud et al. (ICALP 2020), we obtain instantiations of the general framework that take time $O(mn^2\log n\log d)$ and $O(mn^2\log^3 n \log d)$ respectively per iteration.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@article{KohL22,
title = {Beyond Value Iteration for Parity Games: Strategy Iteration with Universal Trees},
author = {Zhuan Khye Koh and Georg Loho},
journal = {Logical Methods in Computer Science},
volume = {Volume 21, Issue 2},
year = {2025},
doi = {10.46298/lmcs-21(2:24)2025}
}