技术摘要：利用通用树解决 Streett 和 Emerson-Lei 游戏

问题陈述

本文研究了求解具有 $\omega$-正则获胜条件的无限时长双人游戏的计算复杂度，具体针对 Streett 和 Emerson-Lei (EL) 游戏。虽然通过引入通用树（universal trees），奇偶博弈（parity games）已被证明可以在拟多项式时间内求解，但将这些结果扩展到更具表达力的条件仍具有挑战性。

现有的 Streett 和 EL 游戏处理方法通常依赖于向奇偶博弈的归约。然而，这些归约往往会带来显著的开销：

1. 复杂度膨胀： 将 EL 条件转换为奇偶博弈通常会导致优先级数量的阶乘级膨胀（例如，使用最新出现记录构造法），导致时间复杂度达到 $O(m \cdot (c!)^2 \cdot n^{1+o(1)})$。
2. 内存效率低下： 从奇偶博弈归约中提取的策略往往会将双方的内存需求都嵌入到竞技场中，导致生成的策略对于原始游戏而言并非内存最优。
3. 缺乏直接理解： 通用树在直接求解非位置性游戏（即需要内存的获胜策略游戏）中的作用此前尚不明确。Streett 和 EL 游戏已知需要内存，并可通过 Zielonka 树进行分析，但此前尚不清楚是否可以直接应用通用树来求解它们而无需进行归约。

方法论

作者提出了一种直接求解框架，该框架集成了通用树（用于限制进度）与 Zielko 树（用于管理内存需求）。该方法由三个主要部分组成：

1. 分层树与签名

论文建立了一种通过映射到分层树（通用树的一种特定结构属性）来对 Streett 和 EL 游戏的获胜区域进行编码的方法。

• Streett 游戏： 获胜区域基于 Zielonka-McNaughton 算法进行划分。作者定义了“签名（signatures）”，将顶点映射到通用树 $U(n, k)$ 的叶子节点或子树，其中 $k$ 是 Streett 对的数量。这些签名遵循吸引子计算和递归子问题的顺序。
• Emerson-Lei 游戏： 该方法通过使用获胜条件的 Zielonka 树 $Z(\alpha)$ 进行了扩展。签名将顶点映射为一对组合，该组合包含一个通用树 $U(n, c/2)$ 中的节点和一个 Zielonka 树中的节点（或特定的偶分支方向）。这种结构捕捉了满足复杂布尔组合公平条件所需的交错内存状态。

2. 秩提升算法（非对称、枚举型）

作者在游戏顶点、内存状态（Streett 游戏中为置换；EL 游戏中为奇方向序列）与通用树的乘积之上定义了排名（rankings）（Streett 排名和 EL 排名）。

• 进度度量： 一个“良好”的排名确保玩家 0 总能取得进展（严格减少排名）以趋向满足获胜条件，同时玩家 1 无法阻止这一进展。
• 内存更新： 排名结合了内存更新。对于 Streett 游戏，访问“授予”集合 $G_i$ 会更新对的置换；对于 EL 游戏，访问特定颜色会更新 Zielonka 树中的路径（奇/偶方向）。
• 算法： **秩提升算法（rank-lifting algorithm）**迭代地更新这些排名，直到达到不动点。该算法从最小排名开始，并根据树结构定义的受控前驱和进度关系提升排名。
• 核心创新： 通过使用拟多项式规模的通用树 $U(n, k)$ 而非指数级规模的通用树，该算法避免了在排名域大小上对对数或颜色数量的指数依赖。

3. 符号化求解（对称、基于吸引子）

对于 EL 游戏，作者还提出了一个符号化算法，该算法通过界定 Zielonka-McNaughton 算法的递归树来工作。

• 该算法并非探索规模与颜色数量阶乘成正比的完整递归树，而是利用通用树来限制递归的深度和分支。
• 该方法通过维护顶点集合（领地/dominions）并使用分层树来追踪这些领地相对于 Zielonka 树结构的规模，从而计算获胜区域（而不显式提取策略）。

核心贡献

