Nathanaël Fijalkow

CNRS, LaBRI, Bordeaux, and The Alan Turing Institute of data science, London

Quasipolynomial upper and lower bounds
for parity games

Main objective

Give a unified and simple presentation the three quasipolynomial time algorithms

Reports on

Research blog

Parity games

Parity: the maximal priority appearing infinitely often is even

Solving parity games

INPUT: A parity game and initial vertex $v_0$
QUESTION: Does Eve have a winning strategy from $v_0$?

Parameters: $n$ (number of vertices) and $d$ (number of priorities)

Best algorithms (Calude, Jain, Khoussainov, Li, and Stephan, then Jurdziński and Lazić, then Lehtinen) $$O(n^{\log(d)}) = O(d^{\log(n)})$$


Positional strategy $$\sigma : V \to E$$
Theorem: If Eve has a winning strategy in a parity game, she also has a positional winning strategy. The same holds for Adam.

Universal graphs

Definition: A graph satisfies parity if all paths in the graph satisfy parity
Definition: A (graph) homomorphism is $\phi : V \to V'$ st $$(v,i,v') \in E \Longrightarrow (\phi(v),i,\phi(v')) \in E$$
Definition: A graph $U$ is $(n,d)$-universal if
  • it satisfies parity
  • all graphs of size $n$ with $d$ priorities satisfying parity can be homomorphically mapped into $U$

Reduction to safety games

Let $G$ parity game, $U$ universal graph. Construct safety game $G \times U$: Eve chooses the evolution in $U$

Lemma: Eve has a winning strategy in $G$ if and only if she has a strategy to play forever in $G \times U$

Algorithm: Solve the safety game $G \times U$, complexity $n \cdot |U|$
Lemma: Eve has a winning strategy in $G$ if and only if she has a strategy to play forever in $G \times U$

If Eve wins in $G$ she has a positional strategy. Then $G_{\sigma}$ embeds into $U$, induces a winning strategy in $G \times U$
If Eve wins in $G \times U$ then this strategy is winning in $G$ because $U$ satisfies parity

Main results

Theorem: the following quantities are equal
  • The smallest universal graph
  • The smallest universal tree
  • The smallest separating automaton

Universal trees

Definition: A tree is $(n,h)$-universal if it embeds all trees of height $h$ with $n$ leaves


Fact: Universal trees are exactly saturated universal graphs!

Upper bounds

We construct a $(n,h)$-universal tree. Inductively
Fact: there exists a balanced node

Lower bounds

$$g(n,h) = \sum_{d = 1}^n g(\lfloor n / d \rfloor,h-1)$$ Let $T$ a $(n,h)$-universal tree and $\delta \in [1,n]$.
Claim: the number of nodes at depth $h-1$ of degree $\ge \delta$ is at least $g(\lfloor n / \delta \rfloor,h-1)$.
Claim: $T_\delta$ is $(\lfloor n / \delta \rfloor,h-1)$-universal