パリティゲーム
A t t r i ( U ) 0 := U A t t r i ( U ) j + 1 := A t t r i ( U ) j ∪ { v ∈ V i ∣ ∃ ( v , w ) ∈ E : w ∈ A t t r i ( U ) j } ∪ { v ∈ V 1 − i ∣ ∀ ( v , w ) ∈ E : w ∈ A t t r i ( U ) j } A t t r i ( U ) := ⋃ j = 0 ∞ A t t r i ( U ) j {\displaystyle {\begin{aligned}Attr_{i}(U)^{0}&:=U\\Attr_{i}(U)^{j+1}&:=Attr_{i}(U)^{j}\cup \{v\in V_{i}\mid \exists (v,w)\in E:w\in Attr_{i}(U)^{j}\}\cup \{v\in V_{1-i}\mid \forall (v,w)\in E:w\in Attr_{i}(U)^{j}\}\\Attr_{i}(U)&:=\bigcup _{j=0}^{\infty }Attr_{i}(U)^{j}\end{aligned}}}
別の言い方をすれば、初期集合 U から開始して、「プレイヤー0の手番となるノードで、 U に一歩で到達できるノード」と「プレイヤー1の手番となるノードで、プレイヤー1がどのように選択しても U に入ってしまうノード」をUに追加していく。これを繰り返して止まったときのUがAttr0(U)である。
Zielonkaのアルゴリズムは、優先度の値に関する再帰降下に基づいている。最大優先度が0のときは、どんな戦略であってもプレイヤー0が勝つのは明らかである。
) この偶奇性が「パリティ」の由来であろう。
パリティゲームはボレル階層の3層目に属する。したがってパリティゲームは決定的である。
n後者演算に関する二階の理論の決定可能性に関するラビンの証明では、パリティゲームに類似のゲームが暗黙的に使われ、該当ゲームの決定性も証明されている。 ナスター-タルスキの定理を使えば、パリティゲームの決定性に対するより単純な証明を与えることもできる。
さらに、パリティゲームは履歴なしの決定性 (history-free determinacy, memoryless determinacy) をもつ。 これは、あるパリティーゲームの初期位置で、どちらかのプレイヤーが必勝戦略を持つとき、履歴なしの必勝戦略、すなわち今までの駒の動きに関係なく、現在位置だけで次の行き先を決めるような戦略、が存在するというものである。
いっぽう、もし W 1 − i ′ {\displaystyle W'_{1-i}} が空ではなかった場合、プレイヤー 1 − i {\displaystyle 1-i} は少なくとも W 1 − i ′ {\displaystyle W'_{1-i}} では勝利することができる。なぜならば、プレイヤー i が W 1 − i ′ {\displaystyle W'_{1-i}} から A に逃げることはできない (さもなくば A がアトラクタであることに反する) からである。しかしそれ以外のノードでの必勝性は明らかではないので、プレイヤー 1 − i {\displaystyle 1-i} のアトラクタ B = A t t r 1 − i ( W 1 − i ′ ) {\displaystyle B=Attr_{1-i}(W'_{1-i})} を計算し、これを G から取り除いた、より小さいゲーム G ′′ = G ∖ B {\displaystyle G''=G\setminus B} を得る。するとやはりこのゲームの必勝性を再帰的に解くことができ、各プレイヤーの勝利領域 W i ′′ , W 1 − i ′′ {\displaystyle W''_{i},W''_{1-i}} がわかる。このとき W i = W i ′′ {\displaystyle W_{i}=W''_{i}} かつ W 1 − i = W 1 − i ′′ ∪ B {\displaystyle W_{1-i}=W''_{1-i}\cup B} であることがわかる。
このアルゴリズムは、擬似コードでは以下のように書ける: