奇偶博弈的小进展度量

形式陈述

小进展度量用有限排序标记求解min-even奇偶博弈。设nⱼ为优先级j的顶点数，只为出现的奇优先级j建立坐标，按j从小到大排列，小优先级坐标更重要。有限度量域为

M=\prod_{j\text{奇}}\{0,1,\ldots,n_j\}, \qquad M^\top=M\cup\{\top\}.

M按字典序排序，⊤大于一切有限元组。写x≥ₚy，表示只比较优先级不大于p的奇坐标；未纳入的后缀忽略。即使p以下没有奇坐标，⊤仍严格大于有限元组，且⊤=ₚ⊤。

定义Prog(x,p)：若x=⊤，结果为⊤；否则取满足下述条件的字典序最小有限元组y，若不存在则为⊤：p为偶数时要求y≥ₚx，p为奇数时要求y>ₚx。取最小意味着被忽略的后缀清零，奇数处加一时可向更重要坐标进位。

每顶点v保存μ(v)，初始全零。一次提升只更新v：

\mu(v)\leftarrow\max\!\left(\mu(v), \begin{cases} \min_{(v,w)\in E}\operatorname{Prog}(\mu(w),\Omega(v)),&v\in V_0,\\ \max_{(v,w)\in E}\operatorname{Prog}(\mu(w),\Omega(v)),&v\in V_1. \end{cases}\right).

内层最小/最大都按完整字典序；图总有后继，所以不会取空集合。按固定顺序反复扫描全部顶点，直到一整轮没有变化。最终μ(v)有限的顶点恰为Even获胜区，其余⊤为Odd获胜区。

直觉

有限度量像带多层重置的欠账。经过奇数p时，必须为这一层取得严格进展；经过更小的偶数时，可以清掉更不重要的欠账。这样允许某些无限运行，而不是用一条普通自然数秩禁止一切无限循环。

例如只有奇坐标1时，优先级1要求源端比后继大，优先级2只要求不小；优先级0则把任意有限后继的需要重置为0。因此1与2组成的坏环无法用有限数值支撑，0却可以让合法的0/1循环闭合。

Even只需选择一条满足证书的后继，Odd的每条合法后继都须满足，所以提升规则分别取min和max。若后继已经为⊤，即便当前优先级0也不能把它洗成有限值：有限次好颜色不能挽救后面必败的整个无限后缀。

有限进展数在偶色0处重置，纯奇色自环不断提升直到顶元素 — q的奇色1可选择r的偶色0，稳定为μ(q)=1、μ(r)=0；b的奇色1自环升到⊤，u由对手可选b也升到⊤。

例子与边界

一坐标的完整提升表

给定四顶点，全部边如下：

顶点	行动者	优先级	后继
q	Even	1	r,b
r	Even	0	q
b	Odd	1	b
u	Odd	2	q,b

奇色1共有q、b两个顶点，所以M={0,1,2}，再加⊤。按q、r、b、u的固定顺序扫描，更新后值立即供本轮后续顶点使用：

扫描完成后	μ(q)	μ(b)	μ(u)
初始	0	0	0
第1轮	1	1	1
第2轮	1	2	2
第3轮	1	⊤	⊤
第4轮	1	⊤	⊤

q取r方向，Prog(0,1)=1；r面对有限的μ(q)=1，但优先级0没有奇前缀要求，Prog(1,0)=0。b每轮要求比自身旧值更大，超过2后只能⊤。u属于Odd，可以选b，因此取最坏后继并传播⊤。

最终Even策略q→r、r→q使0无限出现，获胜；Odd从u选择b并永留1自环。不能只看u本身优先级2为偶，就说它安全。

两坐标的截断与进位

另设某图有n₁=2、n₃=1，元组按(坐标1,坐标3)排列。对x=(1,1)：

\operatorname{Prog}(x,0)=(0,0),\quad \operatorname{Prog}(x,2)=(1,0),\quad \operatorname{Prog}(x,3)=(2,0).

优先级2只比较第一个奇坐标，所以保留1、清掉后缀。优先级3须严格增加完整两坐标；第二坐标已经到上界1，于是向第一坐标进位，得到(2,0)。只有当前缀已经没有更大有限值时才到⊤，不能把每个坐标溢出都独立地直接判失败。

推论与应用

固定点为什么是获胜证书

若最终μ(v)有限，则Even顶点可以选择使Prog最小的后继；Odd顶点所有后继的需要都不超过μ(v)。这些后继也必为有限值，因此有限区域在该策略下闭合。

沿任何允许边，源度量在当前优先级前缀上不小于后继，源优先级为奇数时严格大于。若存在一个最小优先级为奇数k的循环，则所有边在k前缀上都不增，至少经过一个优先级k源点时严格下降。绕回起点将得到同一有限前缀严格小于自身，矛盾。所以所有循环都偶，Even策略获胜。

反方向需要“小度量存在”引理：若一个有限优先级图的全部循环都偶，就能为它分配上述nⱼ界内的元组。其证明逐层处理最低色：最低偶色顶点可作为重置点；最低奇色顶点不能处在该层的回返环内，否则直接形成最小色为奇的循环，因而可沿无回边分块递归编号。合并分块时，各奇坐标的范围相加，至多用掉该奇色顶点总数nⱼ。

对Even获胜区固定一份位置获胜策略，保留Odd的全部边，所得图的循环全偶，所以存在这样的小度量；其他区域填⊤即可扩成全图证书。因此小域没有漏掉真正的Even获胜顶点。位置策略存在性由奇偶位置确定性提供，不是由提升表猜出来的。

单调提升为什么找到最小证书

逐点比较μ的值，使所有赋值构成一个有限完备格。每个提升算子单调，外层max又确保值从不下降。有限域中不可能无限严格上升，固定扫描最终停止。

若ρ是一份正确证书，初始零赋值不超过ρ；单调性保证每一步提升仍不超过ρ。因此停止结果是所有证书之下的最小不动点，可将一整轮固定扫描看作所有局部提升的复合算子 $T$ 。每个局部算子都单调且膨胀，所以 $T$ 也是如此；一轮后完全不变，当且仅当这一轮的每个局部更新都不变。

有限赋值格中的每个非空有向子集都有最大元，因此任意单调自映射都保持其上确界，满足 Scott 连续性。于是Kleene 不动点定理确实适用于 $T$ ：从底元整轮迭代得到它的最小不动点，也就是全部局部证书条件的最小共同解。结合前面的存在与可靠性两向结论，有限区域恰为Even获胜区。

成本与策略输出范围

令r为奇坐标数， $P=\prod_{j\text{奇}}(n_j+1)$ 。每顶点最多严格提升P次，全网至多nP次。朴素完整扫描一轮需 $O((r+1)m)$ 操作；每个未终止扫描至少有一次严格提升，因此得到保守时间界 $O((r+1)m(nP+1))$ ，存储为 $O(n(r+1)+m)$ 个字段。字段还需相应整数位数。

这个界明确对应上面的完整扫描实现，没有把寻找可提升顶点的代价隐藏起来。更精细的调度与维护可改进时间常数和界，但P随奇色维数增长，不能将一般算法称为线性。

有限度量直接给Even位置策略；⊤只标出Odd获胜区，不能在所有⊤后继中任意挑一条就声称得到Odd反策略。需要时可另用Zielonka，或把所有优先级加1并交换双方身份，再运行一次度量算法，为原Odd取得有限证书和选择。

参考资料

Marcin Jurdziński, “Small Progress Measures for Solving Parity Games”, STACS, 2000，July2000修订稿，§3 Definitions3、6与Theorem5，§4提升算子、固定点与策略；本页保守复杂度显式包含完整扫描开销

形式陈述 ​

一坐标的完整提升表 ​

两坐标的截断与进位 ​

固定点为什么是获胜证书 ​

单调提升为什么找到最小证书 ​

成本与策略输出范围 ​