1. Streett 游戏的直接求解：

   • 引入了基于通用树的 Streett 排名。
   • 证明了对于任何获胜顶点，在 $U(n, k)$ 上都存在良好的 Streett 排名。
   • 开发了一个求解具有 $n$ 个顶点、$m$ 条边和 $k$ 个对的 Streett 游戏的秩提升算法，时间复杂度为 $O(m \cdot k \log(k) \cdot k! \cdot |U(n, k)|)$。
   • 这改进了之前通过奇偶归约得到的 $O(m \cdot k! \cdot (nk!)^{1+o(1)})$ 的最佳界限。

2. Emerson-Lei 游戏的直接求解：

   • 引入了结合通用树与 Zielonka 树以处理内存需求的 EL 排名。
   • 开发了一个求解具有 $n$ 个顶点、$m$ 条边和 $c$ 个颜色的 EL 游戏的秩提升算法，时间复杂度为 $O(m \cdot c \log(c) \cdot c! \cdot |U(n, c/2)|)$。
   • 这改进了之前最优的 $O(m \cdot c! \cdot (nc!)^{1+o(1)})$ 复杂度。
   • 内存最优性： 与奇偶博弈归约不同，从这些排名中提取的策略使用的内存大小至多为 $m^+_\alpha$（条件的优化内存），而非归约后可能更大的内存。

3. EL 游戏的符号化算法：

   • 提出了一个使用通用树界定 Zielonka-McNaughton 算法递归的符号化算法。
   • 实现了 $O(m \cdot c \cdot c! \cdot n^{2 \log(c/2)+O(1)})$ 的时间复杂度，通过将时间复杂度中的 $n^c$ 因子替换为 $|U(n, c)|$，改进了现有的符号化方法。

4. 理论统一：

   • 证明了分层树（通用树的一种严格形式）足以捕捉非位置性游戏的获胜区域结构。
   • 表明标准的拟多项式通用树（例如 Jurdziński 和 Lazic 提出的）是分层树，从而能够实现 Streett 和 EL 游戏的拟多项式加速。

结果与复杂度分析

论文提供的复杂度改进（其中 $|U(n, k)| \approx n^{\log k}$）：

• Streett 游戏：

  • 此前： $O(m \cdot k! \cdot (nk!)^{1+o(1)})$
  • 现在： $O(m \cdot k \log(k) \cdot k! \cdot n^{\log k})$
  • 改进： 消除了 $n$ 的指数中对 $k$ 的二次阶乘依赖。

• Emerson-Lei 游戏：

  • 此前： $O(m \cdot c! \cdot (nc!)^{1+o(1)})$
  • 现在： 对于秩提升法为 $O(m \cdot c \log(c) \cdot c! \cdot n^{\log(c/2)})$，对于符号化法为 $O(m \cdot c \cdot c! \cdot n^{2 \log(c/2)+O(1)})$。
  • 改进： 同样消除了秩提升法中 $n$ 的指数对 $c$ 的二次阶乘依赖，并用 $|U(n, c)|$ 替换了符号化方法中的 $n^c$ 因子。

• 内存： 提取的策略是内存最优的，最多使用 $m^+_\alpha$ 个内存状态，而奇偶归约通常需要与归约后的奇偶博弈规模成比例的内存（这在原参数下可能是指数级的）。

意义与主张

本文声称反驳了以下普遍观点：即通用树仅与具有无记忆（位置性）获胜策略的游戏相关。通过成功地将通用树（用于进度度量）与 Zielonka 树（用于内存管理）相结合，作者将奇偶博弈和 Rabin 博弈的拟多项式突破提升到了更通用、更复杂的 Streett 和 Emerson-Lei 游戏场景中。

其意义在于：

1. 打破“二次阶乘”壁垒： 这些算法打破了之前基于归约的方法中存在的对对/颜色数量的 $(k!)^2$ 或 $(c!)^2$ 依赖。
2. 直接性： 解决方案是直接的，避免了转换为奇偶博弈的中间步骤，从而保留了原始获胜条件的简洁性。
3. 最优性： 该方法产生内存使用最优的策略，这是通过归约方法经常丢失的特性。
4. 概念洞察： 该工作提供了一个精确的配方（通过 Zielonka 树），说明了如何通过交织更简单的无内存条件的排名，来组合复杂条件的排名。

作者指出，他们的结果与 EL 游戏的指数时间假设（ETH）下界是一致的，因为通用树的大小相对于 $n$ 仍是多项式对数级的。他们还提到，该方法也适用于 Muller 游戏，尽管针对一般 Muller 条件的精确界限仍作为未来的研究工作。