パリティゲーム
パリティゲーム (parity games) は彩色された有向グラフ上でプレイされる理論上のゲームである。各ノードは優先度と呼ばれる(通常は有限種類の)自然数で彩色されている。このゲームはプレイヤー0とプレイヤー1の二名によってプレイされる。各プレイヤーは、ゲーム上に一個だけある駒をグラフの辺にそって動かす。手番は、その駒の現在地によって決められている。この操作を繰り返し(場合によっては無限回)行うことにより、プレイと呼ばれるパスが定まる。
有限長のプレイの場合、駒を動かせなくなったプレイヤーが敗者で、敗者でない側が勝者となる。無限長のプレイの勝者は、プレイ中に現れる優先度の値によって決定される。プレイ中に無限回現れた優先度のうち、最大の値が偶数ならばプレイヤー0の勝利、奇数ならばプレイヤー1の勝利となる。(偶奇が逆だったり、最大値のかわりに最小値を使う場合もある。) この偶奇性が「パリティ」の由来であろう。
パリティゲームはボレル階層の3層目に属する。したがってパリティゲームは決定的である。
"n"後者演算に関する二階の理論の決定可能性に関するラビンの証明では、パリティゲームに類似のゲームが暗黙的に使われ、該当ゲームの決定性も証明されている。 ナスター-タルスキの定理を使えば、パリティゲームの決定性に対するより単純な証明を与えることもできる。
さらに、パリティゲームは履歴なしの決定性 (history-free determinacy, memoryless determinacy) をもつ。 これは、あるパリティーゲームの初期位置で、どちらかのプレイヤーが必勝戦略を持つとき、履歴なしの必勝戦略、すなわち今までの駒の動きに関係なく、現在位置だけで次の行き先を決めるような戦略、が存在するというものである。